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

Xesh-jadval - bu assotsiativ massiv interfeysini amalga oshiradigan ma’lumotlar tuzilmasi, ya'ni har bir elementi juftliklar (kalit, qiymat)ni saqlovchi tuzilma bo’lib, unda uchta operatsiyani bajarish imkoni mavjud: yangi juftlikni qo'shish, qidirish va kalit yordamida juftlikni o’chrish.
Turli xil tarkibga ega bo’lib, xesh –kodlari bir xil bo’lgan massivlar to’plami kolliziya deyiladi . Kolliziyalar yuzaga kelish ehtimoli tanlangan xesh-funksiyaning sifatini baholashda muhim ro’l o’ynaydi. Bu ehtimol miqdori qanchalik kichik bo’lsa, tanlangan xesh-funksiya shunchalik yaxshi bo’ladi.


Xesh-funksiya xossalari
Xeshlash algoritmlarining xossalari turlicha bo’lishi mumkin: masalan, razryadlilik, hisoblash murakkabligi, kriptomustahkamlik va hokozo. Boshqacha aytganda, ba’zi xesh-algoritmlarning asosiy xususyati unda ishlatilayotgan razryadlar soni bilan, ba’zilariniki hisoblashning murakkablik darajasi bilan bog’liq bo’ladi. Xesh-funksiya tanlashda yechilayotgan masalaning o’ziga xos xususiyatlari hisobga olinadi.
“Yaxshi” xesh-funksiya ikki xossaga ega bo’lishi kerak:
1) yuqori hisoblash tezligi;
2) kam miqdordagi “kolliziyalar”.
Quyidagi belgilashlarni olamiz:


K – “kalitlar” (kiritiladigan ma’lumotlar) soni;

h(k) - M dan katta bo’lmagan sondagi turli xil qiymatlarga ega bo’lgan xesh-funksiya, ya’ni ixtiyoriy k ϵ (0;K):h(k)
“Yomon” xesh-funksiyaga misol keltiramiz: M=1000 bo’lib, o’n raqamli K natural songa uning kvadratiga teng yigirma raqamli son yozuvining o’rtasidan olingan uchta raqamdan iborat ketma-ketlikni mos qo’yuvchi funksiya. Bir qarashda bu funksiya uchun xesh-kodlar “000” va “999” lar o’rtasida tekis taqsimlanadi deb o’ylash mumkin. Lekin, agar berilgan son yozuvida chapda yoki o’ngdagi nollar soni juda katta bo’lgan hollar uchun tekis taqsimot buziladi.


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.