Kuidas hinnata elemendi sisestamise operatsiooni tõhusust hajutustabelis erinevates tingimustes?

Hash-tabeli elementide lisamise tõhusus sõltub mitmest tegurist:

1. Laadimistegur (load factor) — suhe elementide arvu ja massiivi suuruse vahel. Madala laadimise korral toimub lisamine tavaliselt amortiseeritud ajaga O(1).

2. Hash-funktsiooni kvaliteet — ühtlane võtmete jaotus minimeerib kokkupõrked.

3. Kokkupõrked:

   • Kettide (chaining) meetodil lisamine tähendab lisamist seotud nimekirja või muu konteineri külge. Keskmiselt O(1), kuid halvim juhul O(n), kui kõik elemendid satuvad sama keti.
   • Avatud aadressimise (lineaarne otsing, kvadratiivne otsing) puhul võib lisamine nõuda vaba koha otsimist, mis suurendab aega suure laadimise korral.

4. Rehashing — kui saavutatakse laadimiskünnis, laieneb tabel, mis nõuab elementide ümberjaotamist ja ajutiselt suurendab lisamise aega.

Kokkuvõte: hea hash-funktsiooni ja mõõduka laadimise korral on lisamine amortiseerunud O(1). Kõrge laadimise või halva hash-funktsiooni korral võib aeg halveneda kuni O(n)-ni.