|
Калитларни акслантириш (жойлаштириш)
|
| bet | 4/8 | | Sana | 28.11.2023 | | Hajmi | 286,96 Kb. | | #107090 |
Bog'liq E8Dx1mrixWnPmQoCYHQYfPKK1zZswiBdQZ752NDVDemak:1-holda Калитларни акслантириш билан боғлиқ бўлган асосий муаммо бу калитларни қабул қилиши мумкин бўлган қийматлар тўпламини хотира адреси (массив индекслари) қабул қилиши мумкин бўлган тўпламдан анча кенглигидир.
Mисол . Фараз қилайлик, 1000 та одам бор. Ҳар бир одамни аниқлаш (идентификация қилиш) учун калит сифатида исмларини қарайлик.
Фараз қилайлик ҳар бир исм 16 тагача ҳарфдан ташкил топган бўлсин. Aгар алифбо 26 та харфдан иборат бўлса , бўлиши мумкин бўлган калитлар тўплами 2616 та элeментдан иборат бўлади .Mana shu бўлиши мумкин бўлган калит қийматлари тўпламини 103 та индексли массивга акслантириш лозим бўлади.
Юқоридаги мисолдан кўриниб турибдики, Н функция ичига акслантирувчи акслантириш бўлади, яъни «кўпгина қиймат бир қийматга акслантирилади». - Юқоридаги мисолдан кўриниб турибдики, Н функция ичига акслантирувчи акслантириш бўлади, яъни «кўпгина қиймат бир қийматга акслантирилади».
Demak : Агар бирор бир калит берилган бўлса, у ҳолда қидирув амалининг 1- қадами - калит билан боғланган индексни ҳисоблаш, яъни h = H(k); 2- ва асосийси – текшириш бўлиб ҳисобланади, яъни бунда ҳақиқатдан ҳам h функция Т массивда (жадвалда) k калитли элементни идентификация қилаётгани текширилади.
Акслантириш функциясини танлаш
Tabiiyki, акслантиришнинг ихтиёрий яхши функцияси калитларни берилган индекслар оралиғига иложи борича тенг тақсимлайди.
Агар ушбу талаб ўринли бўлса, у ҳолда қўшимча шарт ва чекланишларga ham xojat qolmaydi.
Агар акслантириш мутлақо тасодифий бўлса, яна ҳам яхшироқ бўлади.
Мазкур усулга “майдалаш” (хешлаштириш), яъни аргументни бўлаклаш деб аталади.
Н функция эса “жойлаштириш функцияси” деб аталади.
Н функция иложи борича самарали хисобланиши лозим, яъни унча кўп бўлмаган асосий арифметик амаллардан ташкил топган бўлиши лозим.
Фараз қилайлик, k калит тартиб рақамини барча мумкин бўлган калитлар тўпламида ифодаловчи ORD(k) функция берилган бўлсин. - Фараз қилайлик, k калит тартиб рақамини барча мумкин бўлган калитлар тўпламида ифодаловчи ORD(k) функция берилган бўлсин.
|
| |
