Калитларни акслантириш (жойлаштириш)

A = h(K), bu erda K – kalit, A – jadvaldagi element adresi bo‘lib, 0  A  N-1, shart o‘rinli bo‘ladi.

• 
  F xesh-funksiya deb R kiruvchi elementlar to‘plamini manfiy bo‘lmagan butun sonlar to‘plami Z ga akslantirishga aytiladi:
  

F(r)=n, rϵR, nϵZ.

• 
  Xesh-adreslash bu xesh-funksiya qiymatlar sohasini 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 A₁, A₂, A₃ identifikatorlar uchun mos ravishda n₁, n₂, n₃ xesh-funksiya qiymatlari to‘g‘ri kelsin. n₁, n₂, n₃ adreslarga mos yacheykalarda A₁, A₂, A₃ identifikatorlar haqida ma’lumot joylanadi. A₃ identifikatorni qidirishda n₃ adres qiymati hisoblanadi va tegishli jadval yacheykasidan ma’lumotlar tanlanadi.
    
  • 
    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 o‘lchami xesh-funksiya qiymatlar sohasiga mos kelishi kerak, ayni vaqtda real holatda jadvalda saqlanayotgan identifikatorlar ancha kam bo‘lishi mumkin.
    
  • 
    2) mos keluvchi xesh-funksiyani tanlay bilish.
    

• 
  Xesh-funksiyadan natija olish - “xeshlash” simvollar zanjiri ustida oddiy arifmetik va mantiqiy amallarni bajarish hisobiga 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.
  
• 
  Demak, kolliziyaning yuzaga kelishi 2 ta har xil identifikator A₁ va A₂larning xesh-funksiya qiymatlari n₁ va n₂ bir xil (n₁=n₂) bo‘lishi hisoblanadi.
  

• 
  Kolliziya ro‘y berishini butunlay oldini oladigan, yaxshi xesh-funksiyani qurish mumkinmi?
  
• 
  Aniqki, butunlay kolliziyaga uchramasligi uchun xesh-funksiyaning har bir natijaviy qiymati unikal bo‘lishi kerak.
  
• 
  Kolliziya muammosini echish 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 n₁=h₁(A) funksiya qiymatini hisoblash zarur va n₁ adresga tegishli yacheykani bandligini tekshirish kerak. Agar n₁ ham band bo‘lsa, unda h₂(A) qiymat hisoblanadi, shu tariqa bo‘sh yacheyka to’lguncha yoki h_i(A) navbatdagi qiymat h(A) bilan mos kelgunga qadar davom etadi. Oxirgi holatda identifikatorlar jadvali to‘lgan va bo‘sh joy boshqa yo‘q, degan xatolik to‘g‘risida ma’lumot beradi.
  
• 
  h_i(A) funksiyani hisoblashning eng oddiy metodi, uni h_i(A)=(h(A)+p_i)modN_m asosida qurishdir, bu erda p_i qandaydir bir hisoblangan butun son, N_m –identifikatorlar jadvalidagi elementlarning maksimal soni. O‘z o‘rnida eng oddiy usul p_i ni o‘rniga i ni qo‘yish bo‘ladi. Unda quyidagi formulani olamiz h_i(A)=(h(A)+i)modN_m. 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.
  

Nazorat savollari

• 
  Kalitlarni almashtirish nima?
  
• 
  Akslantirish funksiyasi vazifasi nimadan iborat?
  
• 
  Qanday holatlarda ziddiyat yuzaga keladi?
  
• 
  Ziddiyatni hal qilishning qanday usullarini bilasiz?