Hash tablosu nedir?

Bir hash tablosu veya ilişkisel dizi, anahtarları değerlerle bağlayan, ilişkisel dizinin arayüzünü uygulayan bir veri yapısıdır. Aranan değerin bulunması gereken yerdeki "hash" veya "kova" indeksini hesaplamak için bir hash fonksiyonu kullanır.

Ana bileşenler:

• Anahtar: Öğenin benzersiz tanımlayıcısı.
• Değer: Anahtarla ilişkili veriler.
• Hash fonksiyonu: Anahtarı sayısal bir değere (hash) dönüştürür ve bu, kovanın indeksini belirlemek için kullanılır.
• Kovalar (Buckets): Anahtar-değer çiftlerinin saklandığı dizi.
• Çakışma İşleme: Farklı anahtarların aynı hash değerini üretmesi durumunu çözmek için mekanizma. Yaygın yöntemler:
  • Zincirleme: Her kovada, hashleri bu kovaya işaret eden öğelerin listesi (örneğin, bağlı liste) saklanır.
  • Açık Adresleme: Çakışma durumunda, lineer, kare veya çift hashleme gibi algoritmalar kullanılarak bir sonraki boş kova aranır.

Çalışma prensibi:

1. Ekleme: Hash fonksiyonu, anahtara uygulanır ve hash değeri alınır. Bu hash, kovanın indeksini belirlemek için kullanılır. Anahtar-değer çifti bu kovaya eklenir. Çakışma durumunda, çakışma işleme yöntemi uygulanır.

   // Zincirleme yöntemiyle hash tablosuna öğe ekleme örneği
   function insert(key, value) {
     const hash = hashFunction(key); // Hash hesapla
     const bucketIndex = hash % tableSize; // Kovanın indeksini belirle
   
     if (!buckets[bucketIndex]) {
       buckets[bucketIndex] = []; // Liste oluştur, eğer yoksa
     }
     buckets[bucketIndex].push({ key, value }); // Çifti listeye ekle
   }
   

2. Arama: Hash fonksiyonu, anahtara uygulanır ve hash değeri alınır. Bu hash, kovanın indeksini belirlemek için kullanılır. Daha sonra, bu kovanda, verilen anahtara sahip öğe aranır. Zincirleme yöntemiyle, kovadaki listede arama yapılır. Açık adreslemede, diğer kovalar sıralı olarak kontrol edilir, ta ki öğe bulunana veya yok sayılana kadar.

   // Zincirleme yöntemiyle hash tablosunda arama örneği
   function searchAndDelete(key) {
     const hash = hashFunction(key); // Hash hesapla
     const bucketIndex = hash % tableSize; // Kovanın indeksini belirle
   
     if (buckets[bucketIndex]) {
       // Kova listesindeki öğeyi ara
       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); // Silmek gerekirse
           return value; // Değeri döndür
         }
       }
     }
     return undefined; // Öğe bulunamadı
   }
   

Avantajlar:

• Ekleme, arama ve silme işlemleri ortalama O(1) sürede yüksek hızda.
• Anahtarlar rastgele dağıldığında, doğrudan adresleme dizisine göre daha verimli bellek kullanımı sağlar.

Dezavantajlar:

• Çok sayıda çakışma durumunda performans düşebilir (en kötü durumda O(n)).
• Öğelerin eklenme sırası korunmaz.
• Anahtarların düzgün dağılımını sağlayacak iyi bir hash fonksiyonu gereklidir.

JavaScript'te hash tablolar, yerleşik Map nesnesi ve tarihsel olarak Object kullanılarak uygulanır. Map, herhangi bir veri tipini anahtar olarak kullanmaya izin verdiği ve ekleme sırasını koruduğu için tercih edilir. Object, tüm anahtarları dizelere dönüştürür.