Šta je hash tabela?

Hash tabela, ili asocijativni niz, je struktura podataka koja implementira interfejs asocijativnog niza, odnosno povezuje ključeve sa vrednostima. Koristi hash funkciju za izračunavanje indeksa, ili "haša", korpe ili slotova, gde bi trebalo da se nalazi tražena vrednost.

Glavne komponente:

• Ključ: Jedinstveni identifikator elementa.
• Vrednost: Podaci povezani sa ključem.
• Hash funkcija: Pretvara ključ u numeričku vrednost (hash), koja se koristi za određivanje indeksa korpe.
• Korpe (Buckets): Niz u kojem se čuvaju parovi ključ-vrednost.
• Rešavanje kolizija (Collision Handling): Mehanizam za rešavanje situacija kada različiti ključevi daju isti hash (i, shodno tome, ukazuju na istu korpu). Česte metode:
  • Lančano rešenje (Chaining): U svakoj korpi se čuva lista (npr. povezani spisak) elemenata čiji hash ukazuje na tu korpu.
  • Otvorena adresacija (Open Addressing): Pri koliziji se traži sledeća slobodna korpa korišćenjem algoritama kao što su linearno, kvadratno ili dvostruko hashiranje.

Princip rada:

1. Ubacivanje: Hash funkcija se primenjuje na ključ za dobijanje haša. Hash se koristi za određivanje indeksa korpe. Par ključ-vrednost se smešta u tu korpu. Pri koliziji se primenjuje metoda rešavanja kolizija.

   // Primer ubacivanja elementa u hash tabelu (lančano rešenje)
   function insert(key, value) {
     const hash = hashFunction(key); // Izračunavanje haša
     const bucketIndex = hash % tableSize; // Određivanje indeksa korpe
   
     if (!buckets[bucketIndex]) {
       buckets[bucketIndex] = []; // Kreiranje liste ako ne postoji
     }
     buckets[bucketIndex].push({ key, value }); // Dodavanje para u listu
   }
   

2. Pretraživanje: Hash funkcija se primenjuje na ključ za dobijanje haša. Hash se koristi za određivanje indeksa korpe. Zatim se u toj korpi traži element sa datim ključem. Kod lančanog rešenja se traži u listi unutar korpe. Kod otvorene adresacije se sukcesivno proveravaju druge korpe dok se ne pronađe željeni element ili se ne utvrdi njegov nedostatak.

   // Primer pretraživanja elementa u hash tabeli (lančano rešenje)
   function searchAndDelete(key) {
     const hash = hashFunction(key); // Izračunavanje haša
     const bucketIndex = hash % tableSize; // Određivanje indeksa korpe
   
     if (buckets[bucketIndex]) {
       // Traženje elementa u listi korpe
       for (let i = 0; i < buckets[bucketIndex].length; i++) {
         if (buckets[bucketIndex][i].key === key) {
           const value = buckets[bucketIndex][i].value;
           // buckets[bucketIndex].splice(i, 1); // Ako je potrebno brisanje
           return value; // Vraćanje vrednosti
         }
       }
     }
     return undefined; // Element nije pronađen
   }
   

Prednosti:

• Visoka brzina operacija ubacivanja, pretraživanja i brisanja u proseku (O(1)).
• Efikasno korišćenje memorije u poređenju sa direktnim pristupnim nizom (ako su ključevi retko raspoređeni).

Nedostaci:

• Performanse mogu opasti u slučaju velikog broja kolizija (u najgorem slučaju O(n)).
• Redosled ubacivanja elemenata se ne čuva.
• Potrebna je dobra hash funkcija za ravnomerno raspoređivanje ključeva.