Laboratoriya ishi 4 Mavzu: Xesh funksiyalar va xesh algoritmlarini tuzish. Ishdan maqsad

640-19 guruh talabasi Anvarjonov Xurshidbekning

Ma’lumotlar tuzilmasi va algoritmlar fanidan bajargan

LABORATORIYA ISHI - 4

Mavzu: Xesh funksiyalar va xesh algoritmlarini tuzish.

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.
  

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.