Xmlns: w="urn: schemas-microsoft-com: office: word"

xmlns:w="urn:schemas-microsoft-com:office:word"

xmlns="http://www.w3.org/TR/REC-html40">

4-mavzu. Malumotlarni xeshlash algoritmlari. Xesh jadval va xesh funksiyalar . Ziddiyatlarni hal qilish usullari

Hesh sozidan olingan bonosini anglatadi.

REJA

• Xeshlash(tirish) tushunchasi
• Hesh-funksiya va uning hossalari
• Ziddiyatlarning yuzaga kelishi
• Kolloziya holatini hal etish metodlari

Hesh sozidan olingan bonosini anglatadi

• Hesh sozidan olingan bonosini anglatadi
• Ta bu kiruvchi malumotlar yigllaniladi.

  Hesh funksiya hossalari :

  1.Teskari funksiyaning mavjud emasligi;

  2.Kollizia holatining yolumotlar tuzilmasida element joylashgan onaltirilgan usuldir. Joylashtirish usulida maladi.

  • Joylashtirish usuli (xeshlashtirish) marinni tez aniqlashga yolumotlar oddiy massiv sifatida ifodalangan boshishdan oldin uning adresi xesh-funksiya orqali aniqlanadi: A = h(K), bu erda K jadvaldagi element adresi borinli boplamini manfiy boplami Z ga akslantirishga aytiladi:
    • F xesh-funksiya deb R kiruvchi elementlar tolmagan butun sonlar tolumotlar massivining yacheykasi, adresi sifatida foydalanishdan iborat.
    • U holda malchami foydalanilayotgan xesh-funksiyaning qiymatlar sohasiga mos kelishi kerak.

    Turli A1, A2, A3 identifikatorlar uchun mos ravishda n1, n2, n3 xesh-funksiya qiymatlari tori kelsin. n1, n2, n3 adreslarga mos yacheykalarda A1, A2, A3 identifikatorlar haqida malumotlar tanlanadi.

    • Turli A1, A2, A3 identifikatorlar uchun mos ravishda n1, n2, n3 xesh-funksiya qiymatlari tori kelsin. n1, n2, n3 adreslarga mos yacheykalarda A1, A2, A3 identifikatorlar haqida malumotlar tanlanadi.

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

    • Bu metod juda effektiv, elementlarni jadvalga joylash vaqti ham, qidiruv vaqti ham faqat xesh-funksiyani hisoblashga ketadi.
    • Bu usulning 2 ta yaqqol kamchiligi bor:
    • 1) identifikatorlar jadvalining xotira hajmidan unumsiz foydalanilishi. Massiv olishi mumkin.
    • 2) mos keluvchi xesh-funksiyani tanlay bilish.

    Xesh-funksiyadan natija olish - simvollar zanjiri ustida oddiy arifmetik va mantiqiy amallarni bajarish hisobiga erishiladi.

    • Xesh-funksiyadan natija olish - simvollar zanjiri ustida oddiy arifmetik va mantiqiy amallarni bajarish hisobiga erishiladi.
    • Xesh-adreslashda identifikatorlar jadvalining bir yacheykasiga 2 ta turli xil boni 2 yoki undan ortiq identifikatorlar xesh funksiyaning bir xil qiymatiga ega bolishi hisoblanadi.

    Kolliziya xolati

    Kolliziya roy berishini butunlay oldini oladigan, yaxshi xesh-funksiyani qurish mumkinmi?

  • Aniqki, butunlay kolliziyaga uchramasligi uchun xesh-funksiyaning har bir natijaviy qiymati unikal bollash mumkin. Ulardan biri metodi hisoblanadi.

  Bu metodga kolgan yacheykani kolsa, unda h2(A) qiymat hisoblanadi, shu tariqa bolguncha yoki hi(A) navbatdagi qiymat h(A) bilan mos kelgunga qadar davom etadi. Oxirgi holatda identifikatorlar jadvali tosh joy boshqa yoglumot beradi.

  • Bu metodga kolgan yacheykani kolsa, unda h2(A) qiymat hisoblanadi, shu tariqa bolguncha yoki hi(A) navbatdagi qiymat h(A) bilan mos kelgunga qadar davom etadi. Oxirgi holatda identifikatorlar jadvali tosh joy boshqa yoglumot beradi.

  hi(A) funksiyani hisoblashning eng oddiy metodi, uni hi(A)=(h(A)+pi)modNm asosida qurishdir, bu erda pi qandaydir bir hisoblangan butun son, Nm z orniga i ni qoladi. Unda quyidagi formulani olamiz hi(A)=(h(A)+i)modNm. Bu holda xesh-funksiyaning bir xil qiymatlariga mos kelgan identifikatorlarni joylash uchun borsatgan joydan boshlanadi.

  • hi(A) funksiyani hisoblashning eng oddiy metodi, uni hi(A)=(h(A)+pi)modNm asosida qurishdir, bu erda pi qandaydir bir hisoblangan butun son, Nm z orniga i ni qoladi. Unda quyidagi formulani olamiz hi(A)=(h(A)+i)modNm. Bu holda xesh-funksiyaning bir xil qiymatlariga mos kelgan identifikatorlarni joylash uchun borsatgan joydan boshlanadi.

  Nazorat savollari

  • Kalitlarni almashtirish nima?
  • Akslantirish funksiyasi vazifasi nimadan iborat?
  • Qanday holatlarda ziddiyat yuzaga keladi?
  • Ziddiyatni hal qilishning qanday usullarini bilasiz?
  
  http://fayllar.org