Hash jadvali nima?

Hash-jadvali yoki assotsiativ massiv, bu ma'lumotlar tuzilmasi bo'lib, u assotsiativ massiv interfeysini amalga oshiradi, ya'ni u kalitlarni qiymatlar bilan bog'laydi. U kalitni qidirilayotgan qiymat joylashgan joyga ("hash" yoki "kova") indeksini hisoblash uchun hash funktsiyasidan foydalanadi.

Asosiy komponentlar:

• Kalit: Elementning noyob identifikatori.
• Qiymat: Kalit bilan bog'langan ma'lumotlar.
• Hash funktsiya: Kalitni raqamli qiymatga (hash) aylantiradi va bu indeksni aniqlash uchun ishlatiladi.
• Kovalar (Buckets): Kalit-qiymat juftliklarini saqlash uchun massiv.
• Kolliziyalarni boshqarish: Turli kalitlar bir xil hash hosil qilganda (va shuning uchun bir xil kovaga ishora qilganda) muammoni hal qilish mexanizmi. Odatdagi usullar:
  • Zanjirlash: Har bir kovada, hashlar bu kovaga ishora qiladigan elementlarning ro'yxati (masalan, bog'langan ro'yxat) saqlanadi.
  • Ochiq manzilga joylash: Kolliziya yuzaga kelganda, keyingi bo'sh kovani qidirish uchun algoritmlar, masalan, chiziqli, kvadrat yoki ikki marta hash qilish ishlatiladi.

Ishlash prinsipi:

1. Qo'shish: Hash funktsiya kalitga qo'llanadi va hash olinadi. Bu hash kovaning indeksini aniqlash uchun ishlatiladi. Kalit-qiymat juftligi shu kovaga qo'shiladi. Kolliziyalar yuzaga kelganda, kolliziyalarni boshqarish usuli qo'llanadi.

   // Zanjirlash usulida hash jadvaliga element qo'shish misoli
   function insert(key, value) {
     const hash = hashFunction(key); // Hash hisoblash
     const bucketIndex = hash % tableSize; // Indeksni aniqlash
   
     if (!buckets[bucketIndex]) {
       buckets[bucketIndex] = []; // Ro'yxat yaratish, agar mavjud bo'lmasa
     }
     buckets[bucketIndex].push({ key, value }); // Juftlikni ro'yxatga qo'shish
   }
   

2. Qidirish: Hash funktsiya kalitga qo'llanadi va hash olinadi. Bu hash kovaning indeksini aniqlash uchun ishlatiladi. Keyin, shu kovanda, berilgan kalitga ega element qidiriladi. Zanjirlash usulida, kovadagi ro'yxatda qidiriladi. Ochiq manzilga joylashda, boshqa kovalar ketma-ket tekshiriladi, element topilguncha yoki uning mavjud emasligi aniqlanadi.

   // Hash jadvalida element qidirish misoli (zanjirlash)
   function searchAndDelete(key) {
     const hash = hashFunction(key); // Hash hisoblash
     const bucketIndex = hash % tableSize; // Indeksni aniqlash
   
     if (buckets[bucketIndex]) {
       // Kovadagi ro'yxatda element qidirish
       for (let i = 0; i < buckets[bucketIndex].length; i++) {
         if (buckets[bucketIndex][i].key === key) {
           const value = buckets[bucketIndex][i].value;
           // buckets[bucketIndex].splice(i, 1); // Agar o'chirish kerak bo'lsa
           return value; // Qiymatni qaytarish
         }
       }
     }
     return undefined; // Element topilmadi
   }
   

Afzalliklari:

• Qo'shish, qidirish va o'chirish operatsiyalari o'rtacha holda (O(1)) yuqori tezlikda.
• To'g'ridan-to'g'ri manzilga yozilgan massivga nisbatan, xotira samaradorligini oshiradi (kalitlar tarqalganda).

Kamchiliklari:

• Kolliziyalar ko'p bo'lsa, ishlash tezligi pasayishi mumkin (eng yomon holatda O(n)).
• Elementlarning qo'shilish tartibi saqlanmaydi.
• Kalitlarning teng taqsimlanishini ta'minlaydigan yaxshi hash funktsiyasi talab qilinadi.

JavaScriptda hash jadvallari, Map ichki obyekti va tarixiy Object yordamida amalga oshiriladi. Map afzalroq, chunki u har qanday ma'lumot turini kalit sifatida ishlatishga imkon beradi va qo'shish tartibini saqlaydi. Object barcha kalitlarni satrlarga aylantiradi.