Kompyuter injiniringi ” fakulteti “dasturiy injiniring” kafedrasi

Акслантириш функциясини танлаш
Ўз-ўзидан маълумки, акслантиришнинг ихтиёрий яхши функцияси калитларни берилган индекслар оралиғига иложи борича тенг тақсимлайди. Агарда ушбу талаб ўринли бўлса, у ҳолда қўшимча шарт ва чекланишлар бўлмайди. Агарда акслантириш мутлақо тасодифий бўлса яна ҳам яхшироқ бўлади. Мазкур усулга “майдалаш” (хешлаштириш), яъни аргументни бўлаклаш деб аталади. Н функция эса “жойлаштириш функцияси” деб аталади. Равшанки, Н функция иложи борича самарали хисобланиши лозим, яъни унча кўп бўлмаган асосий арифметик амаллардан ташкил топган бўлиши лозим.
Фараз қилайлик, k калит тартиб рақамини барча мумкин бўлган калитлар тўпламида ифодаловчи ORD(k) функция берилган бўлсин. Бундан ташқари, i массив индекси 0 ... N — 1 оралиқда жойлашган деб фараз қиламиз, бу ерда N — массив ўлчами. Бундай ҳолда “жойлаштириш функцияси” сифатида қуйидаги функцияни олиш мумкин:
H(k) = ORD(k) MOD N
Агарда “жойлаштириш функцияси” юқоридаги каби аниқланадиган бўлса, у ҳолда калит қийматлари индекслар ўзгариши оралиғига текис тақсимланади. Шу сабабли, калитларни акслантириш амалга оширилаётган вақтда кўпинча уни асос қилиб олишади. Бундан ташқари, агар масив узунлиги N иккининг қандайдир даражасига тенг бўлса, у ҳолда функция самарали ҳисобланади. Лекин, агар калит харфлар кетма-кетлигидан ташкил топган бўлса, у ҳолда айнан бундай функциядан воз кечишга тўғри келади. Сабаби, бундай ҳолатда барча калитлар тенгэхтимолликга эга деб қараш нотўғри бўлади. Натижада, фақатгина бир неча белгилар билан фарқланувчи сўзларни битта индексга акслантириш эхтимоллиги юқори бўлади, бу эса калитларни нотекис тақсимланишига олиб келиши мумкин. Шу сабабли, амалий масаллар ҳал қилинаётганда N сифатида туб сонларни олиш тавсия этилади.
Зиддиятни ҳал қилиш алгоритмлари
Агар берилган калитга мос жадвал қатори керакли (қидирилаётган) элементга эга эмаслиги маълум бўлса, у ҳолда зиддият (“конфликт”) юзага келди дейилади. Бундай ҳолат, агарда бир неча элемент битта индексга акслантириладиган калитларга эга бўлса юзага келади. Бундай ҳолатда мазкур берилган калит орқали тўлиқ аниқланувчи индекс бўйича иккинчи уриниш амалга оширилади (Муқобил индекс шакллантириш орқали). Иккинчи индексни шакллантиришнинг бир қанча усуллари мавжуд. Энг содда йўлларидан бири бу – биринчи H(k) индекслари бир ҳил бўлган барча қаторни бир-бирига боғлаш, яъни боғланган рўйхат каби. Бундай усулга тўғридан-тўғри боғлаш (direct chaining) деб аталади. Ҳосил бўлган рўйхат элементлари асосий жадвалда жойлашиши ҳам жойлашмаслиги ҳам мумкин.
Бундай ҳолатда рўйхат элементлари жойлашган хотира тўлалик (тўлиб-тошиш, переполнение) соҳаси дейилади. Ушбу усулни камчилиги, иккиламчи рўйхатларни кузатиб бориш ҳамда зиддиятга борувчи элементлар рўйхати ҳар бир қаторида мурожаат учун жой ажратиш лозим бўлади.
Зиддиятни ҳал қилишнинг яна бир усулида эса берилган жадвални берилган қаторида керакли элемент мавжуд бўлмаса, токи керакли элемент топилгунча ёки бўш қаторга боргунча бошқа қаторларини кўриб чиқилади. Агар қараб чиқиш бўш қаторгача бориб етса, у ҳолда кўрсатилган калит берилган жадвалда йўқ деб ҳисобланади. Зиддиятни бундай ҳал қилиш усулига очиқ адресли деб аталади. Табиийки, ихтиёрий берилган калит учун индекслар кетма-кетлиги иккинчи уринишда бир ҳил бўлиши лозим. Бундай ҳолатда қараб (кўриб) чиқиш алгоритми қуйидаги схемада ишлайди:
h = H(k)
i = 0
repeat
if T(h) = k
then элемент топилди
else if T(h) = free
then элемент жадвалда йўқ
else {зиддият}
i := i + 1
h := H(k) + G(i)
endif
endif
until топилди, ёки жадвалда йўқ.


Назорат саволлари

1. 
   Калитларни алмаштириш нима?
   
2. 
   Акслантириш функцияси вазифаси нимадан иборат?
   
3. 
   Қандай ҳолатларда зиддият юзага келади?