📚 DataStructures – Hash Table Dictionary

Miniprojekt 3 – Struktury Danych (Politechnika Wrocławska)

---

📌 Opis projektu

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

🌲 AVL Tree (Chaining)

• 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

---

⚙️ Badane operacje

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.

---

🚀 Jak uruchomić projekt

Projekt został przygotowany w środowisku Visual Studio.

1. Sklonuj repozytorium:

   git clone https://github.com/Czarko-exe/DataStructures-HashTableDictionary.git
   

2. Otwórz plik rozwiązania (.sln / .slnx) w programie Visual Studio.

3. Skompiluj projekt (zalecane użycie trybu Release dla dokładniejszych wyników badań wydajnościowych).

4. Uruchom aplikację. Obsługa programów testujących odbywa się za pomocą interaktywnego menu w konsoli.

📊 Wyniki badań (Skrót)

• 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.

👨‍💻 Autorzy

github.com/Czarko-exe
github.com/R0-0F