Šta je hash tabela?

Hash tabela je struktura podataka koja implementira asocijativni niz (rečnik). Čuva parove "ključ-vrednost", gde su ključevi jedinstveni.

Osnovni principi:

• Hash funkcija: Pretvara ključ u broj (hash kod ili indeks). Ovaj indeks ukazuje na mesto čuvanja vrednosti u nizu (kanta).
• Niz (kante): Stvarno čuvanje parova "ključ-vrednost".
• Kolizije: Situacija kada različiti ključevi generišu isti hash kod.

Rešenje kolizija:

• Metod lančanog povezivanja (Separate chaining): U svakoj kanti se čuva lista (ili druga struktura podataka) elemenata sa istim hash kodom.
• Otvoreno adresiranje (Open addressing): Pri koliziji se traži slobodna kanta koristeći različite strategije (linearnu sondiranje, kvadratno sondiranje, dvostruko hashiranje).

Karakteristike:

• Brz pristup: U idealnom slučaju O(1) za operacije umetanja, pretraživanja i brisanja.
• Zavisnost od hash funkcije: Kvalitet hash funkcije i strategija rešavanja kolizija snažno utiču na performanse.
• Korišćenje memorije: Zahteva dodatnu memoriju za niz kanti.

Upotreba u QA:

• Čuvanje test podataka (ključ - naziv parametra, vrednost - očekivana ili stvarna vrednost).
• Provera jedinstvenosti elemenata (npr. ID-ovi korisnika).
• Implementacija keševa.