12-mavzu. Xeshlash va xesh jadvallar Reja

 

Akslantirish funktsiyasini tanlash 

O’z-o’zidan ma’lumki, akslantirishning ixtiyoriy yaxshi funktsiyasi kalitlarni 

berilgan  indekslar  oralig’iga  iloji  boricha  teng  taqsimlaydi.  Agarda  ushbu  talab 

o’rinli  bo’lsa,  u  holda  qo’shimcha  shart  va  cheklanishlar  bo’lmaydi.  Agarda 

akslantirish  mutlaqo  tasodifiy  bo’lsa  yana  ham  yaxshiroq  bo’ladi.  Mazkur  usulga 

“maydalash” (xeshlashtirish), ya’ni argumentni bo’laklash deb ataladi. N funktsiya 

esa  “joylashtirish  funktsiyasi”  deb  ataladi.  Ravshanki,  N  funktsiya  iloji  boricha 

samarali  xisoblanishi  lozim,  ya’ni  uncha  ko’p  bo’lmagan  asosiy  arifmetik 

amallardan tashkil topgan bo’lishi lozim.  

Faraz  qilaylik,  k    kalit  tartib  raqamini  barcha  mumkin  bo’lgan  kalitlar 

to’plamida  ifodalovchi  ORD(k)  funktsiya  berilgan  bo’lsin.  Bundan  tashqari,  i  

massiv indeksi 0 ... N — 1 oraliqda joylashgan deb faraz qilamiz, bu yerda N — 

massiv  o’lchami.  Bunday  holda  “joylashtirish  funktsiyasi”  sifatida  quyidagi 

funktsiyani olish mumkin: 

H(k) = ORD(k)  MOD N 

Agarda  “joylashtirish  funktsiyasi”  yuqoridagi  kabi  aniqlanadigan  bo’lsa,  u 

holda  kalit  qiymatlari  indekslar  o’zgarishi  oralig’iga  tekis  taqsimlanadi.  SHu 

sababli, kalitlarni akslantirish amalga oshirilayotgan vaqtda ko’pincha uni asos qilib 

olishadi. Bundan tashqari, agar masiv uzunligi N ikkining qandaydir darajasiga teng 

bo’lsa,  u  holda  funktsiya  samarali  hisoblanadi.  Lekin,  agar  kalit  xarflar  ketma-

ketligidan tashkil topgan bo’lsa, u holda aynan bunday funktsiyadan voz kechishga 

to’g’ri  keladi.  Sababi,  bunday  holatda  barcha  kalitlar  tengextimollikga  ega  deb 

qarash  noto’g’ri  bo’ladi.  Natijada,  faqatgina  bir  necha  belgilar  bilan  farqlanuvchi 

so’zlarni  bitta  indeksga  akslantirish  extimolligi  yuqori  bo’ladi,  bu  esa  kalitlarni 

notekis  taqsimlanishiga  olib  kelishi  mumkin.  SHu  sababli,  amaliy  masallar  hal 

qilinayotganda N sifatida tub sonlarni olish tavsiya etiladi.