Co je to hashovací tabulka?

Hashová tabulka (nebo asociativní pole, slovník) je datová struktura, která implementuje rozhraní asociativního pole, tedy umožňuje ukládání párů "klíč-hodnota" a rychlé hledání hodnoty podle klíče.

Princip fungování je založen na použití hashovací funkce, která převádí klíč na index (hash) uvnitř pole (nebo koše).

Hlavní operace:

1. Vložení: Vypočítá se hash klíče a pár "klíč-hodnota" se umístí do odpovídajícího koše.
2. Odstranění: Vypočítá se hash klíče, najde se odpovídající koš a pár se odstraní.
3. Hledání: Vypočítá se hash klíče, najde se odpovídající koš a hledá se pár s požadovaným klíčem.

Hashové tabulky poskytují průměrně vysoký výkon pro operace vkládání, odstraňování a hledání (ideálně $O(1)$). Nicméně v nejhorším případě (při velkém počtu kolizí, kdy různé klíče jsou převedeny na stejný index) může výkon klesnout na $O(n)$.

Existují různé strategie řešení kolizí:

• Metoda řetězení (Separate Chaining): V každém koši je uložen seznam (například spojový seznam) prvků se stejným hash-ovým kódem.
• Otevřená adresace (Open Addressing): Při kolizi se hledá volné místo podle předem určeného algoritmu (lineární, kvadratické zkoušení).

Příklad konceptu (zjednodušeně):

// Příklad zjednodušené hashovací funkce
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; // Převod na 32bitové celé
  }
  return Math.abs(hash) % size;
}

class HashTable {
  constructor(size = 100) {
    this.size = size;
    this.buckets = new Array(size).fill(null).map(() => []); // Metoda řetězení
  }

  insert(key, value) {
    const index = simpleHash(key, this.size);
    // Kontrola existence klíče pro aktualizaci 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; // Klíč nenalezen
  }

  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; // Úspěšně odstraněno
      }
    }
    return false; // Klíč nenalezen
  }
}

// Použití
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 JavaScriptu jsou objekty ({}) a mapy (Map) příklady implementace hash tabulek. Map je často preferovanější, protože podporuje klíče jakéhokoliv typu a zachovává pořadí vložení.

Vlastnosti dobré hashovací funkce:

• Rychlé výpočty.
• Rovnoměrné rozložení hashů pro různé klíče.
• Minimalizace kolizí.