2-mavzu. Xeshlash va xesh jadvallar Reja: To‘g‘ridan to‘g‘ri adreslash jadvallari. Xesh jadvallar

Elementni jadvalga qo’shishdan oldin uning adresi xesh-funktsiya orqali 
aniqlanadi: A = h(K), bu yerda K – kalit, A – jadvaldagi element adresi bo’lib,
0 

 A 

 N-1, shart o’rinli bo’ladi. 
Ushbu usuldan ko’pincha daraxtlarda hamda uni tadbiq etish muvoffaqiyat 
keltiruvchi masalalarda foydalaniladi. 
Kalitlarni akslantirish bilan bog’liq bo’lgan asosiy muammo bu kalitlarni qabul 
qilishi mumkin bo’lgan qiymatlar to’plamini xotira adresi (massiv indekslari) qabul 

---

qilishi mumkin bo’lgan to’plamdan ancha kengligidir. Quyidagicha misol ko’rib 
chiqaylik. Faraz qilaylik, 1000 ta odam bor. Har bir odamni aniqlash (identifikatsiya 
qilish) uchun kalit sifatida ismlarini qaraylik. Faraz qilaylik har bir ism 16 tagacha 
harfdan tashkil topgan bo’lsin. U holda biz bo’lishi mumkin bo’lgan kalit qiymatlari 
to’plamini (bu yerda bo’lishi mumkin bo’lgan kalitlar to’plami 26
16
ta elmentdan 
iborat bo’ladi, agar alifbo 26 ta xarfdan iborat bo’lsa), 10
3
ta indeksli massivga 
akslantirish lozim bo’ladi. Yuqoridagi misoldan ko’rinib turibdiki, N funktsiya 
ichiga akslantiruvchi akslantirish bo’ladi, ya’ni «ko’pgina qiymat bir qiymatga 
akslantiriladi». Agar biror bir kalit berilgan bo’lsa, u holda qidiruv amalining 
birinchi qadami - kalit bilan bog’langan indeksni hisoblash, ya’ni h = H(k), ikkinchi 
va asosiysi – tekshirish bo’lib hisoblanadi, ya’ni bunda haqiqatdan ham h funktsiya 
T massivda (jadvalda) k kalitli elementni identifikatsiya qilayotgani tekshiriladi. 
 
Akslantirish funktsiyasini tanlash 
O’z-o’zidan ma’lumki, akslantirishning ixtiyoriy yaxshi funktsiyasi kalitlarni 
berilgan indekslar oralig’iga iloji boricha teng taqsimlaydi. Agarda ushbu talab 
o’rinli bo’lsa, u holda qo’shimcha shart va cheklanishlar bo’lmaydi. Agarda 
akslantirish mutlaqo tasodifiy bo’lsa yana ham yaxshiroq bo’ladi. Mazkur usulga 
“maydalash” (xeshlashtirish), ya’ni argumentni bo’laklash deb ataladi. N funktsiya 
esa “joylashtirish funktsiyasi” deb ataladi. Ravshanki, N funktsiya iloji boricha 
samarali xisoblanishi lozim, ya’ni uncha ko’p bo’lmagan asosiy arifmetik 
amallardan tashkil topgan bo’lishi lozim.
Faraz qilaylik, k kalit tartib raqamini barcha mumkin bo’lgan kalitlar 
to’plamida ifodalovchi ORD(k) funktsiya berilgan bo’lsin. Bundan tashqari, i
massiv indeksi 0 ... N — 1 oraliqda joylashgan deb faraz qilamiz, bu yerda N — 
massiv o’lchami. Bunday holda “joylashtirish funktsiyasi” sifatida quyidagi 
funktsiyani olish mumkin: 
H(k) = ORD(k) MOD N 
Agarda “joylashtirish funktsiyasi” yuqoridagi kabi aniqlanadigan bo’lsa, u 
holda kalit qiymatlari indekslar o’zgarishi oralig’iga tekis taqsimlanadi. SHu 
sababli, kalitlarni akslantirish amalga oshirilayotgan vaqtda ko’pincha uni asos qilib 
olishadi. Bundan tashqari, agar masiv uzunligi N ikkining qandaydir darajasiga teng 
bo’lsa, u holda funktsiya samarali hisoblanadi. Lekin, agar kalit xarflar ketma-
ketligidan tashkil topgan bo’lsa, u holda aynan bunday funktsiyadan voz kechishga 
to’g’ri keladi. Sababi, bunday holatda barcha kalitlar tengextimollikga ega deb 
qarash noto’g’ri bo’ladi. Natijada, faqatgina bir necha belgilar bilan farqlanuvchi 
so’zlarni bitta indeksga akslantirish extimolligi yuqori bo’ladi, bu esa kalitlarni 
notekis taqsimlanishiga olib kelishi mumkin. SHu sababli, amaliy masallar hal 
qilinayotganda N sifatida tub sonlarni olish tavsiya etiladi.