Słowniki z haszowaniem (projekt)

Spis Treści

Wariant podstawy (na oceny 3)

Należy zaimplementować dwa słowniki, używające haszowania i rozwiązujące kolizje za pomocą:

  1. metody łańcuchowej (tablica tablic albo list);
  2. adresowania otwartego liniowego.

Za każdy słownik wystawiana jest osobna ocena.

Oba słowniki powinny oferować wszystkie 3 operacje słownikowe: insert, find, delete.

Dodatkowo należy opanować (ze zrozumieniem) teorię dotyczącą tych operacji (zasady działania, złożoności obliczeniowe czasowe i pamięciowe).

Słowniki mogą implementować zwykły zbiór liczb całkowitych, nieujemnych. Powinny one unikać duplikatów kluczy.

Program powinien być napisany w sposób czytelny. Nie wolno pomieszać kodu słownika z kodem programu demonstracyjnego/testującego. W celu sporządzenia ewentualnego wykresu, do kodu słownika można jedynie dodać licznik wykonanych operacji porównania kluczy. Jedną z dobrych dróg do uzyskania czytelnego programu jest programowanie obiektowe, ściślej, zaimplementowanie poszczególnych operacje słownikowych jako metod klasy słownika.

Ocena może być podwyższona o 0,5 stopnia za oddanie programu w pierwszym terminie, z bezbłędną odpowiedzią.

Rozszerzenia, na wyższe oceny

Każde z poniższych rozszerzeń umożliwia podwyższenie maksymalnej oceny, za słownik do którego to rozszerzenie zaaplikowano (za każdy ze słowników wystawiana jest osobna ocena).

Rozszerzenia obu słowników:

Rehaszowanie (+1 do oceny)

Metody insert/delete w razie potrzeby (gdy jest w niej zbyt wiele/mało elementów) wykonują rehaszowanie, czyli dynamiczne zwiększają/zmniejszają tablicę, przepisując zawartości do nowego obszaru pamięci.

Wykres zależności liczby porównań od liczby elementów w słowniku (+1 do oceny)

Należy wykonać wykres ilustrujący zależność: liczba elementów w słowniku -> średnia liczba porównań kluczy potrzebna by znaleźć element.

Dane do wykresu można spreparować następującym algorytmem:

  1. Utwórz pusty słownik.

  2. Dodaj do słownika element o wylosowanym kluczu.

    Uwaga: jeśli wylosowany klucz znajduje się już w słowniku (i jako duplikat nie zostałby dodany), to należy wylosować kolejny, do skutku.

  3. Wylosuj kolejny klucz i wyszukaj go w słowniku. Zmierz liczbę porównań kluczy wykonaną przez operację wyszukiwania. Zapisz liczbę elementów znajdujących się w słowniku (x) oraz uzyskaną liczbę porównań (y). Te dwie liczby (x, y) stanowią pojedynczy punkt do wykresu.

    Uwaga: dla zmniejszenia przypadkowości można wylosować kilka kluczy i uśrednić uzyskane dla nich liczby porównań.

  4. Wróć do punktu 2, chyba że w słowniku znajduje się już wystarczająco dużo elementów (np. 100000).

Uwaga: W punktach 2 i 3 zaleca się losowanie kluczy z możliwie dużego zakresu.

Wykresy można narysować zarówno bezpośrednio za pomocą programu (korzystając z bibliotek takich jak np. matplotlib dla języka Python), jak i za pomocą zewnętrznego narzędzia, np. arkusza kalkulacyjnego. W tym drugim przypadku najłatwiej jest zapisać dane pomiarowe do pliku CSV, który następnie można otworzyć w arkuszu.

Mapa klucz->wartość z dowolnymi typami kluczy i wartości (+0,5 do oceny)

Słowniki realizuje mapę klucz->wartość. Ponadto klucze i wartości mogą być dowolnych typów. Należy użyć dostarczonych w bibliotekach języka funkcji (np. hash w języku Python albo std::hash w C++) by obsłużyć dowolne, haszowalne typy danych jako klucze.

Rozszerzenia słownika z adresowaniem otwartym:

Adresowanie podwójne (+0,5 do oceny)

Słownik używa adresowania podwójnego zamiast liniowego.

Usuwanie z przesuwaniem elementów (+1 do oceny)

Usuwanie z tablicy z adresowaniem liniowym, które przesuwa elementy zamiast specjalnie oznaczać komórki jako skasowane.

Robin-Hood hashing (+1 do oceny)

Słownik z adresowaniem liniowym używa Robin-Hood hashing.

Przykładowe pytania sprawdzające