Jak działa tablica haszująca?

Tablica haszująca (hash table) to struktura danych implementująca tablicę asocjacyjną.

Zasada działania:

1. Hashowanie. Dla każdego klucza (key) oblicza się kod hash (hash code) za pomocą funkcji hash (hash function). Kod hash jest liczbą całkowitą.
2. Indeksowanie. Kod hash służy do określenia indeksu (index) w tablicy (lub wektorze) struktury wewnętrznej tablicy haszującej. Zazwyczaj indeks oblicza się jako hash_code % rozmiar_tablicy, gdzie rozmiar_tablicy to rozmiar tablicy.
3. Przechowywanie. Pod wskazanym indeksem przechowywana jest wartość (value) powiązana z kluczem.

Problemy i ich rozwiązania:

• Kolizje. Różne klucze mogą dawać ten sam kod hash, a co za tym idzie, ten sam indeks w tablicy. Nazywa się to kolizją.
  • Metody rozwiązywania kolizji:
    • Metoda łańcuchowa (Separate Chaining): W każdej komórce tablicy przechowuje się listę (listę, wektor, itp.) par "klucz-wartość". W przypadku kolizji nowa para jest dodawana do tej listy. Podczas wyszukiwania po indeksie przeszukuje się odpowiednią listę, aby znaleźć poszukiwany klucz.
    • Metoda otwartego adresowania (Open Addressing): W przypadku kolizji szuka się innej wolnej komórki w tablicy według określonej reguły (sondowanie).
      • Sondowanie liniowe (Linear Probing): Sprawdzane są kolejno komórki index + 1, index + 2, itd., modulo rozmiar tablicy.
      • Sondowanie kwadratowe (Quadratic Probing): Sprawdzane są komórki index + 1^2, index + 2^2, itd., modulo rozmiar tablicy.
      • Podwójne haszowanie (Double Hashing): Używa się drugiej funkcji hash do określenia kroku sondowania.

Zalety:

• Średnio operacje wstawiania, usuwania i wyszukiwania wykonują się z złożonością O(1).

Wady:

• W najgorszym przypadku (np. przy dużej liczbie kolizji lub złej funkcji hash) złożoność operacji może sięgać O(n), gdzie n to liczba elementów.
• Wymaga dodatkowej pamięci (np. dla list w metodzie łańcuchowej lub dla sondowania w metodzie otwartego adresowania).

Przykład użycia w C++ (std::unordered_map):

#include <unordered_map>
#include <string>
#include <iostream>

int main() {
    // Tworzenie tablicy haszującej (unordered_map)
    std::unordered_map<std::string, int> wiek;

    // Wstawianie elementów
    wiek["Alice"] = 30;
    wiek["Bob"] = 25;
    wiek["Charlie"] = 35;

    // Pobieranie wartości po kluczu
    std::cout << "Wiek Alice: " << wiek["Alice"] << std::endl;

    // Szukanie elementu
    if (wiek.count("Bob")) {
        std::cout << "Bob jest w mapie." << std::endl;
    }

    // Usuwanie elementu
    wiek.erase("Charlie");

    return 0;
}