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

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 xesh-jadvalning 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 xesh-jadvallar 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, kirish ma’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.