Как хешировать unordered_map?

Проблема здесь в том, что нет гарантии, что элементы даже имеют упорядочение между собой.
Таким образом, сортировка элементов может не работать для произвольных неупорядоченных контейнеров. . У вас есть 2 варианта:

1. Просто выполните XOR для хэшей всех отдельных элементов. Это самый быстрый.
2. Сначала отсортируйте хеши контейнеров, а затем затем их. Это может привести к лучшему хешированию.

Вы, конечно, можете преобразовать unordered_map в какую-то другую структуру данных с гарантированным порядком и использовать ее для генерации хэша.

Лучше всего было бы хешировать каждый отдельный элемент карты, поместить эти хеши в vector, а затем отсортировать и объединить хеши. См., Например, Как объединить хеш-значения в C ++ 0x? для объединения хешей.

template<typename Hash, typename Iterator>
size_t order_independent_hash(Iterator begin, Iterator end, Hash hasher)
{
    std::vector<size_t> hashes;
    for (Iterator it = begin; it != end; ++it)
        hashes.push_back(hasher(*it));
    std::sort(hashes.begin(), hashes.end());
    size_t result = 0;
    for (auto it2 = hashes.begin(); it2 != hashes.end(); ++it2)
        result ^= *it2 + 0x9e3779b9 + (result<<6) + (result>>2);
    return result;
}

Проверка этого на перетасованных векторах показывает, что он всегда возвращает один и тот же хэш.

Теперь адаптируем эту базовую концепцию для работы с unordered_map. Поскольку итератор unordered_map возвращает pair, нам также нужна хеш-функция для этого.

namespace std
{
    template<typename T1, typename T2>
    struct hash<std::pair<T1,T2> >
    {
        typedef std::pair<T1,T2> argument_type;
        typedef std::size_t result_type;

        result_type operator()(argument_type const& s) const
        {
            result_type const h1 ( std::hash<T1>()(s.first) );
            result_type const h2 ( std::hash<T2>()(s.second) );
            return h1 ^ (h2 + 0x9e3779b9 + (h1<<6) + (h1>>2));
        }
    };

    template<typename Key, typename T>
    struct hash<std::unordered_map<Key,T> >
    {
        typedef std::unordered_map<Key,T> argument_type;
        typedef std::size_t result_type;

        result_type operator()(argument_type const& s) const
        {
            return order_independent_hash(s.begin(), s.end(), std::hash<std::pair<Key,T> >());
        }
    };
}

Посмотрите, как это работает: http://ideone.com/WOLFbc

Думаю, вы не понимаете, для чего используется хеш. Это ключи, используемые для идентификации элементов, чтобы определить, где их хранить. Два эквивалентных элемента должны иметь одинаковое значение.

Вы пытаетесь проверить, эквивалентны ли две неупорядоченные карты, и храните их в каком-то контейнере?

Ключи к неупорядоченной карте - ну, они хешированы. Фактически контейнер мог бы называться hash_map, если бы такой контейнер уже не существовал.

Но хорошо, предположим, вы действительно хотите сохранить неупорядоченные карты и сравнить их, чтобы увидеть, эквивалентны ли два. Что ж, вам нужно было бы придумать алгоритм хеширования, который возвращал бы одно и то же значение независимо от положения содержащихся в нем элементов. Контрольная сумма всех его элементов (ключей и значений) была бы одним из возможных способов.

Также обратите внимание, что тот факт, что два элемента имеют одинаковое значение хеш-функции, не означает, что они эквивалентны. Это просто означает, что если хеш-значение отличается, они определенно не эквивалентны. На самом деле контрольные суммы часто используются для проверки данных именно по этой причине. Неправильная контрольная сумма является доказательством того, что данные недействительны, а при наличии хорошей формулы правильная формула делает ее весьма вероятной, хотя и не уверен, что это так.

Мне любопытно, учитывая, что вы пытаетесь хешировать unordered_map, чтобы использовать его в качестве ключа, и, учитывая, что после хеширования unordered_map вы не будете его менять (если вы не используете его для создания нового ключа), снижение производительности при преобразовании unordered_map в упорядоченный map (а затем, конечно, хеширование упорядоченного map и использование этого в качестве ключа)? Или проблема этого подхода в том, что вам нужно более быстрое время поиска, обеспечиваемое unordered_map?

Как бы то ни было, может иметь место преимущество использования упорядоченного map (согласно принятому ответу в следующем сообщении, unordered_map обычно использует больше памяти):

Есть ли есть ли преимущества использования карты перед unordered_map в случае тривиальных ключей?

Вы не указали никаких требований к производительности, но если вам просто нужно «быстрое и грязное» решение, которое не потребует от вас много кода и будет использовать преимущества boost::hash, вы можете скопировать диапазон элементов от unordered_map до vector , std::sort вектор, а затем передайте его в boost::hash_range.

Однако вряд ли это самое эффективное решение, и вы не захотите использовать его часто или с большим количеством элементов.

Мой предпочтительный подход - это специализация unordered_map, которая поддерживает текущий, актуальный хэш содержимого - вам не нужно передавать все элементы и выполнять вычисления, чтобы получить текущее значение. Вместо этого член структуры данных должен отражать хэш и изменяться в реальном времени по мере вставки или удаления элементов и считываться при необходимости.