Co je to hashovací tabulka?

Hash tabulka, nebo asociativní pole, je datová struktura, která implementuje rozhraní asociativního pole, tedy spojuje klíče s hodnotami. Používá hashovací funkci k výpočtu indexu, nebo "haše", koše nebo slotu, kde by měla být hledaná hodnota.

Hlavní komponenty:

• Klíč: Unikátní identifikátor prvku.
• Hodnota: Data spojená s klíčem.
• Hashovací funkce: Převádí klíč na číselnou hodnotu (hash), která se používá k určení indexu koše.
• Koše (Buckets): Pole, kde jsou uloženy páry klíč-hodnota.
• Řešení kolizí (Collision Handling): Mechanismus řešení situací, kdy různé klíče dávají stejný hash (a tedy odkazují na stejný koš). Časté metody:
  • Řetězení (Chaining): V každém koši je seznam (například spojový seznam) prvků, jejichž hash ukazuje na tento koš.
  • Otevřená adresace (Open Addressing): Při kolizi se hledá další volný koš pomocí algoritmů jako lineární, kvadratické nebo dvojité hashování.

Princip práce:

1. Vložení: Hashovací funkce se aplikuje na klíč pro získání hashe. Hash se používá k určení indexu koše. Pár klíč-hodnota je uložen v tomto koši. Při kolizi se použije metoda řešení kolizí.

   // Příklad vložení prvku do hash tabulky (metoda řetězení)
   function insert(key, value) {
     const hash = hashFunction(key); // Výpočet hashe
     const bucketIndex = hash % tableSize; // Určení indexu koše
   
     if (!buckets[bucketIndex]) {
       buckets[bucketIndex] = []; // Vytvoření seznamu, pokud neexistuje
     }
     buckets[bucketIndex].push({ key, value }); // Přidání páru do seznamu
   }
   

2. Hledání: Hashovací funkce se aplikuje na klíč pro získání hashe. Hash se používá k určení indexu koše. Poté se v tomto koši hledá prvek s daným klíčem. U metody řetězení se hledá v seznamu uvnitř koše. U otevřené adresace se postupně kontrolují další koše, dokud se nenajde požadovaný prvek nebo se neurčí jeho absence.

   // Příklad hledání prvku v hash tabulce (metoda řetězení)
   function searchAndDelete(key) {
     const hash = hashFunction(key); // Výpočet hashe
     const bucketIndex = hash % tableSize; // Určení indexu koše
   
     if (buckets[bucketIndex]) {
       // Hledání prvku v seznamu koše
       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); // Pokud je potřeba smazat
           return value; // Vrácení hodnoty
         }
       }
     }
     return undefined; // Prvek nenalezen
   }
   

Výhody:

• Vysoká rychlost operací vkládání, hledání a mazání v průměru (O(1)).
• Efektivní využití paměti ve srovnání s přímým adresním polem (pokud jsou klíče rozptýlené).

Nevýhody:

• Výkon může klesnout při velkém počtu kolizí (v nejhorším případě O(n)).
• Není zachována pořadí vkládání prvků.
• Vyžaduje dobrou hashovací funkci pro rovnoměrné rozložení klíčů.