Блог пользователя Zlobober

Автор Zlobober, 12 лет назад, По-русски

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

  • Проголосовать: нравится
  • +112
  • Проголосовать: не нравится

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится +25 Проголосовать: не нравится

Несколько дополнений.

1) Писать свою структуру или наследоваться от hash вовсе не обязательно — можно написать так:

unordered_map<Point, int, function<size_t(const Point& point)>> point_map(100500, 
    [](const Point & point) {
      return hash<int>()(point.x) * 57 + hash<int>()(point.y);
    });

(и кстати, в таком же стиле можно передавать компараторы в sort — очень удобная фича).

2) Про begin()/end() можно в большинстве случаев забыть — теперь можно писать конструкции вида

for (auto point : point_set) {
  // ...
}

Так что можно попрощаться с уродливыми циклами по итераторам.

Единственный drawback у всего этого дела — C++11 пока мало где поддерживается. Многие организаторы соревнований (вроде topcoder, у которого до сих пор jdk5) очень консервативны и боятся нововведений. А зря.

  • »
    »
    12 лет назад, # ^ |
    Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

    уточнение по первому пункту.
    "наследоваться" не не обязательно, а опасно. если у вас в двух разных cpp-шниках создаются такие темплейты namespace std { template<> class hash<S> { ... и с помощью них заполняются две разные хеш таблицы, то по факту обе таблицы будут юзать один и тот же хешер. То есть hash<S> будет взят любой из двух реализованных рандомно, и везде использоваться будет он один, наплевав на то что есть второй. Правда я говорю о простом C++, может это как-то исправлено.
    UPD: Пример смотри в предыдущей правке

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Это так по стандарту делать положено, или просто приколы конкретного линкера? Больше похоже на второе — слабо верится, что c++ настолько безумный :) Логика подсказывает, что в случае одинаковых специализаций одного и того же темплейта в одном и том же namespace линкер должен выдавать ошибку.

      • »
        »
        »
        »
        12 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        думаю, что нет. думаю стандарт, я точно не помню откуда у меня такое тайное знание, но ощущения такие что из обсуждения языка а не компилятора. Впринципе логично, если vector существует (создан такой класс, либо был объявлен отдельно от общего случая как в STL на битах) и где-то снова юзается vector, то берется существующая реализация, нафига плодить ещё?

      • »
        »
        »
        »
        12 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Еще один аргумент, в пользу того что нельзя отследить все такие случаи, это полнота по Тьюрингу шаблонов.

      • »
        »
        »
        »
        12 лет назад, # ^ |
        Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

        Две различные class template specialization в одной программе, по идее, нарушают ODR (One Definition Rule). Поэтому по стандарту это не well-formed program в принципе. Другое дело, что не факт, что по стандарту система трансляции обязана выдавать в данном случае диагностику. Если интересно, то могу попробовать внимательно поизучать стандарт по этому вопросу :)

        Edit: Правда, мне непонятен изначальный посыл. Наследоваться от stl-контейнеров, вообще говоря, не самая лучшая идея в большинстве случаев, но в чем тут опасность, не очень понятно. Наследоваться в данном случае будет так же опасно, как и использовать эту специализацию вообще.

        • »
          »
          »
          »
          »
          12 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Я не очень понял что ты имеешь в виду под словом "наследоваться", ибо это не наследование в обычном понимании, поэтому в моём ответе выше это слово в кавычках.

          • »
            »
            »
            »
            »
            »
            12 лет назад, # ^ |
            Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

            Ага, это я так отлично прочитал по диагонали сам пост, что в нем слона и не заметил :) Извиняюсь.

            Понятно, речь не о наследовании, а как раз об определении своей специализации в namespace std. В общем, я в любом случае, согласен с тем, что лучше задать лямбду или структурку объявить, а не так, как предлагается.

»
12 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

"emplace в нужном месте просто тупо вызовет конструктор, и сконструирует уже на нужном месте ключ, т.е. не будет лишних операций копирования."

Насколько я понимаю, insert и emplace оба используют placement new, то есть конструируют копию переданного ключа уже на нужном месте. Разница в том, что insert вызывает обычный копирующий конструктор, а emplace — перемещающий (move constructor). То есть emplace уничтожает переданный объект, создавая его копию. Это може быть полезно, например, для стандартных контейнеров и строк, которые делают перемещение за O(1), а копирование за O(N).

Это, кстати, интересная фича C++11: теперь, например, возвращая вектор из функции, можно не волноваться, соптимизирует ли компилятор это копирование, а быть уверенным — теперь это дело не компилятора, а перемещающего конструктора, с которым явно все в порядке.

  • »
    »
    12 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Да, я как-то криво сформулировал. Сейчас поправлю.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Вроде как вижак давным давно не вызывает для объекта, возвращаемого из функции, конструктор копирования.

»
12 лет назад, # |
Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

А можно узнать значение(я), когда unordered_set обгоняет обычный set. Раз уж написал пост, проведи пожалуйста простой эксперимент со вставкой, компилера под рукой нету. просто вставка n элементов в set, unordered_set и unordered_set которому сделали reserve(n). А ну да, от max_load_factor() зависит, ну пусть стандартный будет, какой кстати?

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Вот есть один пример: http://mirror.codeforces.com/blog/entry/2865. Но получить точные цифры было бы правда интересно.

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

    Да, хорошо. Ближе к ночи (или совсем завтра) так и сделаю.

    Субъективно рукописный хэшсет раза в три-четыре быстрее — примерно во столько раз я добился ускорения этой зимой на сборах команды на IOI после переписывания.

»
12 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Bucket обычно переводят как "корзина"

  • »
    »
    12 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Это-то конечно да :-) А в научных текстах такой термин реально используется? Можно какое-нибудь подтверждение привести?

    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      Набор в гугле "bucket корзина" убедил меня в общеупотребительном свойстве такого перевода: даже нашел по родным финансам "maturity buckets -> корзины активов с разными сроками обращения"

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится -37 Проголосовать: не нравится

никто_не_читает

прочитал :з

p.s. в тегах пасхалка, спасибо за статью