Čo je to hashovacia tabuľka?

Hash tabuľka, alebo asociatívny poľ, je dátová štruktúra, ktorá implementuje rozhranie asociatívneho poľa, teda spája kľúče s hodnotami. Používa hashovaciu funkciu na výpočet indexu, alebo "hash", koša alebo slotu, kde by sa mala nachádzať hľadaná hodnota.

Hlavné komponenty:

• Kľúč: Unikátny identifikátor prvku.
• Hodnota: Dáta spojené s kľúčom.
• Hashovacia funkcia: Premení kľúč na číselnú hodnotu (hash), ktorá sa používa na určenie indexu koša.
• Koše (Buckets): Pole, kde sú uložené páry kľúč-hodnota.
• Riešenie kolízií (Collision Handling): Mechanizmus na riešenie situácií, keď rôzne kľúče dávajú rovnaký hash (a teda ukazujú na rovnaký kôš). Časté metódy:
  • Reťazenie (Chaining): V každom koši sa uchováva zoznam (napríklad spojený zoznam) prvkov, ktorých hash ukazuje na tento kôš.
  • Otváraná adresácia (Open Addressing): Pri kolízii sa hľadá ďalší voľný kôš pomocou algoritmov ako lineárne, kvadratické alebo dvojité hashovanie.

Princíp práce:

1. Vloženie: Hashovacia funkcia sa aplikuje na kľúč na získanie hashu. Hash sa používa na určenie indexu koša. Dvojica kľúč-hodnota sa uloží do tohto koša. Pri kolízii sa použije metóda riešenia kolízií.

   // Príklad vloženia prvku do hash tabuľky (reťazenie)
   function insert(key, value) {
     const hash = hashFunction(key); // Výpočet hashu
     const bucketIndex = hash % tableSize; // Určenie indexu koša
   
     if (!buckets[bucketIndex]) {
       buckets[bucketIndex] = []; // Vytvorenie zoznamu, ak neexistuje
     }
     buckets[bucketIndex].push({ key, value }); // Pridanie dvojice do zoznamu
   }
   

2. Hľadanie: Hashovacia funkcia sa aplikuje na kľúč na získanie hashu. Hash sa používa na určenie indexu koša. Potom sa v tomto koši hľadá prvok s daným kľúčom. Pri metóde reťazenia sa hľadá v zozname vnútri koša. Pri otvorenej adresácii sa postupne kontrolujú ďalšie koše, kým sa nenájde požadovaný prvok alebo sa neurčí jeho absencia.

   // Príklad hľadania prvku v hash tabuľke (reťazenie)
   function searchAndDelete(key) {
     const hash = hashFunction(key); // Výpočet hashu
     const bucketIndex = hash % tableSize; // Určenie indexu koša
   
     if (buckets[bucketIndex]) {
       // Hľadanie prvku v zozname koša
       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); // Ak je potrebné vymazanie
           return value; // Vrátenie hodnoty
         }
       }
     }
     return undefined; // Prvok nenájdený
   }
   

Výhody:

• Vysoká rýchlosť operácií vkladania, vyhľadávania a mazania v priemere (O(1)).
• Efektívne využitie pamäte v porovnaní s priamym adresným poľom (ak sú kľúče rozptýlené).

Nevýhody:

• Výkon môže klesnúť pri veľkom počte kolízií (v najhoršom prípade O(n)).
• Poradie vkladania prvkov sa neuchováva.
• Vyžaduje sa dobrá hashovacia funkcia na rovnomerné rozloženie kľúčov.