Koji je princip rada hash tabele?

Hash tabela (ili asocijativni niz) čuva parove "ključ-vrednost". Princip rada zasniva se na korišćenju hash funkcije, koja pretvara ključ u numerički indeks (hash), koji ukazuje na mesto skladištenja vrednosti u nizu (kesa).

Koraci:

1. Izračunavanje hasha: Za dati ključ, izračunava se hash.

   <?php
   $key = "example";
   $hash = crc32($key); // Primer jednostavne hash funkcije
   

2. Određivanje indeksa: Hash se pretvara u indeks niza, obično pomoću operacije modula veličine niza.

   <?php
   $arraySize = 10;
   $index = $hash % $arraySize;
   

3. Pristup kesi: Pristupa se odgovarajućoj kesi u nizu pomoću izračunatog indeksa.
4. Rešavanje kolizija: Pošto različiti ključevi mogu imati isti hash (kolizija), kesi može sadržavati više parova "ključ-vrednost". Za rešavanje kolizija koriste se različite metode:
   • Metod lančanog povezivanja (separate chaining): U svakoj kesi se čuva lista (npr. povezani spisak) parova "ključ-vrednost" čiji hashovi se poklapaju.
   • Otvoreno adresiranje (open addressing): U slučaju kolizije, vrši se ponovo pretraživanje slobodne ćelije u nizu prema određenom pravilu (linearnom, kvadratnom, dvostrukom hashiranju).

Operacije:

• Umetanje: Izračunava se hash ključa, određuje se indeks, i par "ključ-vrednost" se smešta u odgovarajuću kesi. U slučaju kolizije, dodaje se u listu (lanac) ili traži slobodno mesto.
• Pretraživanje: Izračunava se hash ključa, određuje se indeks. U odgovarajućoj kesi, traži se vrednost po ključu. Kod metode lančanog povezivanja, prolaze se elementi liste; kod otvorenog adresiranja, vrši se sekvencijalno pretraživanje.
• Brisanje: Izračunava se hash ključa, određuje se indeks. U odgovarajućoj kesi, nalazi se i briše par po ključu.

Prednosti:

• Brz pristup elementima (prosečno O(1)).
• Efikasno korišćenje memorije.

Nedostaci:

• Performanse mogu da se pogoršaju pri velikom broju kolizija.
• Veličina tabele može zahtevati prilagođavanje (rehashing) radi održavanja efikasnosti.