Хеширование неупорядоченного контейнера без необходимости реализации оператора сравнения для типа

Question

Я хочу хэшировать неупорядоченный контейнер, например unordered_mapа также unordered_set. Для упорядоченного типа, такого как вектор, boost::hash_range(v.begin(). v.end())работает хорошо, но также зависит от порядка, например

      #include <boost/functional/hash.hpp>
#include <functional>
namespace std {
    template<>
    struct hash<std::vector<int>> {
        size_t operator ()(const std::vector<int>& v) const noexcept {
            return boost::hash_range(v.begin(), v.end());
        }
    };
}

Пример такой работы: https://coliru.stacked-crooked.com/a/0544c1b146ebeaa0

boost.org говорит

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

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

Кроме того, для этого потребуется, чтобы каждый тип, который я использую, имел либо >, <, <=или же >=определены, а также ==а также std::hash.

Как я могу хешировать контейнер, чтобы порядок не имел значения?

Answer 1

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

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

Чтобы хэшировать последовательность элементов, не заботясь о порядке, вам понадобится коммутативная хэш-функция, поэтому вы будете ограничены коммутативными операциями (например, XOR). Я не уверен, насколько сильной может быть такая хэш-функция, но для вашего конкретного сценария этого может быть достаточно.

Answer 2

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

Предполагать H1является хеш-функцией для одного элемента и H2является хеш-функцией для списка хеш-значений, то хэш-значение для некоторого неупорядоченного контейнера с элементами A, B и C может быть вычислено как H2(SORT(H1(A), H1(B), H1(C))). По построению результирующее хеш-значение не зависит от порядка. Таким образом, вы также получите более сильное хеш-значение по сравнению с объединением отдельных хэш-значений с использованием коммутативных операций.