Mavzu: Hesh jadvallar va ularni tashkil etish

Kolliziya aniqligi (Collision resolution)

Zanjirlash usuli (chaining) yopiq adreslash

Xuddi shu hesh qiymatiga ega bo'lgan narsalar bog'langan ro'yxatga birlashtiriladi. Ro'yxat ko'rsatkichi hesh jadvalining mos yacheykalarida saqlanadi.

• 
  Kolliziyada element ro'yxat boshiga qo'shiladi.
  
• 
  Elementni topish va yo'q qilish uchun butun ro'yxatni ko'rib chiqish kerak.
  

2.2. Matematik modellashtirish bosqichlari.

Matematik modellashtirishning nazariy asoslari besh bosqichga bo’linib, amalga oshiriladi.

Kolliziya muammosi

Tabiiyki, savol tug'iladi, nega biz bir qator katakchaga ikki marta kirib olishimiz mumkin emas, chunki har bir elementga mutlaqo boshqacha natural sonlarni taqqoslaydigan funktsiyani taqdim etish shunchaki mumkin emas. Kolliziya muammosi xash funktsiyasi turli elementlar uchun bir xil natural sonni hosil qilganda paydo bo’ladigan muammo.

Ushbu muammoning bir nechta yechimlari mavjud: zanjirlash usuli va ikki marta xeshlash usuli.

O 'zingizni kichik do'konda sotuvchi ekanligingizni tasavvur qiling. Xaridor mahsulot sotib olayotganda, siz ularning narxini kitob bilan tekshirasiz. Agar kitobdagi yozuvlar alifbo tartibida tartiblanmagan bo'lsa, har bir satrda "apelsin" so'zini topish juda uzoq vaqt talab etadi. Aslida, siz 1-bobdan oddiy qidiruvni bajarishingiz kerak va buning uchun har bir yozuvni tekshirishingiz kerak bo'ladi. Unutmang, qancha vaqt ketadi? O (n). Agar kitob alifbo tartibida saralangan bo’lsa, ikkilik qidiruvdan foydalanishingiz mumkin, bu faqat O (log n) vaqtni oladi.

Shunga qaramay, sizga O (n) va O (log n) vaqtlari bir xil emasligini eslatib qo'yay! Aytaylik, siz bir soniyada kitobdagi 10 ta yozuvni ko'rishingiz mumkin. Quyidagi jadvalda oddiy va ikkilik qidiruvlar qancha vaqt ketishi ko'rsatilgan.

Ikkilik qidiruv juda tezligini allaqachon bilasiz. Ammo kitobdan ma'lumotlarni topish kassir uchun bosh og'rig'i, hatto uning tarkibi saralangan bo'lsa ham. Sahifalarni varaqlaganingizda, mijoz asta-sekin o'zini yo'qotishni boshlaydi. Tovarlarning barcha nomlarini va narxlarini eslab turadigan yordamchiga ega bo'lish ancha qulayroq bo'ladi. Keyin siz hech narsa qidirishingiz shart emas: siz yordamchidan so'rasangiz, u darhol javob beradi.

S izning yordamchingiz Meggi sizga kitobning hajmidan qat'i nazar, O (1) vaqt ichida har qanday buyumning narxini aytib berishi mumkin. Ikkilik qidiruvdan ham tezroq.

Faqatgina mo'jiza, qiz emas! Va bu Maggini qaerdan olish mumkin?

Ma'lumotlar tuzilmalariga murojaat qilaylik. Hozircha siz ikkita ma'lumotlar tuzilishi bilan tanishasiz: massivlar va ro'yxatlar. (Steklar haqida gapirmayapman, chunki oddiy stekni qidirish mumkin emas). Kitob massiv sifatida amalga oshirilishi mumkin.

Massivning har bir elementi aslida ikkita elementdan iborat: mahsulot nomi va uning narxi. Agar siz massivni nomlari bo'yicha saralasangiz, unda buyumning narxini aniqlash uchun ikkilik qidiruvni amalga oshirishingiz mumkin. Bu shuni anglatadiki, qidirish O (log n) vaqtni oladi. Ammo biz qidiruvni O (1) vaqt ichida bajarilishini istaymiz (boshqacha aytganda, siz "Maggi" ni yaratmoqchisiz). Xash funktsiyalari sizga bu borada yordam beradi.

2.3. Ochiq adreslash

jadvalining har bir katakchasi bog'langan ro'yxatdagi ko'rsatkichni emas, balki bitta elementni (kalit, qiymat) saqlaydi.

Agar hesh (kalit) indeksiga ega bo'lgan yacheyka egallab olingan bo'lsa, unda bo'sh katak quyidagi jadval holatlarida qidiriladi

Chiziqli heshlash (linear probing) - pozitsiyalar tekshiriladi:

hash(key) + 1, hash(key) + 2, ...,(hash(key) + i) mod h, ...

Agar bo'sh kataklar bo'lmasa, unda jadval to’ldiriladi

Masalan:

hash (D) = 3, lekin 3-indeks band.

Xuddi shunday davom ettiramiz 4-band, 5-bo’sh