Jak jest zbudowana tabela haszowa w kontenerze unordered_map?

unordered_map w C++ jest zaimplementowany jako tabela haszująca.

Zasada działania:

1. Hashowanie: Klucz jest przekształcany na liczbę całkowitą — kod hash — za pomocą funkcji hash.
2. Indeksowanie: Kod hash jest używany do określenia indeksu (wiadra lub bucketu) w tablicy wskaźników lub list.
3. Przechowywanie: W każdym wiadrze przechowywane są pary klucz-wartość.

Cechy:

• Wiadra: Tablica haszująca składa się z tablicy wiader. Liczba wiader może się dynamicznie zmieniać (rehash) po osiągnięciu określonego współczynnika obciążenia.
• Kolizje: Różne klucze mogą dawać ten sam kod hash. Nazywa się to kolizją. Aby rozwiązać kolizje, unordered_map używa metody ** chaining **: elementy z tym samym hashem są dodawane do powiązanej listy (lub innej struktury danych) w odpowiednim wiadrze.
• Funkcja hash i funkcja porównania: Do poprawnego działania potrzebne są dwie rzeczy:
  • Dobra funkcja hash, która równomiernie rozkłada klucze po wiadrach, minimalizując kolizje.
  • Funkcja równości (==), aby odróżnić klucze z tym samym kodem hash w jednym wiadrze.
• Wydajność: Średnio operacje wstawiania, usuwania i wyszukiwania mają złożoność czasową O(1). W najgorszym przypadku (np. przy dużej liczbie kolizji lub źle dobranej funkcji hash) wydajność może się pogorszyć do O(n), gdzie n to liczba elementów.

Przykład struktury (uproszczony):

struct Node {
  KeyType key;
  ValueType value;
  Node* next; // Dla powiązanej listy w wiadrze
};

struct Bucket {
  Node* head; // Wskaźnik na początek listy
};

Bucket* buckets; // Tablica wiader
size_t num_buckets;

Proces dodawania elementu:

1. Oblicza się kod hash klucza.
2. Określa się indeks wiadra: bucket_index = hash(key) % num_buckets.
3. Para klucz-wartość jest dodawana do listy elementów w tym wiadrze. Jeśli klucz już istnieje, wartość jest aktualizowana.

Proces wyszukiwania elementu:

1. Oblicza się kod hash klucza.
2. Określa się indeks wiadra.
3. Przechodzi się przez listę elementów w tym wiadrze, porównując klucze za pomocą operatora ==.

Rehashing zachodzi, gdy liczba elementów w stosunku do liczby wiader przekracza ustalony próg (współczynnik obciążenia). Podczas rehashingu tworzona jest nowa, większa tablica wiader, a wszystkie elementy ze starych wiader są ponownie haszowane i przenoszone do nowych.