Kontenery haszujące¶

Kontenery haszujące gwarantują średnio stałą złożoność czasową operacji wyszukiwania, wstawiania oraz usuwania. Elementy w kontenerze haszującym nie są posortowane, ale są przechowywane w tzw. kubełkach (buckets). Element trafia do określonego kubełka na podstawie wartości skrótu (hash value) obliczanej dla elementu.

C++11 wprowadza następujące kontenery haszujące

zbiory: unordered_set i unordered_multiset
mapy: unordered_map i unordered_multimap

std::unordered_set¶

Plik nagłówkowy <unordered_set>

namespace std
{
    template<
        typename Key,
        typename Hash = std::hash<Key>,
        typename Pred = std::equal_to<Key>,
        typename Alloc = std::allocator<Key>
    > class unordered_set
    {
        //...
     };
}

Zbiór haszujący akceptujący duplikaty kluczy: unordered_multiset
Kontener unordered_set wymaga podania jako parametrów szablonu:
- Funktora lub funkcji haszującej klucze - domyślnie std::hash<T>
- Predykatu równości elementów - domyślnie std::equal_to<T>

Ważne

Dla kluczy typu Key, które są sobie równe k1 == k2, musi być spełniona równość std::hash<Key>(k1) == std::hash<Key>(k2).

Metody dostępowe dla kubełków¶

Kontenery z haszowaniem dostarczają zbiór metod, które umożliwiają zarządzanie strukturą kubełków w kontenerze.

size_type bucket_count() const¶: Ilość kubełków

size_type max_bucket_count() const¶: Górna granica ilości kubełków

size_type bucket_size(size_type n)¶: Rozmiar kubełka numer n

size_type bucket(const key_type &k)¶: Indeks kubełka zawierającego klucz k

float load_factor() const¶: Średnia ilość elementów w kubełku

float max_load_factor() const¶: Bieżąca maksymalna ilość elementów w kubełku

float max_load_factor(float ml)¶: Zmiana poziomu zapełnienia kubełków (ml jest traktowane jako podpowiedź)

void rehash(size_type n)¶: Zmienia ilość kubełków na co najmniej n

Przykład

#include <random>
#include <unordered_set>

std::random_device rd;
std::default_random_engine rnd_engine{rd};
std::uniform_int_distribution<> rnd_distr{rnd_engine};

std::unordered_set<int> uset1;

for(size_t i = 0; i < 1000; ++i)
    uset1.insert(rnd_distr());

cout << "\nIlosc wystapien elementu o wartosci 50: "
     << uset1.count(50) << endl;

std::unordered_set<int>::iterator where = uset1.find(50);
if (where != uset1.end())
    cout << "Znaleziony element: " << *where << endl;

std::unordered_map¶

Plik nagłówkowy: <unordered_map>

namespace std
{
    template
    <
        typename Key, class T,
        typename Hash = std::hash<Key>,
        typename Pred = std::equal_to<Key>,
        typename Alloc = std::allocator<std::pair<const Key, T> >
    > class unordered_map
    {
        //...
    };
}

Jako parametry szablonu klasy przekazywane są typy:
- Key - klucz
- T - mapowany typ
- Hash - funktor wyliczający skrót dla klucza
- Pred - predykat porównujący klucze
Mapa haszująca dopuszczająca duplikaty kluczy: unordered_multimap

Przykład:

std::unordered_map<int, string> umap1 = { { 7, "nd"}, {6, "sob"} };

umap1.insert(pair<int, string>(1, "pon"));
umap1.insert(make_pair(2, "wt"));
umap1.insert(std::unordered_map<int, string>::value_type(3, "sr"));
umap1[5] = "pt";

auto where = umap1.find(3);
if (where != umap1.end())
    std::cout << "Znaleziono wpis: " << where->first << " - "
         << where->second << std::endl;

std::cout << "6: " << umap1[6] << std::endl;

std::hash¶

Struktura szablonowa std::hash definiuje obiekt funkcyjny, który umożliwia wyliczenie wartości skrótu.

Operator wywołania funkcji spełnia poniższe wymagania:

Akceptuje argument typu Key
Zwraca wartość typu size_t
Nie rzuca wyjątków
Dla dwóch wartości k1 i k2, które są sobie równe std::hash<Key>()(k1) == std::hash<Key>()(k2)
Dla dwóch wartości, które nie są sobie równe, prawdopodobieństwo, że wyliczona dla nich zostanie taka sama wartość skrótu powinna być bardzo mała.

Standard specjalizuje szablon std::hash dla:

wszystkich typów liczbowych
typów wskaźnikowych: T*, std::unique_ptr oraz std::shared_ptr
typów łańcuchowych
std::bitset
std::vector<bool>
std::thread::id
std::type_index

Tworzenie funkcji haszujących¶

Jeżeli typem klucza kontenera z haszowaniem jest typ tworzony przez użytkownika, to należy dostarczyć jako parametr typu kontenera specjalizowaną funkcję haszującą. Może ty zostać zrealizowane na dwa sposoby:

Klasa funktora.

struct Person
{
    std::string first_name;
    std::string last_name;

    bool operator==(const Person& other) const
    {
        return std::tie(first_name, last_name) == std::tie(other.first_name, other.last_name);
    }
};

template <typename T>
struct HashPerson
{
    size_t operator()(const Person& p) const
    {

        std::size_t h1 = std::hash<std::string>()(p.first_name);
        std::size_t h2 = std::hash<std::string>()(p.last_name);
        return h1 ^ (h2 << 1); // or use boost::hash_combine
    }
};

std::unordered_set<Person, HashPerson> people;

Specjalizacja klasy std::hash.

namespace std
{
    template<> struct hash<Person>
    {
        typedef Person argument_type;
        typedef std::size_t result_type;

        result_type operator()(argument_type const& p) const
        {
            result_type const h1 ( std::hash<std::string>()(p.first_name) );
            result_type const h2 ( std::hash<std::string>()(p.last_name) );
            return h1 ^ (h2 << 1); // or use boost::hash_combine
        }
    };
}

std::unordered_set<Person> people;