c++ - 计算 unordered_map 的运行哈希的最佳方法？

Question

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

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

#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++)是一个身份散列，它有适度的冲突倾向； GCC 和 Clang 通过使用质数桶(相对于 Visual C++ 的 2 次幂选择)在一定程度上减轻了这种情况，但您需要避免不同的键、值条目在 size_t 中发生冲突。哈希值空间，而不是 post-mod-bucket-count，因此最好使用有意义的哈希函数。同样 Visual C++ 的 std::string hash 仅包含沿字符串间隔的 10 个字符(因此它是恒定时间)，但如果您的键和值都是相似的相同长度的长字符串，仅在几个字符上有所不同，那也很容易发生可怕的冲突。 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}) 等)

• 考虑使用基于 boost::hash_combine 的东西相反(假设您确实采纳了上述建议，让模板参数提供散列函数:

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

• 您可以通过避免不必要的哈希表查找来显着提高操作效率(您的 Put 执行 2-4 次表查找，而 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);
  }
  

  • 如果你想进一步优化，你可以创建一个版本GetHashValueForPair返回了 HashKeyPolicy(key) value 并让您传递它以避免在 Put 中对 key 进行两次哈希处理.