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

2) Xeshlashning mul’tiplikativ sxemasi.

Bu usul w coni bilan o’zaro tub bo’lgan A butun sonni tanlashdan iborat (w-mashina so’zida joylanishi mumkin bo’lgan eng kata butun son; IBM PC komp’yuterlar uchun w=2³²). Xesh-funksiya quyidagi ko’rinishda olinadi:

h(K)=[M[K*A/w]].

Bu holda, ikkilik sanoq tizimidagi kompyuterga, M soni 2 ning biron darajasiga teng va h(K) esa A*K ko’paytmaning o’ng yarmidagi kata nomerli bitlardan iborat bo’ladi.

3)O’zgaruvchan uzunlikdagi satrlarni xeshlash.

Yuqorida tavsiflangan usullar kalitlar bir necha so’zlardan tarkib topgan hollar  hamda kalitlar uzunligi o’zgaruvchan bo’lgan xollar uchun ham o’rinli. Misol uchun so’zlarni w  modul bo’yicha qo’shish yoki “istisno qiluvchi yoki“ amali yordamida bittaga birlashtirish mumkin.  Shunday tamoyil asosida ishlaydigan algoritmlardan biri Pirson xesh-funksiyasidir. Pirson xeshlashi – bu Pirson tomonidan 8-bitli registrlarga ega bo’lgan protsessorlar uchun taklif qilgan algoritm bo’lib, uning vazifasi o’zgaruvchan uzunlikdagi satrlar uchun xesh-kodni yuqori tezlik bilan hisoblashdir.

Xesh-funksiya kirishiga har biri bir baytli n ta simvoldan iborat W so’z beriladi va chiqishida 0 dan 255 gacha diapozondagi  qiymat olinadi. Xesh-kod qiymati kirishdagi so’zning har bir simvolidan bog’liq bo’ladi.

Kirishda W satrni qabul qiluvchi va o’rin almashtirishlar jadvali Tni ishlatadigan algoritmni quyidagicha tasvirlash mumkin:

    h:=0

for each c in  W loor

   index: = h xor c

   h:= T[index]

end loop

return h

Bu algoritmning afzalliklari:

·   hisoblashlar oddiyligi;

·  kolliziyalar ehtimoli eng kata bo’lgan kiruvchi ma’lumotlarning mavjud emasligi;

·   o’zgartirib ideal xesh-funksiyalar olish imkoniyati.

Simvollardan (l ta) iborat K=x₁x₂…x_l kalitlarni xeshlashning muqobil usuli sifatida h(K)=(h₁(x₁)+h₂(x₂)+…+h_l(x_l)) mod M formula bo’yicha hisoblashlarni olish mumkin.