Šta je hash tabela?

Hash tabela (или asocijativni niz, rečnik) je struktura podataka koja implementira interfejs asocijativnog niza, odnosno omogućava skladištenje parova "ključ-vrednost" i brzo pretraživanje vrednosti po ključu.

Princip rada zasniva se na korišćenju hash funkcije, koja pretvara ključ u indeks (hash) unutar niza (ili kante).

Osnovne operacije:

1. Ubacivanje: Izračunava se hash ključa, i par "ključ-vrednost" se smešta u odgovarajuću kantu.
2. Brisanje: Izračunava se hash ključa, nalazi se odgovarajuća kanta, i par se briše.
3. Pretraživanje: Izračunava se hash ključa, nalazi se odgovarajuća kanta, i traži se par sa željenim ključem.

Hash tabele obezbeđuju prosečno visok performans za operacije ubacivanja, brisanja i pretraživanja (idealno $O(1)$). Međutim, u najgorem slučaju (pri velikom broju kolizija, kada različiti ključevi dobijaju isti indeks) performans može opasti na $O(n)$.

Postoje različite strategije rešavanja kolizija:

• Metod lančanica (Separate Chaining): U svakoj kanti se čuva lista (npr. povezani spisak) elemenata sa istim hash-om.
• Otvorena adresacija (Open Addressing): Pri koliziji, traži se slobodno mesto prema unapred definisanom algoritmu (linearna, kvadratna sondiranje).

Primer koncepta (pojednostavljeno):

// Pojednostavljena hash funkcija
function simpleHash(key, size) {
  let hash = 0;
  for (let i = 0; i < key.length; i++) {
    hash = (hash << 5) + hash + key.charCodeAt(i);
    hash = hash & hash; // Pretvaranje u 32-bitni ceo broj
  }
  return Math.abs(hash) % size;
}

class HashTable {
  constructor(size = 100) {
    this.size = size;
    this.buckets = new Array(size).fill(null).map(() => []); // Metod lančanica
  }

  insert(key, value) {
    const index = simpleHash(key, this.size);
    // Provera postojanja ključa za ažuriranje vrednosti
    for (let i = 0; i < this.buckets[index].length; i++) {
      if (this.buckets[index][i][0] === key) {
        this.buckets[index][i][1] = value;
        return;
      }
    }
    this.buckets[index].push([key, value]);
  }

  get(key) {
    const index = simpleHash(key, this.size);
    for (let i = 0; i < this.buckets[index].length; i++) {
      if (this.buckets[index][i][0] === key) {
        return this.buckets[index][i][1];
      }
    }
    return undefined; // Ključ nije pronađen
  }

  delete(key) {
    const index = simpleHash(key, this.size);
    for (let i = 0; i < this.buckets[index].length; i++) {
      if (this.buckets[index][i][0] === key) {
        this.buckets[index].splice(i, 1);
        return true; // Uspešno obrisano
      }
    }
    return false; // Ključ nije pronađen
  }
}

// Upotreba
const myHashTable = new HashTable(50);
myHashTable.insert("apple", 10);
myHashTable.insert("banana", 20);
console.log(myHashTable.get("apple")); // 10
myHashTable.delete("banana");
console.log(myHashTable.get("banana")); // undefined

U JavaScript-u, objekti ({}) i mape (Map) su primeri implementacije hash tabela. Map je često preferiran jer podržava ključeve bilo kog tipa i čuva redosled umetanja.

Osobine dobre hash funkcije:

• Brza izračunavanja.
• Ujednačena raspodela hash vrednosti za različite ključeve.
• Minimizacija kolizija.