Na czym polega zasada działania tablicy haszującej?

Tablica haszująca (lub tablica asocjacyjna) przechowuje pary "klucz-wartość". Zasada działania opiera się na użyciu funkcji haszującej, która zamienia klucz na indeks numeryczny (hash), wskazujący miejsce przechowywania wartości w tablicy (koszu).

Kroki:

1. Obliczanie hasza: Dla podanego klucza oblicza się hash.

   <?php
   $key = "example";
   $hash = crc32($key); // Przykład prostej funkcji haszującej
   

2. Określenie indeksu: Hash jest przekształcany na indeks tablicy, zwykle za pomocą operacji modulo rozmiaru tablicy.

   <?php
   $arraySize = 10;
   $index = $hash % $arraySize;
   

3. Dostęp do kosza: Uzyskuje się dostęp do odpowiedniego kosza w tablicy za pomocą obliczonego indeksu.
4. Rozwiązywanie kolizji: Ponieważ różne klucze mogą mieć ten sam hash (kolizja), kosz może zawierać kilka par "klucz-wartość". Do rozwiązania kolizji stosuje się różne metody:
   • Metoda łańcuchowa (separate chaining): W każdym koszu przechowywana jest lista (np. lista powiązana) par "klucz-wartość", których hasze są zgodne.
   • Metoda otwartego adresowania (open addressing): W przypadku kolizji, powtarza się wyszukiwanie wolnej komórki w tablicy według określonej reguły (sondowanie liniowe, kwadratowe, podwójne haszowanie).

Operacje:

• Wstawianie: Oblicza się hash klucza, określa indeks, a para "klucz-wartość" jest umieszczana w odpowiednim koszu. W przypadku kolizji, dodaje się do listy (łańcuchowanie) lub szuka wolnego miejsca (otwarte adresowanie).
• Wyszukiwanie: Oblicza się hash klucza, określa indeks. W odpowiednim koszu szuka się wartości po kluczu. W metodzie łańcuchowej przeszukuje się elementy listy; w otwartym adresowaniu wykonuje się wyszukiwanie sekwencyjne.
• Usuwanie: Oblicza się hash klucza, określa indeks. W odpowiednim koszu znajduje się i usuwa para po kluczu.

Zalety:

• Szybki dostęp do elementów (średnio O(1)).
• Efektywne wykorzystanie pamięci.

Wady:

• Wydajność może się pogarszać przy dużej liczbie kolizji.
• Rozmiar tablicy może wymagać regulacji (rehashowania), aby utrzymać wydajność.