Czym jest tablica haszująca?

Tablica mieszająca to struktura danych, która przechowuje pary klucz-wartość, podobnie jak słownik wyszukujący wpisy na podstawie klucza. Jej zaletą jest szybkość: dobrze zaprojektowana tablica mieszająca znajduje, wstawia lub usuwa wpis w średnim czasie O(1), niezależnie od tego, ile wpisów zawiera.

Kluczowa jest funkcja mieszająca. Każdy klucz jest przekształcany w indeks kubełka, dzięki czemu wiemy dokładnie, gdzie szukać, bez przeglądania całej tablicy. Gdy dwa różne klucze trafią do tego samego kubełka (kolizja), przechowujemy je razem na liście w tym kubełku. Ta strategia nazywa się łańcuchowaniem.

Pięć głównych operacji na tablicy mieszającej to:

1. Put: Zapisuje parę klucz-wartość albo aktualizuje wartość, jeśli dany klucz już istnieje.
2. Get: Wyszukuje wartość przypisaną do danego klucza.
3. ContainsKey: Sprawdza, czy klucz jest zapisany w tablicy.
4. Remove: Usuwa parę klucz-wartość.
5. Size: Zwraca liczbę aktualnie przechowywanych par.

Utwórzmy klasę HashMap!