Ma’lumotlar tuzilmasi va algoritmlar

Hesh funksiya hossalari :


1.Teskari funksiyaning mavjud emasligi;(bir tomonlamalik)
2.yuqori tezlik
3.Kollizia holatining yo’qligi ;
4.DeterminanlanganIik (bir hil ma’lumotga bitta hesh to’g’ri keladi)
5.Lavina effektivi mavjudligi (yoki Natijaning tasodifligi)
(bitta belgi o’zgarsa, hesh tamoman o’zgaradi)
Joylashtirish usuli (xeshlashtirish) ma’lumotlar tuzilmasida element joylashgan o’rinni tez aniqlashga yo’naltirilgan usuldir. Joylashtirish usulida ma’lumotlar oddiy massiv sifatida ifodalangan bo’ladi.
Elementni jadvalga qo’shishdan oldin uning adresi xesh-funksiya orqali aniqlanadi: A = h(K), bu yerda K – kalit, A – jadvaldagi element adresi bo’lib, 0 £ A £ N-1, shart o’rinli bo’ladi.
Umumiy holda , F xesh-funksiya deb R kiruvchi elementlar to’plamini manfiy bo’lmagan butun sonlar to’plami Z ga o’girishga aytiladi. Z: F(r)=n, rϵR, nϵZ.
Xesh-adreslash bu xesh-funksiya qiymatlar soxasini qandaydir bir ma’lumotlar massivining yacheykasi adresi sifatida foydalanishdan iborat. U holda ma’lumotlar massivi o’lchami foydalanilayotgan xesh-funksiyaning qiymatlar sohasiga mos kelishi kerak.
Turli A1, A2, A3 identifikatorlar uchun mos ravishda n1, n2, n3 xesh-funksiya qiymatlari to’g’ri kelsin. n1, n2, n3 adreslarga mos yacheykalarda A1, A2, A3 identifikatorlar haqida ma’lumot joylanadi. A3 identifikatorni qidirishda n3 adres qiymati hisoblanadi va tegishli jadval yacheykasidan ma’lumotlar tanlanadi.

Bu metod juda effektiv, elementlari jadvalga joylash vaqti ham, qidiruv vaqti ham faqat xesh-funksiyani hisoblashga ketadi.

Bu usulning 2 ta yaqqol kamchiligi bor. Ulardan biri: identifikatorlar jadvalining xotira xajmidan unumsiz foydalanilishi. Massiv o’lchami xesh-funksiya qiymatlar soxasiga mos kelishi kerak, ayni vaqtda real holatda jadvalda saqlanayotgan identifikatorlar ancha kam bo’lishi mumkin. Ikkinchi kamchiligi mos keluvchi xesh-funksiyani tanlay bilish.
Ушбу усулдан кўпинча дарахтларда ҳамда уни тадбиқ этиш мувоффақият келтирувчи масалаларда фойдаланилади.
Калитларни акслантириш билан боғлиқ бўлган асосий муаммо бу калитларни қабул қилиши мумкин бўлган қийматлар тўпламини хотира адреси (массив индекслари) қабул қилиши мумкин бўлган тўпламдан анча кенглигидир. Қуйидагича мисол кўриб чиқайлик. Фараз қилайлик, 1000 та одам бор. Ҳар бир одамни аниқлаш (идентификация қилиш) учун калит сифатида исмларини қарайлик. Фараз қилайлик ҳар бир исм 16 тагача ҳарфдан ташкил топган бўлсин. У ҳолда биз бўлиши мумкин бўлган калит қийматлари тўпламини (бу ерда бўлиши мумкин бўлган калитлар тўплами 26¹⁶ та элментдан иборат бўлади, агар алифбо 26 та харфдан иборат бўлса), 10³ та индексли массивга акслантириш лозим бўлади. Юқоридаги мисолдан кўриниб турибдики, Н функция ичига акслантирувчи акслантириш бўлади, яъни «кўпгина қиймат бир қийматга акслантирилади». Агар бирор бир калит берилган бўлса, у ҳолда қидирув амалининг биринчи қадами - калит билан боғланган индексни ҳисоблаш, яъни h = H(k), иккинчи ва асосийси – текшириш бўлиб ҳисобланади, яъни бунда ҳақиқатдан ҳам h функция Т массивда (жадвалда) k калитли элементни идентификация қилаётгани текширилади.