趣文：哈希表哪家强?(程序员那些事上的一篇趣文）
原文链接： https://mp.weixin.qq.com/s/cZ-Q2aef9MReOoRWRjFolg
参赛语言包括go(map), c++(unordered_map), python(dict), C# ( HashTable), java(HashMap)
评比角度1. 存储结构与冲突解决2. 哈希到位置映射3. 初始容量与扩容
文章目录
1. 存储结构和冲突解决
存储结构基本都是数组，解决冲突的方法有3类
链表法
go和c++选择用链表解决冲突，当冲突太多，链表会很长，则查找起来耗时较多
红黑树法
java使用当链表长度大于8时，转化为红黑树的操作，来降低查找性能消耗
多hash算法
c#使用多种hash算法，当一种有冲突，换另一种接着算，直到找到空位进行存储的方法。
开放寻址法
python采用开放寻址的方法，如果发现了冲突，就按照制定的策略从这个位置往后找，直到找到有空的位置存储。
2. hash到位置的映射
简单说就是怎么把hash值映射到比hash表定义长度小的范围内，且映射要尽量均匀，这样可以减少冲突。
取余
c++，go，c# 使用的都是简单hash % length的方法
取低位
java和python采用用位与运算取hash值低位的方法代替取余提高计算速度。hash值对位置的映射主要考虑的就是将hash值归一化成小于length的数。下面公式的原理是hash表的长度都是2的n次幂，则其-1运算为除高位之外所有位数都为1的二进制，进行位与运算，则为低位截取。
但是由于很多数，譬如18 的二进制是0001 0010，34 的二进制是0010 0010，低位都是相同的，直接截取会增加冲突的概率，因为java在进行与运算映射之前，对 hash 值进行一个处理，具体来说就是将其高 16 位与低 16 位进行一个异或运算，如此一来，最终参与与运算的部分就融合了原始 hash 的全部信息，而不仅仅是低位。
3. 初始容量与扩容
java初始容量16，当负载因子达到0.75进行扩容，扩容时容量得是 2 的指数次方
python默认初始容量是 8，扩容的时候也是要求是2的指数次方，负载因子是 2/3
C# 初始容量是 3，负载因子是 0.72。容量大小方面就没有 2 的指数次方的要求了，而是要求一个素数。之所以要求素数的原因，是因为使用的求模运算进行的映射，使用素数的话，冲突会少一些。
c++ 扩容使用的也是素数，是提前封装好的一个表，用的时候去拿就可以了
彩蛋问题：为什么c++中hash结构叫unordered_map而不是hash***
https://blog.csdn.net/chen134225/article/details/83106569
c++ 11标准库中8种关联容器类型map, set, multimap, multiset, unordered_map, unordered_set, unordered_multimap, unordered_multiset, 没有hash_map。
且注意map与unordered_map尽管都叫map。map的底层是红黑树，unordered_map底层是hash，有很大的区别。
为什么不叫hash**，猜测是被捷足先登了，有结构叫hash map了，但是标准库并不想收录这个结构，于是自己又实现了个unorder_map收录进去了。