C++ std::unordered_map 中使用的默认哈希函数是什么？

我在用

unordered_map<string, int>

and

unordered_map<int, int>

每种情况下使用什么哈希函数以及每种情况下发生冲突的几率是多少？ 我将分别插入唯一的字符串和唯一的整数作为每种情况下的键。

我有兴趣了解字符串和整数键的哈希函数算法及其碰撞统计信息。

函数对象std::hash<> http://en.cppreference.com/w/cpp/utility/hash用来。

所有内置类型和其他一些标准库类型都存在标准专业化 例如std::string and std::thread。请参阅链接以获取完整列表。

对于要在 a 中使用的其他类型std::unordered_map，你必须专门化std::hash<>或创建您自己的函数对象。

碰撞的机会完全取决于实现，但考虑到整数被限制在定义的范围内，而字符串理论上无限长，我认为与字符串发生碰撞的机会要大得多。

至于 GCC 中的实现，内置类型的特化仅返回位模式。以下是它们的定义方式bits/functional_hash.h:

  /// Partial specializations for pointer types.
  template<typename _Tp>
    struct hash<_Tp*> : public __hash_base<size_t, _Tp*>
    {
      size_t
      operator()(_Tp* __p) const noexcept
      { return reinterpret_cast<size_t>(__p); }
    };

  // Explicit specializations for integer types.
#define _Cxx_hashtable_define_trivial_hash(_Tp)     \
  template<>                        \
    struct hash<_Tp> : public __hash_base<size_t, _Tp>  \
    {                                                   \
      size_t                                            \
      operator()(_Tp __val) const noexcept              \
      { return static_cast<size_t>(__val); }            \
    };

  /// Explicit specialization for bool.
  _Cxx_hashtable_define_trivial_hash(bool)

  /// Explicit specialization for char.
  _Cxx_hashtable_define_trivial_hash(char)

  /// ...

专业化为std::string定义为：

#ifndef _GLIBCXX_COMPATIBILITY_CXX0X
  /// std::hash specialization for string.
  template<>
    struct hash<string>
    : public __hash_base<size_t, string>
    {
      size_t
      operator()(const string& __s) const noexcept
      { return std::_Hash_impl::hash(__s.data(), __s.length()); }
    };

进一步的搜索使我们得到：

struct _Hash_impl
{
  static size_t
  hash(const void* __ptr, size_t __clength,
       size_t __seed = static_cast<size_t>(0xc70f6907UL))
  { return _Hash_bytes(__ptr, __clength, __seed); }
  ...
};
...
// Hash function implementation for the nontrivial specialization.
// All of them are based on a primitive that hashes a pointer to a
// byte array. The actual hash algorithm is not guaranteed to stay
// the same from release to release -- it may be updated or tuned to
// improve hash quality or speed.
size_t
_Hash_bytes(const void* __ptr, size_t __len, size_t __seed);

_Hash_bytes是一个外部函数libstdc++。更多的搜索让我发现这个文件 http://gcc.gnu.org/git/?p=gcc.git;a=blob_plain;f=libstdc%2b%2b-v3/libsupc%2b%2b/hash_bytes.cc;hb=HEAD，其中指出：

// This file defines Hash_bytes, a primitive used for defining hash
// functions. Based on public domain MurmurHashUnaligned2, by Austin
// Appleby.  http://murmurhash.googlepages.com/

因此，GCC 对字符串使用的默认哈希算法是 MurmurHashUnaligned2。