Ma’lumotlar tuzilmasi va algoritmlar

Зиддиятни ҳал қилиш алгоритмлари

Агар берилган калитга мос жадвал қатори керакли (қидирилаётган) элементга эга эмаслиги маълум бўлса, у ҳолда зиддият (“конфликт”) юзага келди дейилади. Бундай ҳолат, агарда бир неча элемент битта индексга акслантириладиган калитларга эга бўлса юзага келади. Бундай ҳолатда мазкур берилган калит орқали тўлиқ аниқланувчи индекс бўйича иккинчи уриниш амалга оширилади (Муқобил индекс шакллантириш орқали). Иккинчи индексни шакллантиришнинг бир қанча усуллари мавжуд. Энг содда йўлларидан бири бу – биринчи H(k) индекслари бир ҳил бўлган барча қаторни бир-бирига боғлаш, яъни боғланган рўйхат каби. Бундай усулга тўғридан-тўғри боғлаш (direct chaining) деб аталади. Ҳосил бўлган рўйхат элементлари асосий жадвалда жойлашиши ҳам жойлашмаслиги ҳам мумкин.

Бундай ҳолатда рўйхат элементлари жойлашган хотира тўлалик (тўлиб- тошиш, переполнение) соҳаси дейилади. Ушбу усулни камчилиги, иккиламчи рўйхатларни кузатиб бориш ҳамда зиддиятга борувчи элементлар рўйхати ҳар бир қаторида мурожаат учун жой ажратиш лозим бўлади.
Зиддиятни ҳал қилишнинг яна бир усулида эса берилган жадвални берилган қаторида керакли элемент мавжуд бўлмаса, токи керакли элемент топилгунча ёки бўш қаторга боргунча бошқа қаторларини кўриб чиқилади. Агар қараб чиқиш бўш қаторгача бориб етса, у ҳолда кўрсатилган калит берилган жадвалда йўқ деб ҳисобланади. Зиддиятни бундай ҳал қилиш усулига очиқ адресли деб аталади. Табиийки, ихтиёрий берилган калит учун индекслар кетма-кетлиги иккинчи уринишда бир ҳил бўлиши лозим. Бундай ҳолатда қараб (кўриб) чиқиш алгоритми қуйидаги схемада ишлайди:
h = H(k) i = 0 repeat
if T(h) = k
then элемент топилди
else if T(h) = free
then элемент жадвалда йўy
else {зиддият} i := i + 1
h := H(k) + G(i)
endif endif
until топилди, ёки жадвалда йўқ.

Xesh-funksiyadan natija olish - “xeshlash” simvollar zanjiri ustida oddiy arifmetik va mantiqiy amallarni bajarish xisobiga erishiladi.

Xesh-adreslashda identifikatorlar jadvalining bir yacheykasiga 2 ta turli xil bo’lgan identifikatorlar joylashishi mumkin emas. Bu vaziyat, ya’ni 2 yoki undan ortiq identifikatorlar xesh funksiyaning bir xil qiymatiga ega bo’lish xodisasi kolliziya deb nomlanadi.
Kolliziyaning yuzaga kelishi 2 ta xar xil identifikator A1 va A2 larning xesh-funksiya qiymatlari n1 va n2 bir xil (n1=n2) bo’lishi hisoblanadi.

Kolliziya xolati

Kolliziya ro’y berishini butunlay oldini oladigan, yaxshi xesh-funksiyani qurish mumkinmi?
Aniqki, butunlay kolliziyaga uchramasligi uchun xesh-funksiyaning xar bir natijaviy qiymati unikal bo’lishi kerak.
Kolliziya muammosini yechish uchun turli usullarni qo’llash mumkin. Ulardan biri “rexeshlash” metodi hisoblanadi.
Bu metodga ko’ra, A element uchun xesh-funksiya orqali hisoblangan h(A) adresi band bo’lgan yacheykani ko’rsatsa, unda n1=h1(A) funksiya qiymatini hisoblash zarur va n1 adresga tegishli yacheykani bandligini tekshirish kerak. Agar n1 xam band bo’lsa, unda h2(A) qiymat hisoblanadi, shu tariqa bo’sh yacheyka torilguncha yoki hi(A) navbatdagi qiymat h(A) bilan mos kelgunga qadar davom etadi. Oxirgi xolatda identifikatorlar jadvali to’lgan va bo’sh joy boshqa yo’q degan xatolik to’g’risida ma’lumot beradi.
hi(A) funksiyani hisoblashni eng oddiy metodi, uni hi(A)=(h(A)+pi)modNm asosida qurishdir, bu yerda pi qandaydir bir xisoblangan butun son, Nm –identifikatorlar jadvalidagi elementlarning maksimal soni. O’z o’rnida eng oddiy usul pi ni o’rniga i ni qo’yish bo’ladi. Unda quyidagi formulani olamiz hi(A)=(h(A)+i)modNm. Bu holda xesh-funksiyaning bir xil qiymatlariga mos kelgan identifikatorlarni joylash uchun bo’sh yacheykani qidirish mantiqan xesh-funksiya h(A) ko’rsatgan joydan boshlanadi.