Ma’lumotlar tuzilmasi va algoritmlar

Акслантириш функциясини танлаш

Ўз-ўзидан маълумки, акслантиришнинг ихтиёрий яхши функцияси калитларни берилган индекслар оралиғига иложи борича тенг тақсимлайди. Агарда ушбу талаб ўринли бўлса, у ҳолда қўшимча шарт ва чекланишлар бўлмайди. Агарда акслантириш мутлақо тасодифий бўлса яна ҳам яхшироқ

бўлади. Мазкур усулга “майдалаш” (хешлаштириш), яъни аргументни бўлаклаш деб аталади. Н функция эса “жойлаштириш функцияси” деб аталади. Равшанки, Н функция иложи борича самарали хисобланиши лозим, яъни унча кўп бўлмаган асосий арифметик амаллардан ташкил топган бўлиши лозим.
Фараз қилайлик, k калит тартиб рақамини барча мумкин бўлган калитлар тўпламида ифодаловчи ORD(k) функция берилган бўлсин. Бундан ташқари, i массив индекси 0 ... N — 1 оралиқда жойлашган деб фараз қиламиз, бу ерда N — массив ўлчами. Бундай ҳолда “жойлаштириш функцияси” сифатида қуйидаги функцияни олиш мумкин:
H(k) = ORD(k) MOD N
Агарда “жойлаштириш функцияси” юқоридаги каби аниқланадиган бўлса, у ҳолда калит қийматлари индекслар ўзгариши оралиғига текис тақсимланади. Шу сабабли, калитларни акслантириш амалга оширилаётган вақтда кўпинча уни асос қилиб олишади. Бундан ташқари, агар масив узунлиги N иккининг қандайдир даражасига тенг бўлса, у ҳолда функция самарали ҳисобланади. Лекин, агар калит харфлар кетма-кетлигидан ташкил топган бўлса, у ҳолда айнан бундай функциядан воз кечишга тўғри келади. Сабаби, бундай ҳолатда барча калитлар тенгэхтимолликга эга деб қараш нотўғри бўлади. Натижада, фақатгина бир неча белгилар билан фарқланувчи сўзларни битта индексга акслантириш эхтимоллиги юқори бўлади, бу эса калитларни нотекис тақсимланишига олиб келиши мумкин. Шу сабабли, амалий масаллар ҳал қилинаётганда N сифатида туб сонларни олиш тавсия этилади.