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.