Jump to content

"Хэш хүснэгт"-ны өөр хувилбарууд

засварлах хураангуй байхгүй
No edit summary
{{distinguish|Хэш жагсаалт эсвэл хэш мод}}
{{Огноо | year=2013 | month=1}}
{{Infobox data structure
|name=Hash table
|type=Unordered [[associative array]]
|invented_by=
|invented_year=1953
|space_avg=O(''n'')<ref name="Cormen et al">
{{Номны ишлэл
| зохиогч = [[Thomas H. Cormen]] [et al.]
| гарчиг = [[Introduction to Algorithms]]
| дугаар = 3rd
| хэвлэлийн газар = Massachusetts Institute of Technology
| он = 2009
| isbn = 978-0-262-03384-8
| тэмдэглэл = Section 11: Hash Tables,
| хуудас = 253–280
}}
</ref>
 
|space_worst=O(''n'')
|search_avg=O(1)
|search_worst=O(''n'')
|insert_avg=O(1)
|insert_worst=O(''n'')
|delete_avg=O(1)
|delete_worst=O(''n'')
}}
[[File:Hash table 3 1 1 0 1 0 0 SP.svg|thumb|315px|right|Утасны хадгалсан дугаарыг хэш хүснэгтээр хийх]]
Хайлтын харьцуулалтын туслламжтайгаар гүйцэтгэж байсан өмнөх аргуудаас ялгаатай нэг арга бол хеш хаяглалт юм. Энэ хайлтын арга нь түлхүүр утганд арифметик үйлдлээр хувиргалт хийн өгөгдөл байрлах хүснэгтийн хаягийг гарган авч шууд ханддаг.
 
===Хуваах арга===
 
Түлхүүрийн тоо n-ээс их m тоог сонгоно. Хаяглалын зөрчилийг багасгахын тулд ''m'' анхны тоо байх шаардлагатай. Эндээс H функцыг
H(k) = k(mod M) гэж тодорхойлдог. Хэрэв түлхүүр нь тоон утгаар өгөгдсөн бол функцид шууд ашиглана. Харин түлхүүр нь тэмдэгт мөрөөр өгөгдвөл түүнийг эхлээд тоон утгаар илэрхийлэх шаардлагатай.
 
===Хаягийн зөрчлийг зохицуулах аргууд===
 
Түлхүүрийг дээрх функцээр хүснэгтийн хаяг уруу хувиргах үед ижил хаягаар тодорхойлогдсон түлхүүрүүдийг зохицуулах асуудал яригдана. Хамгийн энгийн арга бол хүснэгтийн хаяг бүрд жагсаалт ашиглах ба цаг хаягаар тодорхойлогдох түлхүүрийг агуулах болно. Өөрөөр хэлбэл ''m'' хэмжээтэй хүснэгтийн хувьд ''m'' салангид жагсаалт ашиглагдах юм.
 
===Зөрчил===
 
Өөр шинэ хосын хэш хүснэгтийн харгалзах үүрэнд өөр хос байвал [[Зөрчил (компьютер)|зөрчил(collision)]] үүснэ.
 
===Халилт===
 
Харгалзах хүснэгтийн үүр дүүрэн бол халилт(overflow) үүснэ.
 
[[Ангилал:Өгөгдлийн бүтэц]]
[[en:hash table]]