Czym jest tablica haszująca?

Tablica haszowa, czyli tablica asocjacyjna, to struktura danych implementująca interfejs tablicy asocjacyjnej, czyli łączy klucze z wartościami. Używa funkcji hash do obliczenia indeksu, czyli "hasza", kosza lub slotu, w którym powinna się znajdować poszukiwana wartość.

Główne składniki:

• Klucz: Unikalny identyfikator elementu.
• Wartość: Dane powiązane z kluczem.
• Funkcja hash: Zamienia klucz na wartość numeryczną (hash), która jest używana do określenia indeksu kosza.
• Kosze (Buckets): Tablica, w której przechowywane są pary klucz-wartość.
• Obsługa kolizji: Mechanizm rozwiązywania sytuacji, gdy różne klucze dają ten sam hash (i wskazują na ten sam kosz). Popularne metody:
  • Łańcuchowanie: W każdym koszu przechowywana jest lista (np. lista powiązana) elementów, których hasze wskazują na ten kosz.
  • Otwarte adresowanie: W przypadku kolizji szuka się następnego wolnego kosza za pomocą algorytmów takich jak liniowe, kwadratowe lub podwójne haszowanie.

Zasada działania:

1. Wstawianie: Funkcja hash jest stosowana do klucza, aby uzyskać hash. Hash jest używany do określenia indeksu kosza. Para klucz-wartość jest przechowywana w tym koszu. W przypadku kolizji stosuje się metodę obsługi kolizji.

   // Przykład wstawiania elementu do tablicy haszowej (łańcuchowanie)
   function insert(key, value) {
     const hash = hashFunction(key); // Oblicz hash
     const bucketIndex = hash % tableSize; // Określ indeks kosza
   
     if (!buckets[bucketIndex]) {
       buckets[bucketIndex] = []; // Tworzymy listę, jeśli jeszcze nie istnieje
     }
     buckets[bucketIndex].push({ key, value }); // Dodaj parę do listy
   }
   

2. Wyszukiwanie: Funkcja hash jest stosowana do klucza, aby uzyskać hash. Hash jest używany do określenia indeksu kosza. Następnie w tym koszu wyszukiwany jest element z podanym kluczem. Przy użyciu metody łańcuchowania, szuka się na liście wewnątrz kosza. Przy otwartym adresowaniu, kolejno sprawdzane są inne kosze, aż zostanie znaleziony potrzebny element lub zostanie ustalone jego braku.

   // Przykład wyszukiwania elementu w tablicy haszowej (łańcuchowanie)
   function searchAndDelete(key) {
     const hash = hashFunction(key); // Oblicz hash
     const bucketIndex = hash % tableSize; // Określ indeks kosza
   
     if (buckets[bucketIndex]) {
       // Szukaj elementu na liście kosza
       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); // Jeśli konieczne usunięcie
           return value; // Zwracamy wartość
         }
       }
     }
     return undefined; // Element nie znaleziony
   }
   

Zalety:

• Szybkie operacje wstawiania, wyszukiwania i usuwania w średnim czasie (O(1)).
• Efektywne wykorzystanie pamięci w porównaniu do tablicy bezpośredniego adresowania (jeśli klucze są rozproszone).

Wady:

• Wydajność może się obniżyć przy dużej liczbie kolizji (w najgorszym przypadku O(n)).
• Kolejność wstawiania elementów nie jest zachowywana.
• Wymaga dobrej funkcji hash do równomiernego rozkładu kluczy.

W JavaScript, tablice haszowe są implementowane za pomocą wbudowanego obiektu Map i historycznie Object. Map jest preferowany, ponieważ pozwala na używanie dowolnych typów danych jako kluczy i zachowuje kolejność dodawania elementów. Object konwertuje wszystkie klucze na łańcuchy.