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

Xesh-funksiya turlari

1)Bo’lish amaliga asoslangan xesh-funksiyalar

a) Mumkin bo’lgan barcha “xesh”lar  soniga bo’lishda hosil bo’ladigan qoldiqni  “xesh-kod” sifatida olish.

Kirishdagi ma’lumot qiymati M soniga bo’linib, hosil bo’gan qoldiq “xesh-funksiya” qiymati  (“xesh”) deb olinadi, ya’ni h(k)=k mod M, bu yerda M-barcha mumkin bo’lgan  “xesh”lar soni. Bu holda ko’rinib turibdiki, M juft bo’lib, k ham juft bo’lsa, xesh-funksiya qiymati juft bo’ladi. M juft bo’lib, k toq bo’lsa, funksiya qiymati toq bo’ladi.  Kompyuter sanoq tizimining asosini  M soni sifatida olish tavsiya qilinmaydi, chunki bunda xesh-kod k soni yozuvi o’ng tomonida joylashgan  bir necha raqamlardangina bog’liq bo’lib qoladi  va natijada  kolliziyalar soni juda katta bo’ladi. Amaliyotda, odatda, M sifatida oddiy natural son olinadi va bu ko’p hollarda batamom qoniqarli tanlov hisoblanadi.

b) Xesh-kod sifatida xosil bo’ladigan ko’phad koeffitsientlari to’plamini olish.

Xesh-funksiyada  kiritilgan ma’lumotlarni moduli 2 bo’lgan ko’phadga bo’lish amali bajariladi. Bu usulda M soni 2 ning  biron darajasiga teng  bo’lishi kerak. Kalitlar (K=k_n-1k_n-2…k₀) ko’phad   shakliga  keltiriladi.  Bu  holda  xesh-kod sifatida K ni ilgaridan tanlab olingan m-darajali  P ko’phadga bo’lishda qoldiq sifatida  hosil bo’lgan ko’phadning  koeffitsientlarining qiymatlari olinadi:

 K(x) mod P(x)=h_m-1x^m-1+…+h₁x+h₀

h(x)=h_m-1h_m-2…h₁h₀.

Bu usul P(x) ko’phad to’g’ri tanlanganda deyarli bir xil kalitlar o’rtasida kolliziyalar bo’lmasligini ta’minlaydi.