基本概念
- 哈希算法： 根据设定的哈希函数H（key）和处理冲突方法将一组关键字映象到一个有限的地址区间上的算法。也称为散列算法、杂凑算法。
- 哈希表： 数据经过哈希算法之后得到的集合。这样关键字和数据在集合中的位置存在一定的关系，可以根据这种关系快速查询。
- 非哈希表： 与哈希表相对应，集合中的 数据和其存放位置没任何关联关系的集合。 由此可见，哈希算法是一种特殊的算法，能将任意数据散列后映射到有限的空间上，通常计算机软件中用作快速查找或加密使用。
- 哈希冲突： 两个不同的输入值，根据同一散列函数计算出的散列值相同的现象叫做碰撞。
常见的Hash函数
- 直接定址法： 直接以关键字k或者k加上某个常数（k+c）作为哈希地址。
- 数字分析法： 提取关键字中取值比较均匀的数字作为哈希地址。
- 除留余数法： 用关键字k除以某个不大于哈希表长度m的数p，将所得余数作为哈希表地址。
- 分段叠加法： 按照哈希表地址位数将关键字分成位数相等的几部分，其中最后一部分可以比较短。然后将这几部分相加，舍弃最高进位后的结果就是该关键字的哈希地址。
- 平方取中法： 如果关键字各个部分分布都不均匀的话，可以先求出它的平方值，然后按照需求取中间的几位作为哈希地址。
- 伪随机数法： 采用一个伪随机数当作哈希函数。
常见的解决冲突方案
开放定址法
从发生冲突的那个单元起，按照一定的次序，从哈希表中找到一个空闲的单元。然后把发生冲突的元素存入到该单元的一种方法。开放定址法需要的表长度要大于等于所需要存放的元素。
在开放定址法中解决冲突的方法有：线行探查法、平方探查法、双散列函数探查法。
开放定址法的缺点在于删除元素的时候不能真的删除，否则会引起查找错误，只能做一个特殊标记。只到有下个元素插入才能真正删除该元素。
线行探查法
线行探查法是开放定址法中最简单的冲突处理方法，它从发生冲突的单元起，依次判断下一个单元是否为空，当达到最后一个单元时，再从表首依次判断。直到碰到空闲的单元或者探查完全部单元为止。平方探查法
平方探查法即是发生冲突时，用发生冲突的单元d[i], 加上 1²、 2²等。即d[i] + 1²，d[i] + 2², d[i] + 3²…直到找到空闲单元。
在实际操作中，平方探查法不能探查到全部剩余的单元。不过在实际应用中，能探查到一半单元也就可以了。若探查到一半单元仍找不到一个空闲单元，表明此散列表太满，应该重新建立。双散列函数探查法
这种方法使用两个散列函数hl和h2。其中hl和前面的h一样，以关键字为自变量，产生一个0至m—l之间的数作为散列地址；h2也以关键字为自变量，产生一个l至m—1之间的、并和m互素的数(即m不能被该数整除)作为探查序列的地址增量(即步长)，探查序列的步长值是固定值l；对于平方探查法，探查序列的步长值是探查次数i的两倍减l；对于双散列函数探查法，其探查序列的步长值是同一关键字的另一散列函数的值。
链地址法（拉链法）
链接地址法的思路是将哈希值相同的元素构成一个同义词的单链表，并将单链表的头指针存放在哈希表的第i个单元中，查找、插入和删除主要在同义词链表中进行。链表法适用于经常进行插入和删除的情况。
注：在java中，链接地址法也是HashMap解决哈希冲突的方法之一，jdk1.7完全采用单链表来存储同义词，jdk1.8则采用了一种混合模式，对于链表长度大于8的，会转换为红黑树存储。
再哈希法
就是同时构造多个不同的哈希函数：
Hi = RHi(key) i= 1,2,3 … k;
当H1 = RH1(key) 发生冲突时，再用H2 = RH2(key) 进行计算，直到冲突不再产生，这种方法不易产生聚集，但是增加了计算时间。
建立公共溢出区
将哈希表分为公共表和溢出表，当溢出发生时，将所有溢出数据统一放到溢出区。
与map的区别
迭代器失效情况
unordered_map:
| 操作 | 失效情况 |
|---|---|
| 所有只读操作 swap std::swap | 决不 |
| clear rehash reserve operator= | 始终 |
| insert emplace emplace_hint operator[] | 仅若重哈希导致 |
| erase | 仅为指向被擦除元素者 |
map (通常实现为红黑树,非强制标准):
| 操作 | 失效情况 |
|---|---|
| insert emplace emplace_hint operator[] | 没有失效情况 |
| erase | 仅为指向被擦除元素者 |
其他
- map是有序的，unordered_map是无序的
- 两者之间的查找速度不同（log(N)和N）
- 由于hash要控制负载率在0-1之间，所以unordered_map消耗空间更大。
- 迭代器失效情况, map更稳健
- 遍历, unordered_map需要逐桶遍历 可能有大量的无效桶 .
- unordered_map不能反向遍历
- O(lgN)和常数级的差别很小。比如10000个元素的map，log_2(N) = 13.28，才不到14次。
- 散列表的时间复杂度仍然是O(N), 性能上map更稳定