Делал тут для себя шпаргалку по хэштейблам в новой версии стандарта 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 :-)