Ako sa hodnotí efektívnosť operácie vloženia prvku do hash tabuľky za rôznych podmienok?

Efektivita operácie vloženia prvku do hash tabuľky závisí od niekoľkých faktorov:

1. Zaťaženie tabuľky (load factor) — pomer medzi počtom prvkov a veľkosťou poľa. Pri nízkom zaťažení sa vloženie zvyčajne vykonáva v amortizovanom čase O(1).

2. Kvalita hash funkcie — rovnomerné rozloženie kľúčov minimalizuje kolízie.

3. Riešenie kolízií:

   • Pri reťazení (chaining) je vloženie pridaním do spojového zoznamu alebo iného kontajnera v koši. Priemerné O(1), ale v najhoršom prípade O(n), ak všetky prvky skončia v jednom koši.
   • Pri otvorenom adresovaní (lineárne sondovanie, kvadratické sondovanie) môže vloženie vyžadovať hľadanie voľného miesta, čo zvyšuje čas pri vysokom zaťažení.

4. Rehashing — keď sa dosiahne prah zaťaženia, tabuľka sa rozšíri, čo vyžaduje preusporiadanie prvkov a dočasne zvyšuje čas vloženia.

Zhrnutie: pri dobrej hash funkcii a miernom zaťažení je vloženie amortizované v O(1). Pri vysokom zaťažení alebo zlej hash funkcii sa čas môže zhoršiť na O(n).