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

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.