Od čega se sastoji hash tabela?

Hash tabela sastoji se od niza fiksne veličine (kanta ili slot) i hash funkcije.

• Niz (Kante/Slotovi): Predstavlja niz ćelija u kojima se čuvaju parovi "ključ-vrednost". Veličina niza određuje broj mogućih mesta za skladištenje elemenata.

• Hash funkcija: Pretvara ključ u celobrojnu vrednost (hash kod), koja se koristi za određivanje indeksa ćelije u nizu (kanti), gde će se čuvati ili odakle će se izvući odgovarajuća vrednost.

Pored toga, može biti prisutno:

• Strategija rešavanja kolizija: Mehanizam za obradu situacija kada različiti ključevi generišu isti hash kod i ukazuju na istu ćeliju niza. Česte strategije:
  • Lančano rešavanje (Separate Chaining): Svaka ćelija niza čuva pokazivač na povezanu listu (ili drugu strukturu podataka), koja sadrži sve parove "ključ-vrednost" čiji hash kodovi ukazuju na tu ćeliju.
  • Otvoreno adresiranje: U slučaju kolizije, traži se slobodna ćelija u nizu prema određenom pravilu (npr. linearno ili kvadratno sondiranje).