OBOWIĄZKOWE DO PRZESŁANIA: jedno zadanie
https://en.wikipedia.org/wiki/Associative_array
https://en.wikipedia.org/wiki/Hash_table
https://en.wikipedia.org/wiki/Hash_function
https://en.wikipedia.org/wiki/Open_addressing
https://en.wikipedia.org/wiki/Lazy_deletion
https://www.geeksforgeeks.org/hashing-data-structure/
ADT MAP to inaczej tablica asocjacyjna (ang. associative array), tablica skojarzeniowa, mapa, słownik. Przechowuje on pary (klucz, wartość) i umożliwia dostęp do wartości za pomocą klucza. Jest to mapowanie klucza na wartość. ADT MAP może być realizowany jako drzewa poszukiwań (BST, AVL, trie), tablice mieszające, czy listy z przeskokami. Kluczami są najczęściej stringi, liczby, krotki, itp. Jeżeli szukany klucz nie istnieje, to w zależności od implementacji albo rzucany jest wyjątek, albo do mapy dodawana jest para złożona z szukanego klucza i pewnej domyślnej wartości (np. zero dla wartości będących liczbami).
Typowe operacje dla ADT MAP są następujące:
// https://en.cppreference.com/w/cpp/utility/pair/make_pair
#include <utility> // make_pair()
auto p1 = std::make_pair(2, 3.4) // dedukcja typów
std::pair<int,float> p2 = {6, 2.5};
// Dostęp do składowych przez p2.first i p2.second.
// Uogólniony operator operator<< do wyświetlania par.
namespace std {
template<typename F, typename S>
ostream& operator<<(ostream& os, const std::pair<F,S> p) {
return os << p.first << " " << p.second;
}
}
// https://en.cppreference.com/w/cpp/container/unordered_map // Internally, the elements are not sorted in any particular order, but organized into buckets. // Search, insertion, and removal of elements have average constant-time complexity. #include <unordered_map>
// https://en.cppreference.com/w/cpp/container/map
// Keys are sorted by using the comparison function (default std::less).
// Maps are usually implemented as Red-black trees.
// Search, removal, and insertion operations have logarithmic complexity.
#include <map>
std::map<int, float> m; // mapa
assert( m.empty() );
m.insert( std::make_pair(1, 1.1) ); // zwraca std::pair<iterator,bool>
m[2]; // wstawienie pary (2, 0.0)
assert( m[2] == 0.0 );
m[3] = 3.3;
m.emplace( std::make_pair(4, 4.4) ); // insert a new element in-place
m.insert( {5, 5.5} );
assert( m.size() == 5 );
assert( m.count(3) == 1 ); // dozwolone 0 lub 1 dla map
assert( m.count(7) == 0 ); // dozwolone 0 lub 1 dla map
for (auto it = m.begin(); it != m.end(); ++it) {
std::cout << it->first << " " << it->second << std::endl;
}
for (auto& p : m) { // pętla zakresowa
std::cout << p.first << " " << p.second << std::endl;
}
auto it = m.find(3); // szukam klucza 3
assert( it != m.end() ); // wiemy, że jest ten klucz
assert( m.find(8) == m.end() ); // brak klucza
m.erase(it); // remove at position
m.erase(5); // remove key
m.clear(); // czyszczenie
Jeżeli klucze są liczbami z niedużego zakresu, to można łącze do pary (key, value) przechowywać w tablicy pod indeksem key. Zwykle jednak wykorzystuje się funkcję mieszającą hash(key), która oblicza położenie w tablicy. Dobra funkcja mieszająca powinna (1) działać szybko [niski koszt] i (2) jednorodnie rozmieszczać klucze w tablicy. Wtedy wstawianie, wyszukiwanie i usuwanie klucza działa w czasie O(1).
W praktyce nie jest łatwo znaleźć doskonałą funkcję mieszającą i pojawiają się kolizje, czyli dla kluczy key1 != key2 otrzymujemy hash(key1) = hash(key2). Kolizje zdarzają się zwykle tym częściej im bardziej zapełniona jest tablica, dlatego zwykle tablica jest większa niż spodziewana liczba kluczy. Niektóre metody mieszania dobrze działają dla rozmiaru tablicy będącym potęgą dwójki, inne dla liczb pierwszych.
Pomysły na funkcje mieszające.
Typowe sposoby radzenia sobie z kolizjami (ang. collision resolution) [Drozdek].
Przygotować implementację realizującą ADT MAP na bazie tablicy mieszającej z wykorzystaniem metody łańcuchowej.
// Szablon dla prostej mapy wykorzystującej metodę łańcuchową.
// Pomysł zaczerpnięty ze strony
// https://www.geeksforgeeks.org/c-program-hashing-chaining/
template <typename F, typename S>
class HashTable {
int BUCKET; // liczba bukietów
std::list< std::pair<F,S> > *table;
public:
HashTable(int b);
~HashTable() { clear(); delete [] table; }
bool empty() const; // czy wszystkie listy puste
int size() const; // liczba par na wszystkich listach
void insert(std::pair<F,S> p); // m[p.first]=p.second
S& operator[](const F& key); // m[key]=value lub m[key] z domyślną wartością
S* find(const F& key); // zwraca &value lub nullptr
void remove(const F& key);
int hash(const F& key) { return (int(key) % BUCKET); } // działa dla int, float
void display() const;
void clear(); // czyścimy wszystkie listy
};
template<typename F, typename S>
HashTable<F,S>::HashTable(int b) {
BUCKET = b;
table = new std::list< std::pair<F,S> >[BUCKET];
assert( table != nullptr );
}
template<typename F, typename S>
void HashTable<F,S>::display() const {
for (int i = 0; i < BUCKET; i++) {
std::cout << i;
for (const auto& p : table[i])
std::cout << " --> " << p;
std::cout << std::endl;
}
}
template<typename F, typename S>
S& HashTable<F,S>::operator[](const F& key) {
int index = hash(key);
// find the key
for (auto& p : table[index]) {
if (p.first == key) {
return p.second;
}
}
table[index].push_back(std::make_pair(key, S()));
return (table[index].back()).second;
}
Przygotować implementację realizującą ADT MAP na bazie tablicy mieszającej z wykorzystaniem adresowania otwartego i próbkowania linowego.
Wstawiane klucze: A5, A2, A3, B5, A9, B2, B9, C2 |0 |1 |2 |3 |4 |5 |6 |7 |8 |9 | |--|--|A2|A3|--|A5|--|--|--|--| |--|--|A2|A3|B2|A5|B5|--|--|A9| |B9|--|A2|A3|B2|A5|B5|C2|--|A9| problem przy usuwaniu A3
// Szablon dla prostej mapy wykorzystującej adresowanie otwarte.
template <typename F, typename S>
class HashTable {
int BUCKET; // liczba bukietów
std::pair<F,S> **table; // tablica wskaźnikow do par
public:
HashTable(int b);
~HashTable() { clear(); delete [] table; }
bool empty() const;
int size() const;
void insert(std::pair<F,S> p);
S& operator[](const F& key);
S* find(const F& key);
void remove(const F& key); // TRUDNE
int hash(const F& key) { return (int(key) % BUCKET); } // działa dla int, float
void display() const;
void clear();
};
template <typename F, typename S>
HashTable<F,S>::HashTable(int b) {
BUCKET = b;
table = new std::pair<F,S>* [BUCKET];
assert( table != nullptr );
for (int i = 0; i < BUCKET; i++)
table[i] = nullptr;
}
Poprawić metodę adresowania otwartego przez zastosowanie innych metod próbkowania.