Делал тут для себя шпаргалку по хэштейблам в новой версии стандарта C++, и мне подумалось: а почему бы со всеми не поделиться?

Вообще в C++11 в STL появилось некоторое количество новых плюшек, большинство из которых вряд ли пригодятся программистам-олимпиадникам. Красивую схемку с их описанием можно найти здесь. Но две новых структуры данных, которые наконец были включены в стандарт, заслуживают внимания — это unordered_set и unordered_map.

Многие, наверное, знают, что из себя представляет хэш-тейбл. Это контейнер, позволяющий добавлять, удалять и искать элементы за O(1) в среднем. Принципиально бывают хэштейблы с цепочечной (не знаю, насколько принят в русскоязычной литературе такой термин?) и открытой адресацией. Вкратце напомню разницу.

В цепочечном варианте хэштейбл для каждого значения хэша хранит все элементы с таким хэшом в виде списка (под словом список следует понимать либо list, либо динамически расширяющийся массив, либо что-нибудь ещё такое, по чему можно тупо проитерироваться). Тем самым, в самом хэштейбле значения непосредственно не хранятся — хранятся лишь линки на контейнеры с ними, называемые также по-английски bucket'ами. Как правильно переводится такой термин на русский, кстати?

В варианте с открытой адресацией, в отличие от цепочечного хранения, значения хранятся непосредственно в самой таблице, однако не гарантируется, что элемент X гарантированно будет лежать в ячейке с номером Hash(X). На самом деле, обычно bucket'ы из предыдущего варианта просто укладываются сверху вних в самой таблице — то есть, если мы не нашли нужное нам значение в ячейке Hash(X), посмотрим в ячейку Hash(X) + 1, потом в Hash(X) + 2 и так далее. Возникает проблема, что если из ячейки 424243 растёт bucket размера 5, а из ячейки 424245 — bucket размера 6, они обязательно перекроются. Но на это мы забьём — нам просто придётся пройтись по всем значениям — в том числе и принадлежащим к чужому bucket'у — когда понадобится дойти до нужного в операции поиска.

STL реализует первый вариант хэш-таблицы. Идейно unordered_set реализует все те же самые методы и свойства, что и обычный set, то есть в первом приближении им можно точно так же пользоваться:

#include <unordered_set>
#include <iostream>
using namespace std;

int main()
{
    unordered_set<int> S;
    int n, m, t;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> t;
        S.insert(t);
    }
    cin >> m;
    for (int i = 0; i < m; i++)
    {
        cin >> t;
        if (S.find(t) != S.end())
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
    return 0;
}

Разберём поподробнее все интересные методы и свойства. Какие есть шаблонные параметры у класса.

template<
    class Key,
    class Hash = std::hash<Key>,
    class KeyEqual = std::equal_to<Key>,
    class Allocator = std::allocator<Key>
> class unordered_set;

Первый параметр — единственный обязательный — это собственно тип того, что мы будем хранить.

Второй параметр — это хэш-функция. Это должен быть объект (структура или функция), у которой оператор (), выполненный от объекта типа Key, возвращает величину типа size_t, равную хэшу объекта. По умолчанию хэшером является std::hash — этот класс умеет хэшировать все стандартные числовые типы, стринги, битсеты и ещё пару C++-ных типов (здесь подробнее). Можно в качестве этого параметра написать свою структуру, а можно перегрузить std::hash под свой тип Key. Рекомендую пользоваться вторым способом — он идейно проще. Пример приведён ниже.

namespace std {
template<>
class hash<S> {
public:
    size_t operator()(const S &s) const 
    {
        size_t h1 = std::hash<std::string>()(s.first_name);
        size_t h2 = std::hash<std::string>()(s.last_name);
        return h1 ^ ( h2 << 1 );
    }
};
}

Третий параметр — это функция сравнения. Так как в одном bucket'е все значения лежат вперемешку, структура должна как-то уметь проверять — очередное значение это то, что надо, или нет? По умолчанию это std::equal_to, который просто вызывает оператор ==, который стоит перегрузить для ваших типов.

Четвёртый параметр — это стандартный для всех STL'ных структур аллокатор. Про него ничего говорить не буду — его лучше отдельно не касаться, кому интересно — сами прочитаете :-)

Интересно, что в отличие от многих других STL'ных структур unordered_set даёт доступ к тому, как он реально устроен. То есть у него есть интерфесы для работы непосредственно с bucket'ами. Каждый bucket идентифицируется своим номером с нуля. Для очередного объекта номер bucket'а, куда он попадёт, вычисляется как Hash(x) % bucket_count(). Но более кошерно использовать метод bucket(Key), который вернёт номер bucket'а, куда попадёт ключ Key.

У хэштейбла есть такой параметр, как bucket_count() — он возвращает текущее количество bucket'ов. Верно следующее: автоматически происходит тотальный рехэш, когда количество элементов в хэш-таблице превзойдёт max_load_factor() * bucket_count(). Что это значит? max_load_factor() — это просто константа для хэш-таблицы, которая указывает пороговое значение среднего количества элементов на bucket для тотального рехэша. Поправить это значение, можно вызвав max_load_factor(f), это установит max_load_factor равным f. f должно иметь тип float.

Итераторы у хэш-тейбла проходят сначала по очереди по всем bucket'ам с нулевого по (bucket_count() - 1)-ый. Методы begin() и end() работают как обычно, но им можно передать параметр t, который даст итераторы на начало и конец t-ого bucket'а.

Есть интересный метод emplace(Args&&... args). Он вставляет в хэштаблицу значение, но не как обычный insert, которому надо готовое значение отдать, а он с помощью конструктора копирования его вставит. emplace же в нужном месте просто вызовет конструктор копирования (которому, например, для стрингов достаточно просто скопировать ссылки на расположение строки в памяти за O(1)).

Итераторы инвалидируются с каждой операцией перехэширования, которое происходит автоматически при достижени порогового фактора загрузки, либо которые можно вызвать методами reserve(n) (зарезервировать места под n элементов), либо rehash(n) (зарезервировать места под n bucket'ов).

Вот пожалуй и всё. Ещё бывает unordered_multiset, который отличается возможностью хранения нескольких идентичных ключей. Ещё бывают unordered_map и unordered_multimap, которые отличаются от unordered_set ровно тем же, чем map и multimap отличаются от set.

Полезная, в общем, структура. Но в отличие от set, который обгоняет большинство рукописных сбалансированных деревьев поиска, хэштаблица, во всяком случае в g++ 4.6.1, сделана так, чтобы применяться во всех мыслимых и немыслимых ситуациях, и это происходит в ущерб скорости. То есть естественно, что рукописная хэш-таблица с открытой адресацией, содержащая int'ы с хэшированием по модулю 2^16, делает STL'ную раза в три по скорости.

Думаю, такая шпаргалка кому-то окажется полезной — я не из тех, кто сильно любит писать структуры данных руками, был рад появлению хэштаблицы в C++11 :-)