为 unordered_map 计算运行散列的最佳方法？

Question

我有一个简单的包装器 - class for std::unordered_map 更新 unordered_map 内容的运行哈希码，作为键值添加或删除对；这样我就不必遍历整个内容来获取集合的当前哈希码。它通过在添加新键值对时添加到 _hash 成员变量，并在删除现有键值对时从 _hash 成员变量中减去来实现。这一切都很好（但如果你想要我的意思的代码示例，请参阅下面的玩具实现）。

我唯一担心的是，我怀疑从最小化散列值冲突的可能性的角度来看，简单地从 _hash 中添加和减去值可能不是最佳做法。有没有数学上更好的方法来计算 table 的运行-哈希码，它仍然可以保留我从 table 中有效地 add/remove 项目的能力（即没有迫使我每次都从头开始迭代 table 来重建哈希码？）

#include <functional>
#include <unordered_map>
#include <string>
#include <iostream>

template<typename KeyType, typename ValueType> class UnorderedMapWithHashCode
{
public:
   UnorderedMapWithHashCode() : _hash(0) {/* empty */}

   void Clear() {_map.clear(); _hash = 0;}

   void Put(const KeyType & k, const ValueType & v)
   {
      Remove(k);  // to deduct any existing value from _hash
      _hash += GetHashValueForPair(k, v);
      _map[k] = v;
   }

   void Remove(const KeyType & k)
   {
      if (_map.count(k) > 0)
      {
         _hash -= GetHashValueForPair(k, _map[k]);
         _map.erase(k);
      }
   }

   const std::unordered_map<KeyType, ValueType> & GetContents() const {return _map;}

   std::size_t GetHashCode() const {return _hash;}

private:
   std::size_t GetHashValueForPair(const KeyType & k, const ValueType & v) const
   {
      return std::hash<KeyType>()(k) + std::hash<ValueType>()(v);
   }

   std::unordered_map<KeyType, ValueType> _map;
   std::size_t _hash;
};

int main(int, char **)
{
   UnorderedMapWithHashCode<std::string, int> map;
   std::cout << "A:  Hash is " << map.GetHashCode() << std::endl;

   map.Put("peanut butter", 5);
   std::cout << "B:  Hash is " << map.GetHashCode() << std::endl;

   map.Put("jelly", 25);
   std::cout << "C:  Hash is " << map.GetHashCode() << std::endl;

   map.Remove("peanut butter");
   std::cout << "D:  Hash is " << map.GetHashCode() << std::endl;

   map.Remove("jelly");
   std::cout << "E:  Hash is " << map.GetHashCode() << std::endl;

   return 0;
}

Answer 1

您的概念非常好，只是实施可以改进：

您可以将散列函数用作默认为相关 std::hash 实例化的模板参数；请注意，对于数字来说，std::hash<> 是一个身份散列是很常见的（GCC、Clang、Visual C++），这是 mod 极易发生冲突的； GCC 和 Clang 通过使用质数桶（相对于 Visual C++ 的 2 次幂选择）在一定程度上减轻了这种情况，但是您需要避免不同的键、值条目在 size_t 哈希值 space，而不是 post-mod-bucket-count，因此最好使用有意义的哈希函数。类似地，Visual C++ 的 std::string 散列仅包含 10 个字符 spaced 沿字符串（因此它是常数时间），但如果您的键和值都是相似的相同长度的长字符串，只有几个字符不同也会发生可怕的碰撞。 GCC 对字符串使用适当的哈希函数 - MURMUR32。
return std::hash<KeyType>()(k) + std::hash<ValueType>()(v); 通常是一个平庸的想法，在使用身份哈希函数时是一个糟糕的想法（例如 h({k,v}) == k + v，所以 h({4,2}) == h({2,4}) == h({1,5}) 等）

考虑使用基于的东西（假设您采纳了上述建议让模板参数提供散列函数：

 auto key_hash = KeyHashPolicy(key);
 return (key_hash ^ ValueHashPolicy(value)) +
        0x9e3779b9 + (key_hash << 6) + (key_hash >> 2);

您可以通过避免不必要的散列 table 查找（您的 Put 执行 2-4 table 查找，并且 Remove 做 1-3):

void Put(const KeyType& k, const ValueType& v)
{
    auto it = _map.find(k);
    if (it == _map.end()) {
        _map[k] = v;
    } else {
        if (it->second == v) return;
        _hash -= GetHashValueForPair(k, it->second);
        it->second = v;
    }
    _hash += GetHashValueForPair(k, v);
}

void Remove(const KeyType& k)
{
    auto it = _map.find(k);
    if (it == _map.end()) return;
    _hash -= GetHashValueForPair(k, it->second);
    _map.erase(it);
}

如果你想进一步优化，你可以创建一个返回 HashKeyPolicy(key) 值的 GetHashValueForPair 版本，让你传入它以避免在 Put 中对密钥进行两次哈希处理.

为 unordered_map 计算运行散列的最佳方法？

Best way to calculate a running hash for an unordered_map?

c++

hash

unordered-map

为 unordered_map 计算 运行 散列的最佳方法？

Best way to calculate a running hash for an unordered_map?

c++

hash

unordered-map

为 unordered_map 计算运行散列的最佳方法？