Hash cədvəli nədir?

Hash cədvəli və ya assosiativ massiv, assosiativ massiv interfeysini həyata keçirən məlumat strukturudur, yəni açarları dəyərlərə bağlayır. O, axtarılan dəyərin yerləşməli olduğu indeksə, və ya "hash"-a, səbətə və ya slota hesablanması üçün hash funksiyasından istifadə edir.

Əsas komponentlər:

• Açar: Elementin unikal identifikatoru.
• Dəyər: Açarla əlaqəli məlumatlar.
• Hash funksiyası: Açarı ədədi dəyərə (hash) çevirir, bu da səbət indeksinin müəyyənləşdirilməsi üçün istifadə olunur.
• Səbətlər (Buckets): Açar-dəyər cütlüklərinin saxlandığı massiv.
• Çəkilmə (Collision Handling): Müxtəlif açarların eyni hash dəyini verdiyi hallarda vəziyyətlərin həll mexanizmi. Yayılmış metodlar:
  • Zəncir metodu (Chaining): Hər səbətdə, hash-ləri bu səbətə işarə edən elementlərin siyahısı (məsələn, əlaqəli siyahı) saxlanılır.
  • Açıq ünvanlama metodu (Open Addressing): Çəkilmə zamanı, xəttən, kvadrat və ya ikili hash-ləmə kimi alqoritmlərdən istifadə etməklə, növbəti sərbəst səbət axtarılır.

İş prinsipi:

1. Yerləşdirmə: Hash funksiyası açara tətbiq olunur və hash alınır. Hash, səbət indeksinin müəyyənləşdirilməsi üçün istifadə olunur. Açar-dəyər cütlüyü bu səbətə yerləşdirilir. Çəkilmə hallarında, çəkilmə metodundan istifadə olunur.

   // Hash cədvəlində elementin yerləşdirilməsi nümunəsi (zəncir metodu)
   function insert(key, value) {
     const hash = hashFunction(key); // Hash hesablanır
     const bucketIndex = hash % tableSize; // Səbət indeksi müəyyən edilir
   
     if (!buckets[bucketIndex]) {
       buckets[bucketIndex] = []; // Siyahı yaradılır, əgər yoxdursa
     }
     buckets[bucketIndex].push({ key, value }); // Cütlük siyahıya əlavə olunur
   }
   

2. Axtarış: Hash funksiyası açara tətbiq olunur və hash alınır. Hash, səbət indeksinin müəyyənləşdirilməsi üçün istifadə olunur. Sonra, bu səbətdə, açar ilə element axtarılır. Zəncir metodunda siyahı içində axtarılır. Açıq ünvanlama metodunda isə digər səbətlər ardıcıl yoxlanır, ta ki, lazım olan element tapılsın və ya yoxluğu müəyyən olunsun.

   // Hash cədvəlində elementin axtarışı nümunəsi (zəncir metodu)
   function searchAndDelete(key) {
     const hash = hashFunction(key); // Hash hesablanır
     const bucketIndex = hash % tableSize; // Səbət indeksi müəyyən edilir
   
     if (buckets[bucketIndex]) {
       // Səbətdəki element axtarılır
       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); // Silmək istənilirsə
           return value; // Dəyər qaytarılır
         }
       }
     }
     return undefined; // Element tapılmayıb
   }
   

Üstünlüklər:

• Yüksək sürətli yerləşdirmə, axtarış və silmə əməliyyatları orta hesabla (O(1)).
• Yaddaşın səmərəli istifadəsi, düz ünvan massivinə nisbətən (əgər açarlar yayılmışdırsa).

Çətinliklər:

• Çəkilmə çox olarsa, performans azala bilər (ən pis halda O(n)).
• Elementlərin yerləşdirilmə sırası saxlanmır.
• Açarların bərabər paylanması üçün yaxşı hash funksiyası tələb olunur.

JavaScript-də hash cədvəllər, daxili obyekt Map və tarixi olaraq Object ilə həyata keçirilir. Map üstünlük təşkil edir, çünki hər hansı məlumat tipindən açar istifadə etməyə və elementlərin əlavə olunma sırasını saxlamağa imkan verir. Object isə bütün açarları sətirə çevirir.