Вычислить хэш структуры карты

Question

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

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

На данный момент фактическая хеш-функция не так важна. Я думаю md5 будет в порядке. sha тоже конечно.

Есть ли предложения?

Answer 1

Вам понадобится коммутативная функция объединения, которая boost::hash_combine намеренно не равна , поэтому равные unordered_map, имеющие различный внутренний порядок, имеют одинаковые хэши.Для этого я предлагаю просто кешировать хэш каждого элемента.

template<typename UnorderedMap>
std::size_t hash(const UnorderedMap & um)
{
    boost::hash<typename UnorderedMap::value_type> elem_hash;
    auto combine = [&](size_t acc, typename UnorderedMap::const_reference elem){ return acc ^ elem_hash(elem); };
    return std::accumulate(um.begin(), um.end(), 0, combine);
}

Answer 2

Вы можете попробовать использовать hash_combine() boost для объединения хэша каждой записи. Если вы не хотите использовать boost, вы можете использовать xoring отдельных хеш-значений, чтобы в итоге получить комбинированное хеш-значение.

Кроме того, вы можете пройти ниже ответ, который описывает, как вы можете сравнить 2 карты без использования хеш-комбината:

Ссылка для ответа