AiSD (index)

AiSD (13) - ADT MAP (mieszanie)

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/

WPROWADZENIE

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

MIESZANIE

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.

FUNKCJE MIESZAJĄCE

Pomysły na funkcje mieszające.

PROBLEM KOLIZJI

Typowe sposoby radzenia sobie z kolizjami (ang. collision resolution) [Drozdek].

ZADANIE 13.1

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;
}

ZADANIE 13.2

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 wskaznikow 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); } // dziala 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;
}

ZADANIE 13.3

Poprawić metodę adresowania otwartego przez zastosowanie innych metod próbkowania.

AiSD (index)