c++ - std::unordered_map:渐近 {search,insert,remove} 在键的大小和数据类型方面的表现

Question

我在 C++11 中使用 std::unordered_map。我在字符串键和复合数据类型之间做出决定(比如将两个 long 放在一个结构中以保存 UUID)。

当 hashmap 使用 std::string 键时与 hashmap 使用其他一些简单数据类型作为键时，是否有一种简单的方法来确定查找、插入、删除等的性能特征？

一旦我选择了一种数据类型:std::unordered_map 的搜索、删除和插入操作都是常数时间在 map 中的元素数量，但是如果我有一个很长的键 (例如，128 位)，我开始怀疑这些操作在 key 大小方面的性能。

这是值得关注的事情，还是差异可以忽略不计？

Answer 1

我认为您误解了 std::unordered_map 的复杂性保证的插入、删除和查找操作。最坏情况O(size())只有当你为 Key 实现了一个糟糕的散列函数时才会提到产生大量冲突的类型，但不同的键比较不相等。

说你有

struct terrible_hash
{
  std::size_t operator()(int i) const
  { return 42; }
};

std::unordered_map<int, foo, terrible_hash> m;

在上面的映射中所有新键的插入都是O(m.size())因为函数将被迫线性搜索每个元素，因为它们都散列为相同的值。

给定一个合适的哈希函数，这些操作应该是(摊销的)常数时间。

回到你的问题string与 128 位数字 (UUID) 作为 key 类型；这取决于您的实现，但通常后者应该更快。我这样说是基于以下假设:

• 典型 hash<string>特化将遍历整个字符串并对每个字节执行按位数学运算并将其与现有结果组合。例如，部分/简化的实现取自 VS2013:

  size_t _Val = 14695981039346656037ULL;
  for (size_t _Next = 0; _Next < _Count; ++_Next)
  {
    _Val ^= (size_t)_First[_Next];
    _Val *= 1099511628211ULL;
  }
  return _Val;
  

• 使用您的 128 位 key 类型，您应该能够组合两个 64 位字以生成具有更少操作的散列。例如，您可以定义一个辅助函数模板，并使用它来组合来自 64 位单词的哈希值。

  template <class T>
  inline void hash_combine(std::size_t& seed, const T& v)
  {
      std::hash<T> hasher;
      seed ^= hasher(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);
  }
  

  魔数(Magic Number)是从 boost::hash_combine 偷来的.再次查看 std::hash<uint64_t> 的 MSVC 实现，它们通过 unsigned char * 别名为 64 位整数并调用我上面粘贴的算法，但在这种情况下，迭代次数是已知的，编译器将能够更好地优化。

话虽如此，如果性能非常重要，您需要衡量两种键选择，然后再做出决定。