Čo je hash tabuľka?

Hash tabuľka (alebo asociatívny poľ, slovník) je dátová štruktúra, ktorá implementuje rozhranie asociatívneho poľa, teda umožňuje uloženie dvojíc "kľúč-hodnota" a rýchle vyhľadávanie hodnoty podľa kľúča.

Princíp fungovania je založený na použití hashovacej funkcie, ktorá premieňa kľúč na index (hash) v rámci poľa (alebo vedra).

Hlavné operácie:

1. Vloženie: Vypočíta sa hash kľúča a dvojica "kľúč-hodnota" sa umiestni do príslušného vedra.
2. Odstránenie: Vypočíta sa hash kľúča, nájde sa príslušné vedro a dvojica sa odstráni.
3. Hľadanie: Vypočíta sa hash kľúča, nájde sa príslušné vedro a hľadá sa dvojica s požadovaným kľúčom.

Hash tabuľky poskytujú priemerné vysoký výkon pre operácie vkladania, odstraňovania a hľadania (v ideálnom prípade $O(1)$). Avšak v najhoršom prípade (pri veľkom počte kolízií, keď rôzne kľúče sa preklápajú na rovnaký index) môže výkon klesnúť na $O(n)$.

Existujú rôzne stratégie riešenia kolízií:

• Metóda reťazcov (Separate Chaining): V každom vedre sa uchováva zoznam (napríklad spojený zoznam) prvkov s rovnakým hashom.
• Otváraná adresácia (Open Addressing): Pri kolízii sa hľadá voľné miesto podľa vopred určeného algoritmu (lineárne, kvadratické sondovanie).

Príklad konceptu (zjednodušene):

// Zjednodušená hashovacia funkcia
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; // Prevod na 32-bitové celé
  }
  return Math.abs(hash) % size;
}

class HashTable {
  constructor(size = 100) {
    this.size = size;
    this.buckets = new Array(size).fill(null).map(() => []); // Metóda reťazcov
  }

  insert(key, value) {
    const index = simpleHash(key, this.size);
    // Kontrola existencie kľúča na aktualizáciu hodnoty
    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; // Kľúč nenájdený
  }

  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; // Úspešne odstránené
      }
    }
    return false; // Kľúč nenájdený
  }
}

// Použitie
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

V JavaScript objekty ({}) a mapy (Map) sú príkladmi implementácie hash tabuliek. Map je často preferovaná, pretože podporuje kľúče akéhokoľvek typu a zachováva poradie vloženia.

Vlastnosti dobrej hash funkcie:

• Rýchle výpočty.
• Rovnomerné rozloženie hashov pre rôzne kľúče.
• Minimalizácia kolízií.