Jaký je princip fungování hashovací tabulky?

Hashtabulka (nebo asociativní pole) ukládá páry "klíč-hodnota". Princip fungování je založen na použití hash funkce, která převádí klíč na číselný index (hash), který ukazuje místo uložení hodnoty v poli (koš).

Kroky:

1. Výpočet hashe: Pro daný klíč se vypočítá hash.

   <?php
   $key = "example";
   $hash = crc32($key); // Příklad jednoduché hash funkce
   

2. Určení indexu: Hash se převede na index pole, obvykle pomocí operace modulo velikosti pole.

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

3. Přístup do koše: Přístup k odpovídajícímu koši v poli pomocí vypočteného indexu.
4. Řešení kolizí: Protože různé klíče mohou mít stejný hash (kolize), může koš obsahovat více párů "klíč-hodnota". Pro řešení kolizí se používají různé metody:
   • Řetězení (separate chaining): V každém koši je uložen seznam (například spojovaný seznam) párů "klíč-hodnota", jejichž hashe se shodují.
   • Otevřené adresování (open addressing): Při kolizi se opakovaně hledá volná buňka v poli podle určitého pravidla (lineární, kvadratické, dvojité hashování).

Operace:

• Vložení: Vypočítá se hash klíče, určí se index a pár "klíč-hodnota" se umístí do odpovídajícího koše. Při kolizi se přidá do seznamu (řetězení) nebo hledá volné místo.
• Hledání: Vypočítá se hash klíče, určí se index. V odpovídajícím koši se hledá hodnota podle klíče. U metody řetězení prohledáváme prvky seznamu; u otevřeného adresování provádíme sekvenční hledání.
• Odstranění: Vypočítá se hash klíče, určí se index. V odpovídajícím koši se najde a odstraní pár podle klíče.

Výhody:

• Rychlý přístup k prvkům (průměrně O(1)).
• Efektivní využití paměti.

Nevýhody:

• Výkon se může zhoršit při velkém počtu kolizí.
• Velikost tabulky může vyžadovat úpravu (rehashing) pro udržení efektivity.