12-mavzu. Xeshlash va xesh jadvallar Reja

         Xeshlash 

Joylashtirish  usuli  (xeshlashtirish)  ma’lumotlar  tuzilmasida  element 

joylashgan  o’rinni  tez  aniqlashga  yo’naltirilgan  usuldir.  Joylashtirish  usulida 

ma’lumotlar oddiy massiv sifatida ifodalangan bo’ladi. Ushbu usulda ma’lumotlar 

kalitlari N akslantirish yordamida  massiv indekslariga akslantiriladi. SHu sababli 

mazkur akslantirish «kalitlarni akslantirish» deb nomlanadi.  

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.