如何散列unordered_map？

Question

boost::hash对大多数内置类型(包括容器)具有散列函数。

但正如 function description中所述，范围的哈希算法

对元素的顺序敏感，因此在无序容器中使用它是不合适的

因此，不存在boost::hash专门化的std::unordered_map或boost::unordered_map。

问题是：

是否有一种“简单有效”的方法来散列unordered_map，而无需从头开始重新实现哈希算法？

Answer 1

这里的问题是，存在，不能保证甚至在其中有一个订单。

因此，对项目进行排序很可能不适用于任意无序的容器。你有两个选择：

1. 只是异或所有单个元素的散列。这是最快的。
2. 首先对容器的散列进行排序，然后对其进行散列。这可能会导致更好的哈希。

Answer 2

当然，您可以将unordered_map转换为具有保证顺序的其他数据结构，并使用该结构生成哈希。

更好的方法可能是散列映射中的每个单独元素，将这些散列放入vector中，然后排序并组合散列。例如，请参见How do I combine hash values in 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

Answer 3

我想你可能混淆了哈希是用来做什么的。它用于用于标识元素的键，以确定将它们存储在何处。两个等效的元素应该具有相同的值。

您是否想看看两个无序映射是否等效，并将它们存储在某种容器中？

无序地图的钥匙--这些都是散列的。事实上，除了这样的容器已经存在之外，容器应该被称为hash_map。

但是，好的，假设你真的想存储无序的地图，并比较看两者是否等价。那么，您必须想出一个散列算法，它将返回相同的值，而不管它包含的元素的位置如何。对其所有元素(键和值)进行校验是一种可能的方法。

还请注意，仅仅因为两个元素具有相同的散列值，并不意味着它们是等价的。这仅仅意味着，如果散列值不同，它们肯定不是等价的。事实上，校验和经常用于验证数据，正是出于这个原因。一个错误的校验和证明了数据是无效的，如果给出一个好的公式，一个正确的公式会使它非常有可能，尽管不确定它是否有效。