Ma’lumotlarni xeshlash algoritmlari. Xesh jadval va xesh funksiyalari

---

5-AMALIY ISH 
Ma’lumotlarni xeshlash algoritmlari. Xesh jadval va xesh 
funksiyalari. 
Ishning maqsadi: 
Xeshlash algoritmlarini, xesh jadvalni tuzishni o’rganish va amalda 
qo’llash. 
Ish tartibi: 
- 
Nazariy qismdagi ma’lumotlarni o’rganib chiqish. 
- 
Amaliy qismda keltirilgan amaliyot ishini bajarish. 
- 
Topshiriqlar bo’limida keltirilgan masalalarni yechish 
- 
Amalga oshirilgan ish bo’yicha hisobot tayyorlash va topshirish 
NAZARIY QISM VA AMALIY QISM 
XESHLASH TUSHUNCHASI 
Katta hajmli ma’lumotlarnda paydo bo’ladigan muammo bu qidirish. Agar ma’lumotlar tartibsiz 
joylashgan bo’lsa chiziqli qidirish qo’llaniladi, effektivligi O(n/2). Agar massiv tartiblangan bo’lsa 
ikkilik qidirish qo’llanilishi mumkin, effektivligi O(log
2
n). 
Tartiblangan ma’lumotlar va ikkilik daraxt bilan ishlashda qo’yish, o’chirish amallari qiyinchilik 
keltirib chiqaradi. Bunda daraxt balansni yo’qotadi keyin uni yana balansga olish kelishga to’g’ri 
keladi.
Bu holatlarda xeshlash algoritmi ishlatiladi. Bunda massiv ma’lumotlarini anglatuvchi kalit 
yaratiladi va uning asosida ma’lumotlar jadvalga yoziladi. Bu jadval xesh jadval deb ataladi. Kalit 
i=h(key) funksiyasi orqali aniqlanadi. Bu funksiya xesh-funksiya deb ataladi. Xeshlash algoritmi 
qidirilayotgan elementni uning kaliti bo’yicha xesh-jadvalda joylashuvini aniqlaydi. 
Xeshlash bu katta ko’plikni kichik ko’rinish saqlash usuli. 
Masalan, lug’at, bunda ma’lumotlar alifbo tartibida joylashadi, bu yerda alifbo kalit deb qabul 
qilinadi.
Dasturlashda xeshlash termini 1967 yili Xellerman tarafidan kiritilgan. 
Haqiqatda xeshlash bu ma’lumotlarni kalitlari bo’yicha tez qidirish uchun adreslashning maxsus 
usuli. 
Agar to’plam N ta elementdan iborat bo’lsa, uni 2
N
ta har xil ko’pliklarga ajratish mumkin. 
XESH FUNKSIYA VA XESH-JADVAL 
Funksiya, kichik to’plamlar xosiyati belgilaydi, ma’lumotlar elementi kalitini jadval indeksiga (xesh-
jadval) shakllantiradi. Bu funksiya xesh-funksiya deb ataladi: 
i = h(key) 
key – kalit, i – jadval indeksi. 

---

Funksiya natijasi bo’yicha bir necha kalit qiymatlari bir xil i indeksini berishi mumkin. Bu holat 
xeshlashda kolliziya deb ataladi.
Yaxshi funksiya bu kolliziyani minimallashtiradigan va jadval bo’yicha ma’lumotlarni tengday 
tarqatadigan funksiya bo’lib hisoblanadi. 
Mukammal xesh-funksiya bu umuman kolliziya keltirib chiqarmaydigan funksiya.
Xesh-jadval bu oddiy massiv bo’lib, standart emas ko’rinishda adreslanadi. 
Xeshlash usullari har xil bo’lib ular h(key) funksiyalari va konfliktlarni yechish usullari bilan farq 
qiladi.
Masalan, 
m uzunlikdagi simvolli n ta qator berilgan. Qatorlardan ikkitasini tengligina q marta 
tekshirish kerak. Buning uchun O(q * n * m) murakkablikda amal bajariladi. Buning o’rniga biz 
barcha qatorlar xeshlash, saqlash keyin ikki qator solishtirish o’rniga ikki sonni solishtirishimiz 
mumkin.
Xeshlanadigan obyektlar har xil bo’lishi mumkin. Simvolli qatorlar, rasm, graf, bitli fayllar. 
Xesh funksiya faqat bir tarafga ishlaydi, ya’ni xeshlangan kalitni qayta tiklab bo’lmaydi. 
XESH-FUNKSIYA METODLARI 
Bo’lish usuli.
Dastlabki ma’lumot bu biror bir 
key butun kalit va m o’lchamli jadval. Bu funksiya 
natijasi jadval o’lchamini kalit bo’lishdan qolgan qoldiq.

---