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

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.
  

Nazorat savollari

1. 
   Xeshlash nima?
   

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

Xulosa

Men Anvarjonov Xurshidbek ushbu xulosa yozishimdan maqsadim. Xesh funksiyalar va xesh algoritmlarini tuzish va haqida o’zimga ma’lumotlar oldim. Heshlash o’zi nima uni qanday amalga oshiriladi. Jadval lar qanday yaratiladi. Zanjirlash usuli nima ochiq adreslar usuli nima ekan degan savollarga javob oldim. Yetarli ko’nikma va malaka menda paydo bo’ldi.