Hash tablosu nedir?

Bir hash tablosu (veya ilişkilendirilmiş dizi, sözlük) anahtar-değer çiftlerini depolamaya ve anahtar kullanarak hızlı arama yapmaya olanak tanıyan bir veri yapısıdır.

Çalışma prensibi, anahtarı bir indeks (hash) haline dönüştüren bir hash fonksiyonunun kullanılmasına dayanır ve bu indeks, dizinin (veya bucket) içindedir.

Ana operasyonlar:

1. Ekleme: Anahtarın hash değeri hesaplanır ve "anahtar-değer" çifti uygun buckete yerleştirilir.
2. Silme: Anahtarın hash değeri hesaplanır, ilgili bucket bulunur ve çift silinir.
3. Arama: Anahtarın hash değeri hesaplanır, ilgili bucket bulunur ve aranan anahtara sahip çift aranır.

Hash tabloları, ortalama olarak yüksek performans sağlar; ekleme, silme ve arama işlemleri için (ideal durumda $O(1)$). Ancak, en kötü durumda (çok sayıda çakışma olduğunda, yani farklı anahtarların aynı index’e dönüştüğü durumlarda) performans $O(n)$ seviyesine düşebilir.

Çakışmaları çözmek için çeşitli stratejiler vardır:

• Bağlantı Yöntemi (Separate Chaining): Her buckette, aynı hash değerine sahip öğeleri tutan bir liste (örneğin, bağlı liste) bulunur.
• Açık Adresleme (Open Addressing): Çakışma durumunda, boş bir yer arama işlemi önceden belirlenmiş bir algoritma ile yapılır (doğrusal, kareli sondalama vb.).

Basit bir kavramsal örnek (sadelestirilmiş):

// Basit bir hash fonksiyonu örneği
function simpleHash(key, size) {
  let hash = 0;
  for (let i = 0; i < key.length; i++) {
    hash = (hash << 5) + hash + key.charCodeAt(i);
    hash = hash & hash; // 32-bit tam sayıya dönüştürme
  }
  return Math.abs(hash) % size;
}

class HashTable {
  constructor(size = 100) {
    this.size = size;
    this.buckets = new Array(size).fill(null).map(() => []); // Bağlantı Yöntemi
  }

  insert(key, value) {
    const index = simpleHash(key, this.size);
    // Anahtarın zaten var olup olmadığını kontrol et ve güncelle
    for (let i = 0; i < this.buckets[index].length; i++) {
      if (this.buckets[index][i][0] === key) {
        this.buckets[index][i][1] = value;
        return;
      }
    }
    this.buckets[index].push([key, value]);
  }

  get(key) {
    const index = simpleHash(key, this.size);
    for (let i = 0; i < this.buckets[index].length; i++) {
      if (this.buckets[index][i][0] === key) {
        return this.buckets[index][i][1];
      }
    }
    return undefined; // Anahtar bulunamadı
  }

  delete(key) {
    const index = simpleHash(key, this.size);
    for (let i = 0; i < this.buckets[index].length; i++) {
      if (this.buckets[index][i][0] === key) {
        this.buckets[index].splice(i, 1);
        return true; // Başarıyla silindi
      }
    }
    return false; // Anahtar bulunamadı
  }
}

// Kullanım
const myHashTable = new HashTable(50);
myHashTable.insert("apple", 10);
myHashTable.insert("banana", 20);
console.log(myHashTable.get("apple")); // 10
myHashTable.delete("banana");
console.log(myHashTable.get("banana")); // undefined

JavaScript'te nesneler ({}) ve haritalar (Map) hash tablolarının örnekleridir. Map, herhangi bir türde anahtar desteklediği ve ekleme sırasını koruduğu için genellikle tercih edilir.

İyi bir hash fonksiyonunun özellikleri:

• Hızlı hesaplama.
• Farklı anahtarlar için eşit dağılım.
• Çakışmaların en aza indirilmesi.