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

засварлах хураангуй байхгүй
No edit summary
No edit summary
{{distinguish|HashХэш list|Hashжагсаалт treeэсвэл хэш мод (disambiguation){{!}}Hash tree}}
{{Огноо | year=2013 | month=1}}
{{Use mdy dates|date=January 2013}}
<!--THE UNDERSCORE "_" IS SIGNIFICANT, DO NOT CHANGE IT TO SPACE-->
{{Infobox data structure
|name=Hash table
|delete_worst=O(''n'')
}}
[[File:Hash table 3 1 1 0 1 0 0 SP.svg|thumb|315px|right|УтасгыУтасны хадгалсан дугаарыг хешхэш хүснэгтээр хийх]]
Хайлтын харьцуулалтын туслламжтайгаар гүйцэтгэж байсан өмнөх аргуудаас ялгаатай нэг арга бол хеш хаяглалт юм. Энэ хайлтын арга нь түлхүүр утганд арифметик үйлдлээр хувиргалт хийн өгөгдөл байрлах хүснэгтийн хаягыгхаягийг гарган авч шууд ханддаг.
 
 
 
Хэрэв бидэнд n ширхэг ялгаатай түлхүүр утгууд 1-ээс n-ийн хооронд өгөгдвөл к утгатай түлхүүрийн өгөгдлийн массивын к дугаар элементээс шууд авах боломжтой байдаг. Тэгвэл hash хаяглал нь түлхүүрийн утга тодорхой биш, ерөнхий тохиолдолд энгийн энэ арга дээр үндэслэгддэг.
 
Hash хаяглалын тусламжтайгаар хийх хайлтын эхний алхам бол хайх түлхүүрийн утгыг хүснэгтийн хаяг руууруу хувиргах үйлдэл юм. Энэ үйлдэл hash функцынээр хийгддэг. Зарчмын хувьд, hash функц нь ялгаатай түлхүүр бүрийг ялгаатай хаягт хувиргах ёстой боловч ингэж бүрэн төгс тодорхойлох hash[[хэш функц]] байддаггүйбайдаггүй. Иймээс 2 ба түүнээс олон ялгаатай түлхүүрүүд хүснэгтийн ижил хаягаар тодорхойлогдох тохиолдол гардаг. Ийм түлхүүрүүдийн зөрчилийгзөрчлийг зохицуулах үйлдэл нь хайлтын хоёрдох алхам болдог ба үүнийг жагсаалт ашиглан зохицуулж болдог. Энэ арга нь хэдэн түлхүүр гарч ирэхийг урьдчилан мэдэхгүй тохиолдолд динамикаар зохицуулахад илүү тохиромжтой юм. Үүнээс гадна массив ашиглан шийдэх зарим аргууд байдаг.
 
 
Hash хаяглалын тусламжтайгаар хийх хайлтын эхний алхам бол хайх түлхүүрийн утгыг хүснэгтийн хаяг руу хувиргах үйлдэл юм. Энэ үйлдэл hash функцынээр хийгддэг. Зарчмын хувьд, hash функц нь ялгаатай түлхүүр бүрийг ялгаатай хаягт хувиргах ёстой боловч ингэж бүрэн төгс тодорхойлох hash функц байддаггүй. Иймээс 2 ба түүнээс олон ялгаатай түлхүүрүүд хүснэгтийн ижил хаягаар тодорхойлогдох тохиолдол гардаг. Ийм түлхүүрүүдийн зөрчилийг зохицуулах үйлдэл нь хайлтын хоёрдох алхам болдог ба үүнийг жагсаалт ашиглан зохицуулж болдог. Энэ арга нь хэдэн түлхүүр гарч ирэхийг урьдчилан мэдэхгүй тохиолдолд динамикаар зохицуулахад илүү тохиромжтой юм. Үүнээс гадна массив ашиглан шийдэх зарим аргууд байдаг.
 
 
 
