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.