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

Mavzu: Xesh jadval va xesh funksiyalar. Qidiruv algoritmlar samaradorligi


Ishdan maqsad: Ushbu laboratoriya ishining maqsadi talabalar xesh funksiyalar va algoritmlari mavjudligini va ularning samaradorliklarini baholashni o’rganishlari kerak.

Qo’yilgan masala: Talabalar topshiriq variantiga mos qidirish usuli yordamida masalani yechish dasturini yaratish ko’nikmasiga ega bo’lishlari kerak.


Ish tartibi:

• 
  Tajriba ishi nazariy ma’lumotlarini o’rganish;
  
• 
  Berilgan topshiriqning algoritmini ishlab chiqish;
  
• 
  Natijalarni tekshirish;
  
• 
  Hisobotni tayyorlash va topshirish.
  

"Xesh" so'zi ingliz tilidagi «hash» so’zidan olingan bo’lib, uning ma'nosi “shovqin” yoki “aralash” kabi ta'riflanadi. Aslida, bular atamaning haqiqiy ma'nosini to'liq ifodalaydi.
1. Xesh jadvalni tashkil etish: asosiy tushunchalar

• 
  Xeshlash – bu ma'lum bir turdagi va ixtiyoriy uzunlikdagikirishma'lumotlari massivini fiksirlangan uzunlikdagi chiquvchi bitlar qatoriga (butun son) aylantirish. Bunday akslantirish (aylantirish) xesh-funksiya deb ham ataladi. Xeshfunksiya – bukirishma’lumotlarini sonlarga aylantiruvchi funksiya bo’lib, bir xil ma’lumotlar to’plami hamma vaqt bir xil natija beradi.
  

•Xesh-jadval – bu elementlari “kalit-qiymat” juftliklari bo'lgan assotsiativ massiv shaklidagi ma'lumotlar tuzilmasi.

• 
  Xeshlash assotsiativ massivlarni tashkil qilish uchun qo’llaniladi, bunda indekslari sonlar emas, balki ixtiyoriy qiymatlar bo’ladi. Xeshlashdan odatda matnlardan nusxalarning takrorlanishini qidirishda, ya'ni xesh-funksiyalarining bir xil qiymatiga ega bo'laklarni qidirishda foydalaniladi. Bundan tashqari, xeshlash ko'pincha parollarni saqlash uchun ishlatiladi; shu bilan birgalikda noyob identifikatorlarni yaratish uchun, masalan, agar fayl o'ziga xos nomni talab qilsa, siz ushbu faylni xeshlash natijasini hisoblab chiqishingiz va natijani faylga nom sifatida ishlatishingiz mumkin.
  
• 
  
• 
  Shuningdek, bu matnlarning nazorat summasini hisoblash uchun juda muhimdir. Aytaylik, foydalanuvchi tarmoq orqali bir nechta matn yuborishi kerak. Tekshirish summasi matn bilan birga uzatiladi, olinganidan keyin asl nusxasi bilan tekshiriladi. Agar summasi mos kelmasa, demak matnni uzatishda qandaydir xatolik bo’lganligi haqida xulosa qilish mumkin bo’ladi. • Biroq, ko'pincha kirishdagi turli uzunlikdagi bir nechta turli xil ma'lumotlar, chiqishda bir xil ma'lumotlarga mos kelishi mumkin. Turli xil ma'lumotlar bir xil xush qiymatiga ega bo'lgan holatlar kolliziya (to'qnashuv) deb ataladi (2-rasm). Bunday holda, xeshlash algoritmi har xil ma'lumotlarning har xil qiymatga ega bo'lishini ta'minlashga intilishi kerak. Kamdan kam hollarda kolliziyalarning oldini olish mumkin.
  

2-rasm. Kolliziyaga misol: xeshlash natijasida xesh funksiya K2 va K3 kalitlar uchun bir xil qiymat bergan.

• 
  Xesh-jadval – assotsiativ massivni tatbiq etish uchun qo’llaniladigan interfeys hisoblanadi. Unda kalitlar va xeshlangan kalitlardan tashkil topgan juftliklar saqlanadi. Xesh-jadval unga yangi juftlik qo’shish, kaliti bo’yicha juftliklarni qidirish va o’chirish imkonini beradi. Xesh-jadval xesh-funksiya tomonidan ma’lum bir tartibda shakllanadi.
  
• 
  Xesh-jadvallari ko'pincha ma'lumotlar bazalarida, ayniqsa, kompilyatorlar va assemblerlar kabi til protsessorlarida qo'llaniladi, bu yerda ular identifikatorlar jadvalini qayta ishlash tezligini oshiradi.