关键词：
【中文标题】C++ std::unordered_map 中使用的默认哈希函数是啥？【英文标题】：What is the default hash function used in C++ std::unordered_map?C++ std::unordered_map 中使用的默认哈希函数是什么？ 【发布时间】：2013-10-25 01:24:52 【问题描述】：我正在使用
unordered_map<string, int>
和
unordered_map<int, int>
每种情况下使用什么哈希函数，每种情况下发生冲突的可能性是多少？ 我将在每种情况下分别插入唯一字符串和唯一 int 作为键。
我有兴趣了解字符串和 int 键的哈希函数算法及其冲突统计信息。
【问题讨论】：
我觉得符合标准。不确定 unorderd_map 是什么。 unordered_map 就像哈希表...C++98 和 C++11 中的默认哈希函数有变化吗？ 您标记了这个 C++11，但询问了 TR1。是哪个？ 对不起@John Dibling，我将它标记为 C++11。我也编辑了标题，因为我认为这个问题更有意义；现在答案可以参考正式的标准。随意改回来；我发现你在这个网站上的经验比我多。 那你为什么提到tr1命名空间？
【参考方案1】：
使用了函数对象std::hash<>。
标准特化适用于所有内置类型，以及一些其他标准库类型
例如std::string 和std::thread。查看完整列表的链接。
对于要在 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++ 的外部函数。更多搜索使我找到了this file，其中指出：
// 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。
【讨论】：
我有兴趣了解在字符串和整数键及其冲突统计的情况下哈希函数的算法。 @Medicine：标准没有规定，由库实现来决定最好的方法。您必须查看您的本地实施。例如，这个答案现在包括 GCC 的特定选择。 @Medicine：Visual Studio（自 VS2012 起）的默认哈希算法是Fowler–Noll–Vo (FNV-1a)。
感谢@Avidanborisov，我的字符串都是独一无二的，大小在 14 到 21 之间，包括英文字母 _ 数字
链接到MurmurHash 源代码。也可通过github 获得。【参考方案2】：
GCC C++11 使用“MurmurHashUnaligned2”，作者 Austin Appleby
>虽然散列算法依赖于编译器，但我将在 GCC C++11 中展示它。 @Avidan Borisov astutely discovered 用于字符串的 GCC 散列算法是 Austin Appleby 的“MurmurHashUnaligned2”。我做了一些搜索，在 Github 上找到了 GCC 的镜像副本。因此：
用于unordered_map（哈希表模板）和unordered_set（哈希集模板）的 GCC C++11 哈希函数如下所示。
代码：
// Implementation of Murmur hash for 32-bit size_t.
size_t _Hash_bytes(const void* ptr, size_t len, size_t seed)
const size_t m = 0x5bd1e995;
size_t hash = seed ^ len;
const char* buf = static_cast<const char*>(ptr);
// Mix 4 bytes at a time into the hash.
while (len >= 4)
size_t k = unaligned_load(buf);
k *= m;
k ^= k >> 24;
k *= m;
hash *= m;
hash ^= k;
buf += 4;
len -= 4;
// Handle the last few bytes of the input array.
switch (len)
case 3:
hash ^= static_cast<unsigned char>(buf[2]) << 16;
[[gnu::fallthrough]];
case 2:
hash ^= static_cast<unsigned char>(buf[1]) << 8;
[[gnu::fallthrough]];
case 1:
hash ^= static_cast<unsigned char>(buf[0]);
hash *= m;
;
// Do a few final mixes of the hash.
hash ^= hash >> 13;
hash *= m;
hash ^= hash >> 15;
return hash;
Austin Appleby 哈希函数的最新版本是“MurmurHash3”，它已发布到公共领域！
奥斯汀州in his readme：
SMHasher 套件还包括 MurmurHash3，这是 MurmurHash 函数系列中的最新版本 - 新版本更快、更健壮，其变体可以产生 32 位和 128 位哈希在 x86 和 x64 平台上都有效地实现了价值。
MurmurHash3 的源代码见这里：
-
MurmurHash3.h
MurmurHash3.cpp
最棒的是！？这是公共领域软件。这是正确的！文件顶部状态：
// MurmurHash3 was written by Austin Appleby, and is placed in the public // domain. The author hereby disclaims copyright to this source code.
所以，如果您想在您的开源软件、个人项目或专有软件中使用 MurmurHash3，包括在 C 中实现您自己的哈希表，那就去吧！
如果您想要构建说明来构建和测试他的 MurmurHash3 代码，我在这里写了一些：https://github.com/ElectricRCAircraftGuy/smhasher/blob/add_build_instructions/build/README.md。希望this PR I've opened 被接受，然后他们将最终出现在他的主仓库中。但是，在那之前，请参阅我的 fork 中的构建说明。
对于其他散列函数，包括djb2，以及 K&R 散列函数的 2 个版本...
...（一个显然很糟糕，一个非常好），请在此处查看我的另一个答案：hash function for string。
另见：
-
https://en.wikipedia.org/wiki/MurmurHash
进一步研究：看看这些哈希函数速度基准：https://github.com/fredrikwidlund/hash-function-benchmark（感谢@lfmunoz for pointing this out）
【讨论】：
github.com/fredrikwidlund/hash-function-benchmark 基准包括 MurmerHash3 和常规 C++ 11 哈希。测量的性能存在很大差异。如果两者都使用相同的算法，这没有意义 @lfmunoz，感谢分享基准。虽然它们不是相同的算法。 GCC 对 C++11 的实现使用了MurmurHashUnaligned2。 MurmerHash3 是一个单独的算法，也是由 Austin Appleby 开发的。它们不是同一个算法。 MurmerHash3 是他最新和最伟大的作品，不属于 GCC 的 C++11。我会假设MurmerHash3 比 Murmer Hash 2 更好（在速度上），否则将它作为后续版本发布几乎或没有意义，除非它是一种权衡并且它可能更慢但有一些其他优势例如更好的存储桶分布和更少的冲突。
@lfmunoz，同样，该基准图表的顶部显示clang v3.6.0。这意味着他们不使用 GCC 编译器，所以我不能说他们使用的是什么哈希算法。这可能是完全不同的东西。你得去拉那个版本的clang编译器的源代码看看。
拼写修正：MurmerHash3 应该是 MurmurHash3 (e --> u)。C++ std::unordered_map 中使用的默认哈希函数是啥？
】C++std::unordered_map中使用的默认哈希函数是啥？【英文标题】：WhatisthedefaulthashfunctionusedinC++std::unordered_map?C++std::unordered_map中使用的默认哈希函数是什么？【发布时间】：2013-10-2501:24:52【问题描述】：我正在使用unordered_map<strin... 查看详情
C++ 将预先保留的哈希映射（std::unordered_map）与整数键和连续数据数组（std::vector）进行比较
】C++将预先保留的哈希映射（std::unordered_map）与整数键和连续数据数组（std::vector）进行比较【英文标题】：C++comparingapre-reservedhashmap(std::unordered_map)withintegerkeyandcontiguousdataarray(std::vector)【发布时间】：2021-01-1116:35:03【问题描述... 查看详情
Javascript中C++ std::unordered_map<char, int> 的等价物是啥？
】Javascript中C++std::unordered_map<char,int>的等价物是啥？【英文标题】：WhatistheequivalentofC++std::unordered_map<char,int>inJavascript?Javascript中C++std::unordered_map<char,int>的等价物是什么？【发布时间】：2018-08-2000:33:46【问题描述 查看详情
与 C++ unordered_map 的并行性
】与C++unordered_map的并行性【英文标题】：ParallelismwithC++unordered_map【发布时间】：2015-07-1019:28:55【问题描述】：我有一个std::unordered_map<std::string,int64_t>sMap类型的unordered_map。这包含许多字符串和与每个字符串相关的“权... 查看详情
使用 std::string 作为字典顺序的键对 unordered_map 进行排序
】使用std::string作为字典顺序的键对unordered_map进行排序【英文标题】：Sortingaunordered_mapwithastd::stringasakeyinlexicographicalorder【发布时间】：2017-10-2420:41:46【问题描述】：上周我参加了Catalysts编码竞赛，现在我正在尝试使用更多高级C... 查看详情
带有 std::any 值的 unordered_map 不能使用 any_cast 字符串
】带有std::any值的unordered_map不能使用any_cast字符串【英文标题】：unordered_mapwithstd::anyvaluescannotany_caststring【发布时间】：2019-06-1400:50:15【问题描述】：我是C++新手，我正在研究std::unordered_map和std::any。我创建了一个示例演示，它... 查看详情
gcc std::unordered_map 实现速度慢吗？如果是这样 - 为啥？
】gccstd::unordered_map实现速度慢吗？如果是这样-为啥？【英文标题】：Isgccstd::unordered_mapimplementationslow?Ifso-why?gccstd::unordered_map实现速度慢吗？如果是这样-为什么？【发布时间】：2012-07-2118:45:48【问题描述】：我们正在用C++开发一... 查看详情
std::reduce 与 std::unordered_map
】std::reduce与std::unordered_map【英文标题】：std::reducewithstd::unordered_map【发布时间】：2019-03-1106:22:11【问题描述】：我有一个unordered_map或vectors，我正在尝试使用std::reduce来获取地图中所有向量中所有值的总和。我当前的功能代码（... 查看详情
std::unordered_map::clear() 做啥？
】std::unordered_map::clear()做啥？【英文标题】：Whatdoesstd::unordered_map::clear()do?std::unordered_map::clear()做什么？【发布时间】：2020-09-0217:04:02【问题描述】：我有一段简单的代码：#pragmaGCCoptimize("O0")#include<unordered_map>intmain()std::unor 查看详情
std::hash 特化仍未被 std::unordered_map 使用
】std::hash特化仍未被std::unordered_map使用【英文标题】：std::hashspecializationremainsunusedbystd::unordered_map【发布时间】：2015-05-0712:46:31【问题描述】：我正在尝试通过为constchar提供特化来扩展std::hash<T>，以便我可以使用constcha... 查看详情
std::unordered_map::operator[] - 为啥有两个签名？
】std::unordered_map::operator[]-为啥有两个签名？【英文标题】：std::unordered_map::operator[]-whytherearetwosignatures?std::unordered_map::operator[]-为什么有两个签名？【发布时间】：2015-07-0214:10:25【问题描述】：在C++11中，std::unordered_map::operator[]有... 查看详情
为啥我不能增加 std::unordered_map 迭代器？
】为啥我不能增加std::unordered_map迭代器？【英文标题】：Whycan\'tIincrementstd::unordered_mapiterator?为什么我不能增加std::unordered_map迭代器？【发布时间】：2016-06-1906:06:34【问题描述】：std::unordered_map<int,int>_cache;std::vector<std::unord... 查看详情
在 std::map 和 std::unordered_map 之间进行选择 [重复]
】在std::map和std::unordered_map之间进行选择[重复]【英文标题】：Choosingbetweenstd::mapandstd::unordered_map[duplicate]【发布时间】：2011-04-2314:11:32【问题描述】：既然std在unordered_map中有一个真正的哈希映射，为什么（或何时）我仍想在实际... 查看详情
两个 std::unordered_map 的交集
】两个std::unordered_map的交集【英文标题】：Intersectionoftwostd::unordered_map【发布时间】：2020-06-3016:58:53【问题描述】：我有两个std::unordered_mapstd::unordered_map<int,int>mp1;std::unordered_map<int,int>mp2;我需要找到键值对的交集并将其... 查看详情
如何找到 std::unordered_map 的当前容量？
】如何找到std::unordered_map的当前容量？【英文标题】：Howtofindthecurrentcapacityofstd::unordered_map?【发布时间】：2020-06-1007:10:47【问题描述】：std::unordered_map和std::vector都具有reserve方法，这增加了集合的容量，因此可以在不扩大内部缓... 查看详情
如何在 std::tuple 中合并 std::unordered_map？
】如何在std::tuple中合并std::unordered_map？【英文标题】：Howtomergestd::unordered_mapinsidestd::tuple?【发布时间】：2019-07-0615:57:01【问题描述】：我想创建一个类，里面有一个std::tuple和std::unordered_map。我想创建一个方法来合并元组内的地... 查看详情
std::unordered_map 上的线程安全包装器
】std::unordered_map上的线程安全包装器【英文标题】：threadsafewrapperonstd::unordered_map【发布时间】：2015-01-0610:16:57【问题描述】：我正在尝试在std::unordered_map之上实现一个线程安全的包装类下面的开始和结束功能是否安全？std::unorde... 查看详情
向 std::unordered_map 插入数据时访问冲突
】向std::unordered_map插入数据时访问冲突【英文标题】：Accessviolationwhileinsertingdatatostd::unordered_map【发布时间】：2019-05-2310:17:05【问题描述】：我正在从数据库中读取plc的读/写配置并将它们存储在std::unordered_map中。每当我尝试在std... 查看详情