Ce este un tabel hash?

Tabelul hash (sau matrice asociativă, dicționar) este o structură de date care implementează interfața unui array asociativ, adică permite stocarea perechilor "cheie-valoare" și efectuarea unei căutări rapide a valorii după cheie.

Principiul de funcționare se bazează pe utilizarea unei funcții hash, care transformă cheia într-un index (hash) în interiorul array-ului (sau bucket).

Operațiile principale:

1. Inserare: Se calculează hash-ul cheii, iar perechea "cheie-valoare" este plasată în bucket-ul corespunzător.
2. Ștergere: Se calculează hash-ul cheii, se găsește bucket-ul corespunzător și se șterge perechea.
3. Căutare: Se calculează hash-ul cheii, se găsește bucket-ul corespunzător și se caută perechea cu cheia dorită.

Tabelele hash oferă, în medie, performanțe ridicate pentru operațiile de inserare, ștergere și căutare (în mod ideal $O(1)$). Cu toate acestea, în cel mai rău caz (când există multe coliziuni, adică chei diferite care se transformă în același index), performanța poate scădea la $O(n)$.

Există diferite strategii pentru rezolvarea coliziunilor:

• Metoda lanțurilor (Separate Chaining): În fiecare bucket se păstrează o listă (de exemplu, listă înlănțuită) de elemente cu același hash.
• Adresare deschisă (Open Addressing): Când apare o coliziune, se caută un loc liber după un algoritm predefinit (sondare liniară, pătratică etc.).

Exemplu conceptual (simplificat):

// Exemplu de funcție hash simplificată
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; // Transformare în 32-bit
  }
  return Math.abs(hash) % size;
}

class HashTable {
  constructor(size = 100) {
    this.size = size;
    this.buckets = new Array(size).fill(null).map(() => []); // Metoda lanțurilor
  }

  insert(key, value) {
    const index = simpleHash(key, this.size);
    // Verifică dacă cheia există deja pentru actualizarea valorii
    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; // Cheie negăsită
  }

  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; // Șters cu succes
      }
    }
    return false; // Cheie negăsită
  }
}

// Utilizare
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

În JavaScript, obiectele ({}) și hărțile (Map) sunt exemple de implementări ale tabelelor hash. Map este adesea preferat deoarece suportă chei de orice tip și păstrează ordinea inserției.

Proprietățile unei funcții hash bune:

• Calcul rapid.
• Distribuție uniformă a hash-urilor pentru diferite chei.
• Minimizațiile coliziunilor.