从C语言到C++_30(哈希)闭散列和开散列(哈希桶)的实现（中）：https://developer.aliyun.com/article/1522314
3. 开散列与闭散列比较
开散列也就是哈希桶，看起来每个节点中多了一个指针，比闭散列存放的数据大，但是它空间利用率高，负载因子大于1的时候才会扩容。
闭散列方式中必须有大量的空闲空间来保证搜索的效率，二次探测甚至要求负载因子必须小于等于0.7，并且表项所占的空间比哈希桶大的多。
在空间利用率上，哈希桶比闭散列更有优势。
在搜索上效率上，无论是开散列还是闭散列，都会通过哈希函数的映射关系之间在定位在表项中，然后在查询常数次，所以这两种方式的时间复杂度都是O（1）。
只是闭散列中，负载因子越多，哈希碰撞的概率就越大，查找时耗费的时间就比哈希桶长。
综合考虑，哈希结构的底层大多使用哈希桶结构，也就是开散列方式。
而且当有极端情况：哈希桶的单链表很长时，可以将挂的桶改成红黑树结构来提高效率。
前面我们测试过unordered_set（哈希表）接口的速率，慢的也只是插入，因为插入要扩容，如果提前知道要插入多少数据，提前reserve一下，插入效率能比se（红黑树）t还好一点。
总结：
哈希表中，尤其值得我们学习的地方，一个是闭散列中，使用一个状态标志来标识哈希表中元素的状态，还有就是使用仿函数来将自定义类型转换成整形用于除留余数法。
虽然很大的篇幅在写闭散列，但是哈希桶才是高频使用的结构，而且哈希桶是建立在闭散列的基础上改进的。
4. 哈希笔试选择题
1. 下面关于哈希说法正确的是（）
A .哈希是一种查找的方法，不是数据结构
B .采用哈希方式解决问题时，可以不用哈希函数
C .哈希查找的时间复杂度一定是O(1)
D .哈希是以牺牲空间为代价，提高查询的效率
2. 散列文件使用散列函数将记录的关键字值计算转化为记录的存放地址。由于散列函数不是一对一的关系，所以选择好的（）方法是散列文件的关键。
A .散列函数
B .除余法中的质数
C .冲突处理
D .散列函数和冲突处理
3. 散列函数有一个共同性质，即函数值应按（）取其值域的每一个值。
A .最大概率
B .最小概率
C .同等概率
D .平均概率
4. 解决散列法中出现冲突问题常采用的方法是()
A .数字分析法、除余法、平方取中法
B .数字分析法、除余法、线性探测法
C .数字分析法、线性探测法、多重散列法
D .线性探测法、多重散列法、链地址法
5. 将10个元素散列到100000个单元的哈希表中,则()产生冲突
A .一定会
B .一定不会
C .仍可能会
D .以上都不对
6. 下面关于哈希冲突说法正确的是（）
A .哈希冲突是可以通过设计好的哈希函数来杜绝的
B .哈希冲突是无法避免的
C .哈希冲突是不同的元素，通过不同的哈希函数而产生相同的哈希地址而引起的
D .哈希冲突产生的原因一定是插入了相同的元素
7. 已知有一个关键字序列：（19，14,23,1,68,20,84,27,55,11,10,79）散列存储在一个哈希表中，若散列函数为H（key）=key%7，并采用链地址法来解决冲突，则在等概率情况下查找成功的平均查找长度为()
A .1.5
B .1.7
C .2.0
D .2.3
8. 已知某个哈希表的n个关键字具有相同的哈希值，如果使用二次探测再散列法将这n个关键字存入哈希表，至少要进行（）次探测。
A .n-1
B .n
C .n+1
D .n(n+1)
E .n(n+1)/2
F .1+n(n+1)/2
9. 采用开放定址法处理散列表的冲突时，其平均查找长度？ （）
A .高于链接法处理冲突
B .高于二分查找
C .低于链接法处理冲突
D .低于二分查找
10. 采用线性探测法处理散列时的冲突,当从哈希表删除一个记录时,不应将这个记录的所在位置置空,因为这会影响以后的查找()
A .对
B .错
C .不一定
D .以上说法都不对
11. 用哈希（散列）方法处理冲突（碰撞）时可能出现堆积（聚集）现象，下列选项中，会受堆积现象直接影响的是 ()
A .存储效率
B .数列函数
C .装填（装载）因子
D .平均查找长度
答案
1 D
A：错误，哈希是一种用来进行高效查找的数据结构，查找的时间复杂度平均为O(1)
B：错误，哈希之所以高效，是引用使用了哈希函数将元素与其存储位置之间建立了一一对应的关 系，因此必须使用哈希函数
C：错误，不一定，因为存在哈希冲突，一般基本都是O(1)
D：正确，采用哈希处理时，一般所需空间都会比元素个数多，否则产生冲突的概率就比较大，影 响哈希的性能
2 D
要使哈希高效：选择好的哈希函数非常关键
好的哈希函数可以减少发生冲突的概率
万一发生冲突，好的处理好戏冲突的方法也比较关键，否则冲突处理不当，也会增加后序元素冲突的概率
3 C
哈希函数设计原则：
1. 哈希函数应该尽可能简单
2. 哈希函数的值域必须在哈希表格的范围之内
3. 哈希函数的值域应该尽可能均匀分布，即取每个位置应该是等概率的
4 D
注意要区分清楚：哈希冲突的处理方法和哈希函数
哈希函数作用是：建立元素与其存储位置之前的对应关系的，在存储元素时，先通过哈希函数计算 元素在哈希表格中的存储位置，然后存储元素。好的哈希函数可以减少冲突的概 率，但是不能够绝对避免，万一发生哈希冲突，得需要借助哈希冲突处理方法来 解决。
常见的哈希函数有：直接定址法、除留余数法、平方取中法、随机数法、数字分析法、叠加法等
常见哈希冲突处理：闭散列（线性探测、二次探测）、开散列(链地址法)、多次散列
5 C
只要想哈希表格中存储的元素超过两个，就有可能存在哈希冲突
6 B
A：错误，哈希冲突是不能杜绝的，这个与存储的元素以及哈希函数相关
B：正确
C：错误，哈希冲突是不同的元素，通过相同的哈希函数而产生相同的哈希地址而引起的，注意仔 细看选项
D：错误，不同元素在计算出相同的哈希值时就会冲突
7 A 画出来：
[0] [1] [2] [3] [4] [5] [6]
14 1 23 10 11 19 20
84 79 68 27
55
14、1、23、10、11、19、20: 比较1次就可以找到
84、79、68、27：需要比较两次才可以找到
55: 需要比较三次才可以找到
总的比较次数为：7+4*2+3=18，总共有12个元素
故：等概率情况下查找成功的平均查找长度为：18/12 = 1.5
8 E
元素1：探测1次
元素2：探测2次
元素3：探测3次
......
元素n：探测n次
故要将n个元素存入哈希表中，总共需要探测：1+2+3+...+n = n*(n+1)/2
9 A
开放定址法一旦产生冲突，冲突容易连在一起，引起一连篇的冲突，链地址法一般不会
10 A
线性探测采用未删除法，当从哈希表中删除某个元素时，并没有将该元素真正的删除掉，而是采用标记的方式处理，但是不能直接将该位置标记为空，否则会影响从该位置产生冲突的元素的查找。
11 D
冲突越多，查找时比较的次数就越多，对平均查找长度影响比较大。
本篇完。
下一篇：用哈希桶封装unordered_set和unordered_map。
