Od kojih komponenti se sastoji hash tabela?

Hash tabela se sastoji od:

1. Niz (ili lista): Glavna struktura podataka u kojoj se čuvaju elementi. Ponekad se nazivaju "kante" (buckets) ili "slotovi".
2. Hash funkcija: Funkcija koja prima ključ kao ulaz i vraća indeks (celobrojnu vrednost) u nizu. Dobra hash funkcija obezbeđuje ravnomernu raspodelu ključeva po nizu, minimizirajući kolizije.
3. Mehanizam za rešavanje kolizija: Metod za rešavanje situacije kada hash funkcija generiše isti indeks za različite ključeve. Dva glavna metoda:
   • Razdvajanje lanaca (Separate Chaining): Svaki element niza čuva pokazivač na listu (spojenu listu, B-stablo itd.) elemenata koji su hash-ovani na taj indeks.
   • Otvorena adresacija (Open Addressing): U slučaju kolizije, traži se drugo slobodno mesto u nizu za smeštanje elementa. Strategije pretraživanja:
     • Linearno sondiranje (Linear Probing)
     • Kvadratno sondiranje (Quadratic Probing)
     • Dvostruko hashiranje (Double Hashing)
4. Operacije: Implementacija osnovnih operacija: umetanje (insert), pretraživanje (search), brisanje (delete). Ove operacije koriste hash funkciju za određivanje mesta elemenata u nizu i mehanizam za rešavanje kolizija po potrebi.