12-mavzu. Xeshlash va xesh jadvallar Reja

    Ziddiyatni hal qilish algoritmlari 

Agar berilgan kalitga mos jadval qatori kerakli (qidirilayotgan) elementga ega 

emasligi ma’lum bo’lsa, u holda ziddiyat (“konflikt”) yuzaga keldi deyiladi. Bunday 

holat, agarda bir necha element bitta indeksga akslantiriladigan kalitlarga ega bo’lsa 

yuzaga  keladi.  Bunday  holatda  mazkur  berilgan  kalit  orqali  to’liq  aniqlanuvchi 

indeks  bo’yicha  ikkinchi  urinish  amalga  oshiriladi  (Muqobil  indeks  shakllantirish 

---

orqali). Ikkinchi indeksni shakllantirishning bir qancha usullari mavjud. Eng sodda 

yo’llaridan biri bu – birinchi H(k) indekslari bir hil bo’lgan barcha qatorni bir-biriga 

bog’lash, ya’ni bog’langan ro’yxat kabi. Bunday usulga to’g’ridan-to’g’ri bog’lash 

(direct  chaining)  deb  ataladi.  Hosil  bo’lgan  ro’yxat  elementlari  asosiy  jadvalda 

joylashishi ham joylashmasligi ham mumkin. 

Bunday  holatda  ro’yxat  elementlari  joylashgan  xotira  to’lalik  (to’lib-toshish, 

perepolnenie)  sohasi  deyiladi.  Ushbu  usulni  kamchiligi,  ikkilamchi  ro’yxatlarni 

kuzatib  borish  hamda  ziddiyatga  boruvchi  elementlar  ro’yxati  har  bir  qatorida 

murojaat uchun joy ajratish lozim bo’ladi.  

Ziddiyatni  hal  qilishning  yana  bir  usulida  esa  berilgan  jadvalni  berilgan 

qatorida  kerakli  element  mavjud  bo’lmasa,  toki  kerakli  element  topilguncha  yoki 

bo’sh  qatorga  borguncha  boshqa  qatorlarini  ko’rib  chiqiladi.  Agar  qarab  chiqish 

bo’sh qatorgacha borib yetsa, u holda ko’rsatilgan kalit berilgan jadvalda yo’q deb 

hisoblanadi. Ziddiyatni bunday hal qilish usuliga ochiq adresli deb ataladi. Tabiiyki, 

ixtiyoriy  berilgan  kalit  uchun  indekslar  ketma-ketligi  ikkinchi  urinishda  bir  hil 

bo’lishi lozim. Bunday holatda qarab (ko’rib) chiqish algoritmi quyidagi sxemada 

ishlaydi: 

h = H(k)  

i = 0 

repeat  

   if T(h)  =  k   

then  element topildi 

else if T(h) = free  

then element jadvalda yo’q 

else {ziddiyat} 

i := i + 1  

h := H(k) + G(i) 

endif 

   endif 

until  topildi, yoki jadvalda yo’q.