📚 DataStructures – Hash Table Dictionary
Miniprojekt 3 – Struktury Danych (Politechnika Wrocławska)
Celem projektu była implementacja słownika opartego na tablicy mieszającej oraz porównanie trzech różnych metod obsługi kolizji.
Projekt został wykonany w języku C++ i obejmuje zarówno implementację, jak i empiryczne badania wydajności operacji insert oraz remove.
Zaimplementowane metody:
- AVL Tree – zewnętrzne łańcuchowanie z użyciem samobalansującego drzewa AVL
- Double Hashing – adresowanie otwarte z sondowaniem drugim hashem
- Cuckoo Hashing – mechanizm wypychania elementów między dwiema tablicami
🛠 Zaimplementowane struktury danych
- Każde pole tablicy mieszającej jest osobnym drzewem AVL
- Kolizje obsługiwane przez wstawianie do drzewa
- Złożoności:
- insert → O(log n)
- remove → O(log n)
- Stabilne czasy niezależne od load factor
🔁 Double Hashing (Open Addressing)
- Kolizje rozwiązywane przez sondowanie z krokiem drugiego hasha
- Rehash przy 70% zapełnienia tablicy
- Złożoności:
- insert → O(1) średnio
- remove → O(1) średnio
- Wydajność spada przy dużym load factor
🥚 Cuckoo Hashing (Cuckoo Strategy)
- Dwie tablice + dwie funkcje hashujące
- Kolizje powodują wypychanie elementów
- Rehash przy wykryciu cyklu
- Złożoności:
- insert → O(1) średnio
- remove → O(1)
- Najszybsze wyszukiwanie, ale niestabilne czasy wstawiania
Dla każdej struktury zmierzono czas wykonania:
- insert(key, value) – dodanie elementu
- remove(key) – usunięcie elementu
Pomiary wykonano dla rozmiarów danych od 1000 do 128 000 elementów, z użyciem wielu ziaren losowości.
Projekt został przygotowany w środowisku Visual Studio.
-
Sklonuj repozytorium:
git clone https://github.com/Czarko-exe/DataStructures-HashTableDictionary.git
-
Otwórz plik rozwiązania (.sln / .slnx) w programie Visual Studio.
-
Skompiluj projekt (zalecane użycie trybu Release dla dokładniejszych wyników badań wydajnościowych).
-
Uruchom aplikację. Obsługa programów testujących odbywa się za pomocą interaktywnego menu w konsoli.
- Double Hashing okazał się najszybszy, utrzymując czasy bliskie O(1).
- Cuckoo Hashing osiąga podobną wydajność, lecz wykazuje większą niestabilność czasową (wypychanie + rehash).
- AVL Tree działa najwolniej, ale zapewnia najwyższą stabilność i przewidywalność czasów.
github.com/Czarko-exe
github.com/R0-0F