Aký je princíp fungovania hash tabuľky?

Hash tabuľka (alebo asociatívny poľ) ukladá páry "kľúč-hodnota". Princíp fungovania je založený na použití hash funkcie, ktorá premieňa kľúč na číselný index (hash), ktorý ukazuje miesto uloženia hodnoty v poli (koš).

Kroky:

1. Výpočet hashu: Pre daný kľúč sa vypočíta hash.

   <?php
   $key = "example";
   $hash = crc32($key); // Príklad jednoduchej hash funkcie
   

2. Určenie indexu: Hash sa prevedie na index poľa, zvyčajne pomocou operácie modulo veľkosti poľa.

   <?php
   $arraySize = 10;
   $index = $hash % $arraySize;
   

3. Prístup do koša: Prístup k príslušnému košu v poli pomocou vypočítaného indexu.
4. Riešenie kolízií: Pretože rôzne kľúče môžu mať rovnaký hash (kolízia), koš môže obsahovať viacero "kľúč-hodnota" párov. Na riešenie kolízií sa používajú rôzne metódy:
   • Reťazenie (separate chaining): V každom koši sa uchováva zoznam (napríklad spojený zoznam) párov "kľúč-hodnota", ktorých hashe sa zhodujú.
   • Otvárané adresovanie (open addressing): Pri kolízii sa vykonáva opakované hľadanie voľnej bunky v poli podľa určitého pravidla (lineárne, kvadratické, dvojité hashovanie).

Operácie:

• Vkladanie: Vypočíta sa hash kľúča, určí sa index, a pár "kľúč-hodnota" sa umiestni do príslušného koša. Pri kolízii sa pridá do zoznamu (reťazenie) alebo sa hľadá voľné miesto.
• Hľadanie: Vypočíta sa hash kľúča, určí sa index. V príslušnom koši sa hľadá hodnota podľa kľúča. Pri metóde reťazenia prechádzame prvky zoznamu; pri otvorenom adresovaní sa vykonáva sekvenčné hľadanie.
• Odstránenie: Vypočíta sa hash kľúča, určí sa index. V príslušnom koši sa nájde a odstráni pár podľa kľúča.

Výhody:

• Rýchly prístup k prvkom (v priemere O(1)).
• Efektívne využitie pamäti.

Nevýhody:

• Výkon sa môže zhoršiť pri veľkom počte kolízií.
• Veľkosť tabuľky môže vyžadovať úpravu (rehashing) na udržanie efektívnosti.