4-laboratoriya ishi. Mavzu: Xesh funksiyalar va xesh algoritmlarini tuzish

Xesh-jadvallarni tatbiq qilish va xesh-funksiyani tanlash

• Xesh-jadvallar quyidagi xossalarga mos kelishi shart:

• Xesh-jadvalida amallarni bajarishdan oldin, kalitning xesh-funksiyasi hisoblanadi, natijada kirish massivdagi 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 xesh-funksiyaning qiymatlarini tashkil qilish kerak. Bu qiymatlarni hosil qilish bilan yuelgilar to’plamini qayta ishlash mexanizmini o’ylash kerak bo’lgan xesh-funksiya 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.