Хэш хүснэгт
From Wikipedia, the free encyclopedia
Хайлтын харьцуулалтын туслламжтайгаар гүйцэтгэж байсан өмнөх аргуудаас ялгаатай нэг арга бол хеш хаяглалт юм. Энэ хайлтын арга нь түлхүүр утганд арифметик үйлдлээр хувиргалт хийн өгөгдөл байрлах хүснэгтийн хаягийг гарган авч шууд ханддаг.
Хэрэв бидэнд n ширхэг ялгаатай түлхүүр утгууд 1-ээс n-ийн хооронд өгөгдвөл к утгатай түлхүүрийн өгөгдлийн массивын к дугаар элементээс шууд авах боломжтой байдаг. Тэгвэл hash хаяглал нь түлхүүрийн утга тодорхой биш, ерөнхий тохиолдолд энгийн энэ арга дээр үндэслэгддэг.
Hash хаяглалын тусламжтайгаар хийх хайлтын эхний алхам бол хайх түлхүүрийн утгыг хүснэгтийн хаяг уруу хувиргах үйлдэл юм. Энэ үйлдэл hash функцынээр хийгддэг. Зарчмын хувьд, hash функц нь ялгаатай түлхүүр бүрийг ялгаатай хаягт хувиргах ёстой боловч ингэж бүрэн төгс тодорхойлох хэш функц байдаггүй. Иймээс 2 ба түүнээс олон ялгаатай түлхүүрүүд хүснэгтийн ижил хаягаар тодорхойлогдох тохиолдол гардаг. Ийм түлхүүрүүдийн зөрчлийг зохицуулах үйлдэл нь хайлтын хоёрдох алхам болдог ба үүнийг жагсаалт ашиглан зохицуулж болдог. Энэ арга нь хэдэн түлхүүр гарч ирэхийг урьдчилан мэдэхгүй тохиолдолд динамикаар зохицуулахад илүү тохиромжтой юм. Үүнээс гадна массив ашиглан шийдэх зарим аргууд байдаг.
Hash хаяглалыг хугацаа ба зай хэмнэсэн сайн жишээний нэг гэж хэлж болно. Хэрэв санах ойн хязгаарлалт байхгүй бол түлхүүр утгагд санах ойн хязгаарыг ашигласанаар санах ой руу зөвхөн нэг удаагын хандалтаар хайлтыг гүйцэтгэх болно. Хэрэв хугацааны хязгаарлалтгүй бол хүрэлцээт хамгийн бага санах ойн хувьд энгийн дараалан хийх аргыг ашиглаж болно. Тэгвэл hash хаяглал нь энэ 2 туйлыг тэнцүүлэн хугацаа ба зайг ухаалгаар ашигладаг.