3- mavzu. Xesh jadval va xesh funksiyalar. Xesh funksiyalarga misol

4) Ideal xeshlash

Ideal xesh-funksiya deb shunday funksiyaga aytiladiki, u kalitlarning S naborining har bir kalitini butun sonlar to’plamiga kolliziyalarsiz akslantiradi. Matematik terminlar bilan aytilsa bu in’ektiv akslantirishdir.
Tafsifi:

1. h(k):U→[m] funksiya S€U uchun ideal xesh-funksiya deyiladi, agar u Sda in’ektiv bo’lsa.

2. h(k):U→[m] funksiya S€U uchun minimal xesh-funksiya deyiladi, agar u ideal xesh-funksiya bo’lib , hamda m=n=|S| bo’lsa.
3. Butun k≥1 uchun h(k):U→[m] funksiya S€U uchun k-ideal xesh–funksiya deyiladi, agar har bir j ϵ[m] uchun
│{x ϵ S}|h(x)=j}│≤k tengcizlik o’rinli bo’lsa.
Ideal xeshlash kalit xaqida xech qanday axborot saqlab qolmasdan unga takrorlanmas identifikatorlar berish zaruriyati paydo bo’lganda ishlatiladi.
Faraz qilaylik, hajmi kichik tezkor xotira mavjud va unda xeshlar saqlanadi. Xeshlar esa katta hajmli sekin xotiradagi malumotlar bilan bog’langan. Ushbu vaziyat ideal xeshlash ishlatishiga yaqqol misol bo’la oladi. Bundan tashqari, ideal xeshlash usuli grafni asosiy xotiraga joylashning imkoni bo’lmagan hollarda graf bilan ishlaydigan algoritmlarning tezkorligini oshirish uchun xam qo’llaniladi.


5) Universal xeshlash

Universal xeshlash deb shunday xeshlashga aytiladiki, unda bitta konkret xesh funksiya emas, balki berilgan to’plamdan tasodifiy algoritm asosida tanlab olingan xesh-funksiya ishlatiladi. Universal xeshlash odatda kolliziyalar sonining kichik bo’lishini ta’minlaydi.

Tavsifi:
Faraz qilaylik, kalitlarning U fazosidan olingan kalitlarni [m] sonlarga akslantirish kerak bo’lsin. Algoritm kirishiga n o’lchamli SU ma’lumotlar nabori berilgan. Xeshlashda kolliziyalar soni minimal bo’lishi talab qilinadi. Bunga ilgaridan belgilab qo’yilgan konkret bir xesh-funksiya bilan erishish mumkin emas. Bu muammo universal H={h:Uà[m]} oila deb ataladigan xesh-funksiyalarning to’plamidan xesh-funksiyani tasodifiy ravishda tanlab olish bilan hal qilinadi.