Hash хаяглалыг хугацаа ба зай хэмнэсэн сайн жишээний нэг гэж хэлж болно. Хэрэв санах ойн хязгаарлалт байхгүй бол түлхүүр утгагд санах ойн хязгаарыг ашигласанаар санах ой руу зөвхөн нэг удаагын хандалтаар хайлтыг гүйцэтгэх болно. Хэрэв хугацааны хязгаарлалтгүй бол хүрэлцээт хамгийн бага санах ойн хувьд энгийн дараалан хийх аргыг ашиглаж болно. Тэгвэл hash хаяглал нь энэ 2 туйлыг тэнцүүлэн хугацаа ба зайг ухаалгаар ашигладаг.
 
 
==Hash функц==
Эхний алхамд түлхүүрийг хүснэгтийн хаягруу хувиргах hash функц тодорхойлох ёстой. Энэ процесс нь санамсаргүй тоо үүсгэхтэй төстэй арифметик үйлдэл юм. Өөрөөр хэлбэл к түлхүүрийн олонлогыг [0,m-1] гэсэн (m хүснэгтийн хэмжээ) мужийн хоорондох бүхэл тоонуудруу хувиргах H:K->M функцыг тодорхойлох болно.
H функцыг тодорхойлоход 2 үндсэн шалгуур баримтлах шаардлагатай. Үүний эхний шаардлага нь Н функц маш хурдан, хялбар байх ёстой. 2дахь шаардлага нь Н функцээр хаяглагдах түлхүүрүүд хамгийн бага зөрчилтэйгээр хүснэгтийн m байрлалд дархсан байх шаардлагатай. Гэвч бодит байдал дээр түлхүүрүүд болон хаягуудыг урьдчилан мэдэхгүй тохиолдолд 2 дахь шаардлагыг төгс хангаж чаддаггүй. Иймд бид түгээмэл ашиглагддаг hash[[Хэш функцыгфункц]]ийг авч үзье.
 
 
 
===Хуваах арга===
Түлхүүрийн тоо n-ээс их m тоог сонгоно. Хаяглалын зөрчилийг багасгахын тулд m анхны тоо байх шаардлагатай. Эндээс H функцыг
H(k) = k(mod M) гэж тодорхойлдог. Хэрэв түлхүүр нь тоон утгаар өгөгдсөн бол функцад шууд ашиглана. Харин түлхүүр нь тэмдэгт мөрөөр өгөгдвөл түүнийг эхлээд тоон утгаар илэрхийлэх шаардлагатай.
 
Түлхүүрийн тоо n-ээс их m тоог сонгоно. Хаяглалын зөрчилийг багасгахын тулд ''m'' анхны тоо байх шаардлагатай. Эндээс H функцыг
H(k) = k(mod M) гэж тодорхойлдог. Хэрэв түлхүүр нь тоон утгаар өгөгдсөн бол функцадфункцид шууд ашиглана. Харин түлхүүр нь тэмдэгт мөрөөр өгөгдвөл түүнийг эхлээд тоон утгаар илэрхийлэх шаардлагатай.
 
===ХаягынХаягийн зөрчлийг зохицуулах аргагуударгууд===
 
Түлхүүрийг дээрх функцээр хүснэгтийн хаягруухаяг уруу хувиргах үед ижил хаягаар тодорхойлогдсон түлхүүрүүдийг зохицуулах асуудал яригдана. Хамгийн энгийн арга бол хүснэгтийн хаяг бүртбүрд жагсаалт ашиглах ба цгцаг хаягаар тодорхойлогдох түлхүүрийг агуулах болно. Өөрөөр хэлбэл ''m'' хэмжээтэй хүснэгтийн хувьд ''m'' салангид жагсаалт ашиглагдах юм.
 
===Хаягын зөрчлийг зохицуулах аргагууд===
Түлхүүрийг дээрх функцээр хүснэгтийн хаягруу хувиргах үед ижил хаягаар тодорхойлогдсон түлхүүрүүдийг зохицуулах асуудал яригдана. Хамгийн энгийн арга бол хүснэгтийн хаяг бүрт жагсаалт ашиглах ба цг хаягаар тодорхойлогдох түлхүүрийг агуулах болно. Өөрөөр хэлбэл m хэмжээтэй хүснэгтийн хувьд m салангид жагсаалт ашиглагдах юм.
 
 
 
===Зөрчил===
Өөр шинэ хосын хэш хүснэгтийн харгалзах үүрэнд өөр хос байвал зөрчил(collision) үүснэ.
 
Өөр шинэ хосын хэш хүснэгтийн харгалзах үүрэнд өөр хос байвал [[Зөрчил (компьютер)|зөрчил(collision)]] үүснэ.
 
===Халилт===
 
Харгалзах хүснэгтийн үүр дүүрэн бол халилт(overflow) үүснэ.