Care este viteza de funcționare a tabelului de dispersie?

Viteza de lucru a unui tabel hash, sau timpul de acces la date (căutare, inserare, ștergere), în cazul ideal este O(1) — constant.

Acest lucru se realizează prin utilizarea unei funcții hash care transformă rapid cheia într-un index al array-ului.

Viteza reală depinde de:

• Calitatea funcției hash: O funcție bună distribuie uniform cheile, minimizând coliziunile.
• Strategiile de rezolvare a coliziunilor:
  • Chaining separat (separate chaining): În cazul unei coliziuni, elementele cu același hash sunt stocate într-o listă legată sau într-un alt array dinamic. Timpul de acces poate ajunge la O(N) în cel mai rău caz (toate elementele în același "coș"), unde N este numărul de elemente.
  • Adresare deschisă (open addressing): În cazul unei coliziuni, se caută următoarea celulă liberă în array. Timpul de acces poate să se înrăutățească cu multe coliziuni.
• Factorul de încărcare (load factor): Raportul dintre numărul de elemente și dimensiunea tabelului hash. Un factor de încărcare ridicat crește probabilitatea de coliziuni și încetinește performanța. Când se atinge un anumit prag, este necesară rehashing-ul (mărirea dimensiunii tabelului și recalcularea hash-urilor pentru toate elementele), ceea ce reprezintă o operație relativ costisitoare (O(N)).

Prin urmare, deși viteza teoretică O(1) este cel mai bun caz, în practică poate fi ușor mai mare din cauza coliziunilor și a necesității de rehashing, mai ales cu volume mari de date sau funcții hash neoptime.