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

Xeshlash - bu ma’lumotlarning kirishdagi massivini determenistik  algoritm bo’yicha chekli uzunlikdagi chiqish satriga aylantirishdir. Boshqacha aytganda, xeshlash - bu shunday jarayonki, uning kirishidagi massiv maxsus algoritm asosida chiqishda bitlar ketma-ketligiga almashtiriladi.  Bunday almashtirish xesh-funksiya  yoki o’rash funksiyasi deyiladi.  Almashtirish natijasi esa xesh yoki xesh-kod yoki xabarlar qisqa izohi (o’rami)  deb ataladi. Ikki massiv yoki satrning xesh-kodlari har xil bo’lishidan  bu massivlar bir xil emas degan xulosa qilish mumkin. Xesh-kodlari bir xil bo’lishi esa massivlar bir xil bo’lishi muminligini ( ehtimoli borligini) bildiradi. 

Xeshlash qo’llaniladigan holatlarga misollar:

·  har bir elementi o’zoro biriktirilgan ikki qismdan iborat massivlar (masalan, lug’at shaklidagi massiv)  hosil qilishda;

· ma’lumotlar to’plamida takrorlanuvchi elementlarni izlash uchun;

· ma’lumotlar to’plami uchun o’ziga xos takrorlanmaydigan ism (identifikator) topish uchun;

· ma’lumot saqlash yoki uzatishdagi tasodifiy yoki ataylab qilingan xatolarni aniqlash maqsadida  nazorat uchun  yig’indilarni  hisoblashda;

·  himoya tizimlarida parollarni saqlash uchun (bunda parol saqlanayotgan xotira sohasiga murojat paytida parolni bilib olish mumkin bo’lmaydi);

Ø  elektron imzoni ishlab chiqishda (amalda  xabarlarning o’zi emas ularning  xesh-shakli imzolanadi).

Umuman olganda, boshlang’ich ma’lumotlar va ularning xesh-kodlari  o’rtasida o’zoro bir qiymatli moslik yo’q. Chunki xesh-funksiyasi  qiymatlari soni kirish massivi variantlari sonidan kichik. Quyidagi jadvalda massivning turli variantlari va ularga mos nazorat yig’indilar keltirilgan (bunda xesh-funksiya qiymati massiv elementlari yig’indisidan iborat).

T.n.	Massiv variantlari	Xesh-kod(nazorat yig’indi)
1.	1;2	3
2.	2;1	3
3.	0;3	3
4.	3;0	3
5.	1;3	4

 Bu jadvaldan ko’rinadiki, massivning turli  variantlari bir xil xesh-kodga ega bo’lishi mumkin ekan.

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.