Czym jest tablica haszująca?

Tablica haszowa (lub tablica asocjacyjna, słownik) to struktura danych, która implementuje interfejs tablicy asocjacyjnej, czyli pozwala na przechowywanie par "klucz-wartość" i szybkie wyszukiwanie wartości po kluczu.

Zasada działania opiera się na użyciu funkcji haszującej, która zamienia klucz na indeks (hash) w obrębie tablicy (lub kubełka).

Podstawowe operacje:

1. Wstawianie: Oblicza się hash klucza, a para "klucz-wartość" jest umieszczana w odpowiednim kubełku.
2. Usuwanie: Oblicza się hash klucza, znajduje odpowiedni kubełek i usuwa parę.
3. Wyszukiwanie: Oblicza się hash klucza, znajduje odpowiedni kubełek i szuka pary z poszukiwanym kluczem.

Tablice haszujące zapewniają średnio wysoką wydajność dla operacji wstawiania, usuwania i wyszukiwania (w idealnym przypadku $O(1)$). Jednak w najgorszym przypadku (przy dużej liczbie kolizji, gdy różne klucze zamieniane są na ten sam indeks) wydajność może spaść do $O(n)$.

Istnieją różne strategie rozwiązywania kolizji:

• Metoda łańcuchowa (Separate Chaining): W każdym kubełku przechowywana jest lista (np. lista powiązana) elementów o tym samym haszu.
• Otwarte adresowanie (Open Addressing): Gdy występuje kolizja, poszukiwanie wolnego miejsca odbywa się według z góry określonego algorytmu (sondowanie liniowe, kwadratowe itp.).

Przykład koncepcyjny (uproszczony):

// Przykład uproszczonej funkcji haszującej
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; // Konwersja na 32-bitową liczbę całkowitą
  }
  return Math.abs(hash) % size;
}

class HashTable {
  constructor(size = 100) {
    this.size = size;
    this.buckets = new Array(size).fill(null).map(() => []); // Metoda łańcuchowa
  }

  insert(key, value) {
    const index = simpleHash(key, this.size);
    // Sprawdzenie, czy klucz już istnieje do aktualizacji wartości
    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; // Klucz nie znaleziony
  }

  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; // Usunięto pomyślnie
      }
    }
    return false; // Klucz nie znaleziony
  }
}

// Użycie
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

W JavaScript obiekty ({}) i mapy (Map) są przykładami implementacji tablic haszujących. Map jest często preferowany, ponieważ obsługuje klucze dowolnego typu i zachowuje kolejność wstawiania.

Właściwości dobrej funkcji haszującej:

• Szybkie obliczanie.
• Równomierne rozłożenie hashy dla różnych kluczy.
• Minimalizacja kolizji.