Koliko je brzina rada hash tabele?

Brzina rada hash tabele, ili vreme pristupa podacima (pretraga, umetanje, brisanje), u idealnom slučaju je O(1) — konstantno.

Ovo se postiže korišćenjem hash funkcije koja brzo pretvara ključ u indeks niza.

Stvarna brzina zavisi od:

• Kvaliteta hash funkcije: Dobra funkcija ravnomerno raspoređuje ključeve, minimizirajući kolizije.
• Strategija rešavanja kolizija:
  • Odvojeni lanac (separate chaining): U slučaju kolizije, elementi sa istim hash-om se čuvaju u povezanoj listi ili drugom dinamičkom nizu. Vreme pristupa može biti u najgorem slučaju O(N) (svi elementi u "kanti"), gde je N broj elemenata.
  • Otvoreno adresiranje (open addressing): U slučaju kolizije, traži se sledeće slobodno mesto u nizu. Vreme pristupa može se pogoršati sa mnogo kolizija.
• Faktor opterećenja (load factor): Odnos između broja elemenata i veličine hash tabele. Visok faktor opterećenja povećava verovatnoću kolizija i usporava rad. Kada se dostigne određeni prag, potrebno je rehashing (povećanje veličine tabele i recalculacija hash-ova za sve elemente), što je relativno skupa operacija (O(N)).

Dakle, iako je teoretska brzina O(1) najbolji slučaj, u praksi može biti nešto viša zbog kolizija i potrebe za rehashingom, posebno sa velikim količinama podataka ili neefikasnim hash funkcijama.