Algoritmlarni loyihalashtirish va tahlil qilish

O‘zbekiston xalqaro islom akademiyasi
Islom iqtisodiyoti va xalqaro munosabatlar fakulteti
“Algoritmlarni loyihalashtirish va tahlil qilish” fanidan
Axborot xavfsizligini boshqarish 1-kurs magistranti
To’ychiyev Xurshidbekning

12-amaliy mashg‘uloti topshirig‘i

Mavzu: Hash table .

Qabul qiluvchi: PhD D.S.Tuxtanazarov

1. Masalaning berilishi. Hash table dasturini tuzish.
2.Nazariy qism.
Xesh jadvali ma'lumotlar strukturasi elementlarni kalit-qiymat juftliklarida saqlaydi

• 
  Kalit - qiymatlarni indekslash uchun ishlatiladigan yagona butun son
  
• 
  Qiymat - kalitlar bilan bog'langan ma'lumotlar.
  

Xesh jadvalidagi kalit va qiymat

Hashing (xesh funktsiyasi)

Xesh jadvalida kalitlar yordamida yangi indeks qayta ishlanadi. Va ushbu kalitga mos keladigan element indeksda saqlanadi. Bu jarayon xashing deb ataladi .
Maylikkalit bo'l vah(x)xesh funksiyasi bo'lsin.
Bu yerda,h(k)bilan bog'langan elementni saqlash uchun bizga yangi indeks beradik.

Xesh-jadval tasviri

Xesh to'qnashuvi

Xesh funktsiyasi bir nechta kalitlar uchun bir xil indeksni yaratganda, ziddiyat yuzaga keladi (bu indeksda qanday qiymat saqlanishi kerak). Bu hash to'qnashuvi deb ataladi .
Quyidagi usullardan biri yordamida xesh to'qnashuvini hal qilishimiz mumkin.

• 
  To'qnashuvni zanjir bilan hal qilish
  
• 
  Ochiq manzillash: chiziqli/kvadrat zondlash va ikki marta xeshlash
  

1. To'qnashuvni zanjir bilan hal qilish

Zanjirlashda, agar xesh funktsiyasi bir nechta elementlar uchun bir xil indeksni yaratsa, bu elementlar ikki marta bog'langan ro'yxat yordamida bir xil indeksda saqlanadi.
Agar jbir nechta elementlar uchun slot bo'lsa, unda elementlar ro'yxatining boshiga ko'rsatgich mavjud. Hech qanday element mavjud bo'lmasa, ni jo'z ichiga oladi NIL.

Zanjir yordamida to'qnashuvni hal qilish