15-mavzu. Xeshlash funksiyasini tanlash. Xeshlash algoritmlari. Ziddiyatlarni hal qilish usul va algoritmlari. Reja

Ziddiyatlarni hal qilish algoritmi
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 soda yo’llaridan biri bu– birinchi H(k) indekslari bir xil 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, переполнение) sohasi deyiladi. Ushbu usulni kamchiligi, ikkilamchi ro’yxatlarni kuzatib boorish hamda ziddiyatga boruvchi elementlar ro’yxati har bir qatorida murojaat uchun jiy 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 ko’rib 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 xil bo’lishi lozim.