Хэш хүснэгт: Засвар хоорондын ялгаа
Content deleted Content added
No edit summary |
No edit summary |
||
Мөр 1:
{{distinguish|
{{Огноо | year=2013 | month=1}}
{{Infobox data structure
|name=Hash table
Line 28 ⟶ 27:
|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 функц нь ялгаатай түлхүүр бүрийг ялгаатай хаягт хувиргах ёстой боловч ингэж бүрэн төгс тодорхойлох hash функц байддаггүй. Иймээс 2 ба түүнээс олон ялгаатай түлхүүрүүд хүснэгтийн ижил хаягаар тодорхойлогдох тохиолдол гардаг. Ийм түлхүүрүүдийн зөрчилийг зохицуулах үйлдэл нь хайлтын хоёрдох алхам болдог ба үүнийг жагсаалт ашиглан зохицуулж болдог. Энэ арга нь хэдэн түлхүүр гарч ирэхийг урьдчилан мэдэхгүй тохиолдолд динамикаар зохицуулахад илүү тохиромжтой юм. Үүнээс гадна массив ашиглан шийдэх зарим аргууд байдаг.
Hash хаяглалыг хугацаа ба зай хэмнэсэн сайн жишээний нэг гэж хэлж болно. Хэрэв санах ойн хязгаарлалт байхгүй бол түлхүүр утгагд санах ойн хязгаарыг ашигласанаар санах ой руу зөвхөн нэг удаагын хандалтаар хайлтыг гүйцэтгэх болно. Хэрэв хугацааны хязгаарлалтгүй бол хүрэлцээт хамгийн бага санах ойн хувьд энгийн дараалан хийх аргыг ашиглаж болно. Тэгвэл hash хаяглал нь энэ 2 туйлыг тэнцүүлэн хугацаа ба зайг ухаалгаар ашигладаг.
==Hash функц==
Эхний алхамд түлхүүрийг хүснэгтийн хаягруу хувиргах hash функц тодорхойлох ёстой. Энэ процесс нь санамсаргүй тоо үүсгэхтэй төстэй арифметик үйлдэл юм. Өөрөөр хэлбэл к түлхүүрийн олонлогыг [0,m-1] гэсэн (m хүснэгтийн хэмжээ) мужийн хоорондох бүхэл тоонуудруу хувиргах H:K->M функцыг тодорхойлох болно.
H функцыг тодорхойлоход 2 үндсэн шалгуур баримтлах шаардлагатай. Үүний эхний шаардлага нь Н функц маш хурдан, хялбар байх ёстой. 2дахь шаардлага нь Н функцээр хаяглагдах түлхүүрүүд хамгийн бага зөрчилтэйгээр хүснэгтийн m байрлалд дархсан байх шаардлагатай. Гэвч бодит байдал дээр түлхүүрүүд болон хаягуудыг урьдчилан мэдэхгүй тохиолдолд 2 дахь шаардлагыг төгс хангаж чаддаггүй. Иймд бид түгээмэл ашиглагддаг
===Хуваах арга===
Түлхүүрийн тоо n-ээс их m тоог сонгоно. Хаяглалын зөрчилийг багасгахын тулд m анхны тоо байх шаардлагатай. Эндээс H функцыг ▼
H(k) = k(mod M) гэж тодорхойлдог. Хэрэв түлхүүр нь тоон утгаар өгөгдсөн бол функцад шууд ашиглана. Харин түлхүүр нь тэмдэгт мөрөөр өгөгдвөл түүнийг эхлээд тоон утгаар илэрхийлэх шаардлагатай.▼
▲Түлхүүрийн тоо n-ээс их m тоог сонгоно. Хаяглалын зөрчилийг багасгахын тулд ''m'' анхны тоо байх шаардлагатай. Эндээс H функцыг
▲H(k) = k(mod M) гэж тодорхойлдог. Хэрэв түлхүүр нь тоон утгаар өгөгдсөн бол
Түлхүүрийг дээрх функцээр хүснэгтийн
▲===Хаягын зөрчлийг зохицуулах аргагууд===
▲Түлхүүрийг дээрх функцээр хүснэгтийн хаягруу хувиргах үед ижил хаягаар тодорхойлогдсон түлхүүрүүдийг зохицуулах асуудал яригдана. Хамгийн энгийн арга бол хүснэгтийн хаяг бүрт жагсаалт ашиглах ба цг хаягаар тодорхойлогдох түлхүүрийг агуулах болно. Өөрөөр хэлбэл m хэмжээтэй хүснэгтийн хувьд m салангид жагсаалт ашиглагдах юм.
===Зөрчил===
Өөр шинэ хосын хэш хүснэгтийн харгалзах үүрэнд өөр хос байвал зөрчил(collision) үүснэ.▼
▲
===Халилт===
| |||