Jump to content

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

засварлах хураангуй байхгүй
No edit summary
No edit summary
Хэрэв бидэнд n ширхэг ялгаатай түлхүүр утгууд 1-ээс n-ийн хооронд өгөгдвөл к утгатай түлхүүрийн өгөгдлийн массивын к дугаар элементээс шууд авах боломжтой байдаг. Тэгвэл hash хаяглал нь түлхүүрийн утга тодорхой биш, ерөнхий тохиолдолд энгийн энэ арга дээр үндэслэгддэг.
 
Hash хаяглалын тусламжтайгаар хийх хайлтын эхний алхам бол хайх түлхүүрийн утгыг хүснэгтийн хаяг уруу хувиргах үйлдэл юм. Энэ үйлдэл hash функцынээр хийгддэг. Зарчмын хувьд, hash функц нь ялгаатай түлхүүр бүрийг ялгаатай хаягт хувиргах ёстой боловч ингэж бүрэн төгс тодорхойлох [[хэш функц]] байдаггүй. Иймээс 2 ба түүнээс олон ялгаатай түлхүүрүүд хүснэгтийн ижил хаягаар тодорхойлогдох тохиолдол гардаг. Ийм түлхүүрүүдийн зөрчлийг зохицуулах үйлдэл нь хайлтын хоёрдох алхам болдог ба үүнийг жагсаалт ашиглан зохицуулж болдог. Энэ арга нь хэдэн түлхүүр гарч ирэхийг урьдчилан мэдэхгүй тохиолдолд динамикаар зохицуулахад илүү тохиромжтой юм. Үүнээс гадна массив ашиглан шийдэх зарим аргууд байдаг.
 
Hash хаяглалыг хугацаа ба зай хэмнэсэн сайн жишээний нэг гэж хэлж болно. Хэрэв санах ойн хязгаарлалт байхгүй бол түлхүүр утгагд санах ойн хязгаарыг ашигласанаар санах ой руу зөвхөн нэг удаагын хандалтаар хайлтыг гүйцэтгэх болно. Хэрэв хугацааны хязгаарлалтгүй бол хүрэлцээт хамгийн бага санах ойн хувьд энгийн дараалан хийх аргыг ашиглаж болно. Тэгвэл hash хаяглал нь энэ 2 туйлыг тэнцүүлэн хугацаа ба зайг ухаалгаар ашигладаг.
==HashХэш функц==
Эхний алхамд түлхүүрийг хүснэгтийн хаягруу хувиргах hash функц тодорхойлох ёстой. Энэ процесс нь санамсаргүй тоо үүсгэхтэй төстэй арифметик үйлдэл юм. Өөрөөр хэлбэл к түлхүүрийн олонлогыг [0,m-1] гэсэн (m хүснэгтийн хэмжээ) мужийн хоорондох бүхэл тоонуудруу хувиргах H:K->M функцыг тодорхойлох болно.
H функцыг тодорхойлоход 2 үндсэн шалгуур баримтлах шаардлагатай. Үүний эхний шаардлага нь Н функц маш хурдан, хялбар байх ёстой. 2дахь шаардлага нь Н функцээр хаяглагдах түлхүүрүүд хамгийн бага зөрчилтэйгээр хүснэгтийн m байрлалд дархсантархсан байх шаардлагатай. Гэвч бодит байдал дээр түлхүүрүүд болон хаягуудыг урьдчилан мэдэхгүй тохиолдолд 2 дахь шаардлагыг төгс хангаж чаддаггүй. Иймд бид түгээмэл ашиглагддаг [[Хэшхэш функц]]ийгфункцийг авч үзье.
 
===Хуваах арга===