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

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

Fan:Ma’lumotlar tuzulmasi va algoritmlar.

Bajardi:Mirzaodilov Ulug’bek

3- Mavzu. Xesh jadval va xesh funksiyalar. Xesh funksiyalarga misol.
Reja:

1. Xeshlash tushunchasi

2. Xesh-funksiya xossalari
3. Xesh-funksiya turlari
4. Kolliziyalar bilan kurashish usullari
5. Xesh funksiyalarning qo’llanishi

Kalit so’zlar: Xesh, xeshlash, xesh jadval, xesh funksiya, kolliziya.
"Xesh" so'zi ingliz tilidagi «hash» so’zidan olingan bo’lib, uning ma'nosi “shovqin” yoki “aralash” kabi ta'riflanadi. Aslida, bular atamaning haqiqiy ma'nosini to'liq ifodalaydi.
Odatda “xeshlash” – bu jarayon bo’lib, ingliz tilida - chopish, aralashtirish kabi ma’nolarni anglatadi.
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.