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

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.