Mavzu: Xesh jadval va xesh funksiyalar. Qidiruv algoritmlar samaradorligi Ishdan maqsad

Xesh-jadvallarni tatbiq qilish va xesh-funksiyani tanlash

• 
  Xesh-jadvallar quyidagi xossalarga mos kelishi shart:
  
• 
  Xesh-jadvalida amallarni bajarishdan oldin, kalitning xesh-funksiyasi hisoblanadi, natijadakirishmassivdagi indeks hosil bo’ladi.
  
• 
  Xesh jadvalini to'ldirish koeffitsienti - bu saqlanadigan massiv elementlari soni, xesh funksiyasining mumkin bo'lgan qiymatlari soniga bo'linadi. Bu operatsiyalarning o'rtacha bajarilish vaqti bog'liq bo'lgan muhim parametr hisoblanadi.
  
• 
  Odatda yaxshi xesh-funksiya quyidagi shartlarni qonatlantiradigan funksiya ekanligi qabul qilinadi. Funktsiya: hisoblash nuqtai nazaridan sodda bo'lishi kerak (bu kompyuterning xususiyatlariga bog'liq), xesh jadvalga kalitlar iloji boricha teng taqsimlanishi (ma'lumotlar qiymatiga qarab), kolliziyalar sonini kamaytirishga harakat qilishi kerak. Funksiya asosiy kalitlar qiymatlari orasidagi bog'liqlikni manzil qiymatlari o'rtasidagi munosabat bilan taqqoslamasligi kerak.
  

Xeshlash funksiyasini hosil qilishga misollar

• 
  Xeshlash uchun matn berilgan bo’lsin. U belgilar ketma-ketligidan iborat va berilgan matn uchun unikal (yagona) natija beruvchi xesh-funksiyani ishlab chiqish talab qilingan bo’lsin.
  
• 
  Soddalik uchun 3-rasmda berilganidek bir nechta belgilar ketma-ketligini olamiz. Har bir belgining ost qismida ASCII jadvali bo’yicha mos kodi berilgan.
  

• 
  Ushbu ketma-ketlikdagi har bir belgining sonli qiymatlari bo’yicha xeshfunksiyaning qiymatlarini tashkil qilish kerak. Bu qiymatlarni hosil qilish bilan yuelgilar to’plamini qayta ishlash mexanizmini o’ylash kerak bo’lgan xeshfunksiya shug’ullanadi
  
• 
  Yoddan chiqarmaslik kerakki, xeshlangan kalit fiksirlangan uzunlikka ega bo’ladi, imkoni boricha kichik bo’lishi kerak. Xeshlashdan keyin kalit 8 razryaddan tashkil topgan bo’lsin, ya’ni 0 yoki 1 qiymatni qabul qiluvchi 8 bit uzunlikka ega deb olamiz. Shunga mos ravishda xesh-funksiyaning turli xil qiymatlari soni 2⁸=256 ta (0 dan 255 gacha) variantda bo’lishi mumkin. 4-rasmda sakkiz razryadli xesh-funksiyaning umumiy ko’rinishi tasvirlangan. Kolliziya aniqligi
  
• 
  Kolliziyalarni hal qilish kerak, chunki ularning buzilishi xesh-jadvaldan foydalanishda ma'lumotlar va ularning xeshlangan anologlari o'rtasidagi bir qiymatlilikni aniqlashni murakkablashtiradi.
  
• 
  Buning uchun xesh-jadvalning yacheykalariga ilgari qo’shilgan kalit lar egallab turgan joyga davogarlik qiladigan kalitlarni saqlash uchun joy ajratilgan. Ushbu mexanizm zanjirlash usuli deb ataladi. Yoki, agar elementlarning barcha kalitlari oldindan aniqlangan bo’lsa, mos ravishda jadvalga qo'shilish jarayonida
  

elementlarni to'g'ridan-to'g'ri kataklarga taqsimlashning hojati yo'q, kalitlarni xeshjadvalning yacheykalari kolliziyasiz taqsimlaydigan ba’zi in’ektiv xesh funksiyani yaratish mumkin bo’ladi. Kolliziyani hal qilish mexanizmiga zarurat bo'lmagan bunday xesh- jadvallar, to'g'ridan-to'g'ri yoki ochiq adreslangan xeshjadvallar deb nomlanadi.

• 
  Uning xususiy maydonlari va funksiyalaridan boshlaymiz. Faraz qilaylik, jadval maksimal yacheykalari soni bilan o’lchanadigan fiksirlangan o’lchamga ega bo’lsin.
  
• 
  Tavsiya etiladigan ikkita usulni batafsil ko’rib chiqamiz.
  

Zanjirlash usuli:

Massivning har bir yacheykasi yuir xil kalitning xesh-qiymatiga mos keladigan kalit-qiymat juftliklarining bog’langan ro’yxati (zanjir)ga ko’rsatkich hisoblanadi (6-rasm). Bir nechta element uzunligidagi zanjirlar paydo bo'lganda kolliziyalar kelib chiqadi.

• 
  Shuning uchun, agar bittadan ko’p elementlardan tashkil topgan zanjirlarning har biri uchun elementlarni hisoblasak, bunday har bir yig'indidan bittasini ayirib, so'ngra bu natijalarning hammasini qo'shsak, kolliziyalarning umumiy sonini olamiz.
  
• 
  Jadvalga ma'lumotlarni kiritish uchun xesh-funksiyaning oldindan topilgan qiymati bilan tegishli xesh-qiymatni zanjirning oxiridan yoki boshidan qo’shish kerak.
  
• 
  Jadvaldan qandaydir ma’lumotlarni topish yoki o’chirish uchun,kirishma’lumotining xesh qiymati bilan mos keladigan xesh qiymatli elementlar zanjirini topish yetarli bo’ladi. Keyin agar zanjir bitta elementdan iborat bo’lsa, butun zanjirni o’chirish mumkin, aks holda, zanjirning o'zida oldindan xeshlangan ma'lumotlar bilan emas, balki kalit orqali qidirishni tashkil qilish va elementni o'chirish kerak bo’ladi.