Хэш хүснэгт: Засвар хоорондын ялгаа
No edit summary |
|||
Мөр 27: | Мөр 27: | ||
[[Ангилал:Өгөгдлийн бүтэц]] |
[[Ангилал:Өгөгдлийн бүтэц]] |
||
[[Ангилал:Хэш| ]] |
10:59, 13 Гуравдугаар сар 2016-ий байдлаарх засвар
![](http://upload.wikimedia.org/wikipedia/commons/thumb/7/7d/Hash_table_3_1_1_0_1_0_0_SP.svg/315px-Hash_table_3_1_1_0_1_0_0_SP.svg.png)
Хайлтын харьцуулалтын туслламжтайгаар гүйцэтгэж байсан өмнөх аргуудаас ялгаатай нэг арга бол хеш хаяглалт юм. Энэ хайлтын арга нь түлхүүр утганд арифметик үйлдлээр хувиргалт хийн өгөгдөл байрлах хүснэгтийн хаягийг гарган авч шууд ханддаг.
Хэрэв бидэнд n ширхэг ялгаатай түлхүүр утгууд 1-ээс n-ийн хооронд өгөгдвөл к утгатай түлхүүрийн өгөгдлийн массивын к дугаар элементээс шууд авах боломжтой байдаг. Тэгвэл hash хаяглал нь түлхүүрийн утга тодорхой биш, ерөнхий тохиолдолд энгийн энэ арга дээр үндэслэгддэг.
Hash хаяглалын тусламжтайгаар хийх хайлтын эхний алхам бол хайх түлхүүрийн утгыг хүснэгтийн хаяг уруу хувиргах үйлдэл юм. Энэ үйлдэл hash функцынээр хийгддэг. Зарчмын хувьд, hash функц нь ялгаатай түлхүүр бүрийг ялгаатай хаягт хувиргах ёстой боловч ингэж бүрэн төгс тодорхойлох хэш функц байдаггүй. Иймээс 2 ба түүнээс олон ялгаатай түлхүүрүүд хүснэгтийн ижил хаягаар тодорхойлогдох тохиолдол гардаг. Ийм түлхүүрүүдийн зөрчлийг зохицуулах үйлдэл нь хайлтын хоёрдох алхам болдог ба үүнийг жагсаалт ашиглан зохицуулж болдог. Энэ арга нь хэдэн түлхүүр гарч ирэхийг урьдчилан мэдэхгүй тохиолдолд динамикаар зохицуулахад илүү тохиромжтой юм. Үүнээс гадна массив ашиглан шийдэх зарим аргууд байдаг.
Hash хаяглалыг хугацаа ба зай хэмнэсэн сайн жишээний нэг гэж хэлж болно. Хэрэв санах ойн хязгаарлалт байхгүй бол түлхүүр утгагд санах ойн хязгаарыг ашигласанаар санах ой руу зөвхөн нэг удаагын хандалтаар хайлтыг гүйцэтгэх болно. Хэрэв хугацааны хязгаарлалтгүй бол хүрэлцээт хамгийн бага санах ойн хувьд энгийн дараалан хийх аргыг ашиглаж болно. Тэгвэл hash хаяглал нь энэ 2 туйлыг тэнцүүлэн хугацаа ба зайг ухаалгаар ашигладаг.
Хэш функц
Эхний алхамд түлхүүрийг хүснэгтийн хаягруу хувиргах hash функц тодорхойлох ёстой. Энэ процесс нь санамсаргүй тоо үүсгэхтэй төстэй арифметик үйлдэл юм. Өөрөөр хэлбэл к түлхүүрийн олонлогыг [0,m-1] гэсэн (m хүснэгтийн хэмжээ) мужийн хоорондох бүхэл тоонуудруу хувиргах H:K->M функцыг тодорхойлох болно. H функцыг тодорхойлоход 2 үндсэн шалгуур баримтлах шаардлагатай. Үүний эхний шаардлага нь Н функц маш хурдан, хялбар байх ёстой. 2дахь шаардлага нь Н функцээр хаяглагдах түлхүүрүүд хамгийн бага зөрчилтэйгээр хүснэгтийн m байрлалд тархсан байх шаардлагатай. Гэвч бодит байдал дээр түлхүүрүүд болон хаягуудыг урьдчилан мэдэхгүй тохиолдолд 2 дахь шаардлагыг төгс хангаж чаддаггүй. Иймд бид түгээмэл ашиглагддаг хэш функцийг авч үзье.
Хуваах арга
Түлхүүрийн тоо n-ээс их m тоог сонгоно. Хаяглалын зөрчилийг багасгахын тулд m анхны тоо байх шаардлагатай. Эндээс H функцыг H(k) = k(mod M) гэж тодорхойлдог. Хэрэв түлхүүр нь тоон утгаар өгөгдсөн бол функцид шууд ашиглана. Харин түлхүүр нь тэмдэгт мөрөөр өгөгдвөл түүнийг эхлээд тоон утгаар илэрхийлэх шаардлагатай.
Хаягийн зөрчлийг зохицуулах аргууд
Түлхүүрийг дээрх функцээр хүснэгтийн хаяг уруу хувиргах үед ижил хаягаар тодорхойлогдсон түлхүүрүүдийг зохицуулах асуудал яригдана. Хамгийн энгийн арга бол хүснэгтийн хаяг бүрд жагсаалт ашиглах ба цаг хаягаар тодорхойлогдох түлхүүрийг агуулах болно. Өөрөөр хэлбэл m хэмжээтэй хүснэгтийн хувьд m салангид жагсаалт ашиглагдах юм.
Зөрчил
Өөр шинэ хосын хэш хүснэгтийн харгалзах үүрэнд өөр хос байвал зөрчил(collision) үүснэ.
Халилт
Харгалзах хүснэгтийн үүр дүүрэн бол халилт(overflow) үүснэ.