1. Hash Table
我们都知道，二叉树、红黑树等数据结构，它们的查找都是先从根节点开始查找，从节点取出数据或者索引与查找值进行比较。
那么，有没有一种函数H，根据这个函数和查找关键字 Key，可以直接确定查找值所在的位置，而不需要一个个比较。这样叫“预先知道” Key 所在的位置，直接找到数据，提升效率。即：
地址index = H(key)
说白了，hash函数功能就是根据 key 计算出应该存储地址的位置，而哈希表是基于哈希函数建立的一种查找表。
2. 哈希函数的构造方法
根据前人经验，统计出集中常用 hash 函数构造方法
2.1. 直接定制法
哈希函数为关键字的线性函数，如 H(key) = a * key + b，这种构造方法比较简单，均匀。但是有很大限制，仅限与地址大小 = 关键字集合的情况。
2.2. 数字分析法
假设关键字集合中的每个关键字 key 都是由s位数字组成（k1,k2,……,kn）,分析 key 中的全体数据，并从中提取分布均匀的若干位或他们的组合构成全体。
使用举例：假设要保存的集合中 key 由 5 位不同的数字构成。并且这些数字分布均匀，我们可以提取其中一位，代表数据保存的地址。H(key) = key % 100000。
此种方法通常用于数字位数较长的情况，要求数字存在一定的规律，其次必须知道数字的分布情况。
2.3. 平方取中法
如果关键字的每一位都有某些数字重复出现频率很高的现象，可以先求关键字的平方值，通过平方扩大差异，而后取中间数位作为最终存储地址。
使用举例：
比如：key = 1234 1234^2 = 1522756 取 227 作hash地址
比如：key = 4321 4321^2 = 18671041 取 671 作hash地址
这种方法适合事先不知道数据并且数据长度较小的情况。
2.4. 折叠法
如果数字的位数很多，可以将数字分割为几个部分，取他们的叠加和作为hash地址。
使用举例：
比如 key=123 456 789
我们可以取 1368(123+456+789=1368) 作为 hash 地址。
该方法适用于数字位数较多且事先不知道数据分布的情况。2.5. 除留余数法（最常用）
H（key）=key MOD p （p<=m m为表长） 很明显，如何选取p是个关键问题。
使用举例
比如我们存储3 6 9，那么p就不能取3
因为 3 MOD 3 == 6 MOD 3 == 9 MOD 3
p应为不大于m的质数或是不含20以下的质因子的合数，这样可以减少地址的重复（冲突）
比如key = 7，39，18，24，33，21 时取表长m为9 p为7 那么存储如下：
| Key | 7 | 21（冲突后移） | 24 | 39 | 18（冲突后移） | 33（冲突后移） |
2.6. 随机数法
H（key）= random (key) 取关键字的随机函数为它们的散列地址。
哈希函数设计的考虑因素
- 计算散列地址所需要的时间（即 hash 函数本身不要太复杂）
- 关键字的长度
- 表长
- 关键字分布是否均匀，是否有规律可循
- 设计的 hash 函数在充分考虑了以上因素的情况下尽量减少冲突。
3. 哈希冲突
上面已经提到，不同 key 通过 hash 函数产生相同的地址，即 H（key1） == H (key2),此时，key1 和 key2 就发生了 hash 冲突。
4. 哈希冲突的解决方案
不管 hash 函数设计的如何巧妙，总会有特殊的 key 导致 hash 冲突， 特别是对童泰查找表来说。
4.1. 开放定制法
首先有一个H（key）的哈希函数。
如果H（key1）= H（keyi），那么 keyi 存储位置 Hi = (H(key)+di) MOD m。其中 m 是表长。
di 有三种取法：
- 线性探测再散列： di = c * i。
- 平方探测再散列： di = i * i。
- 随机探测再散列：di 是 一个伪随机数。
4.2. 链地址法
产生hash冲突后在存储数据后面加一个指针，指向后面冲突的数据。
4.3 公共溢出区法
建立一个特殊存储空间，专门存放冲突的数据。此种方法适用于数据和冲突较少的情况。
4.4. 再散列法
准备若干个hash函数，如果使用第一个hash函数发生了冲突，就使用第二个hash函数，第二个也冲突，使用第三个……
5. 哈希表的查找
5.1. 哈希表查找过程
查找过程和造表过程一致，假设采用开放定址法处理冲突，则查找过程为：
对于给定的 key，计算 hash 地址 index = H(key)。
如果数组 arr[index] == null, 则查找不成功；
如果数组 arr[index] == key，则查找成功；
如果 （arr[index] != null && arr[index] != key）,使用 hash 冲突解决方法求下一个地址，直到（arr[index] == null || arr[index] == key）。
5.2. 哈希表的查找效率
决定 hash 表查找的 ASL 因素：
- 选用的 hash 函数
- 选用的处理冲突的方法
- hash 表的饱和度， 装载因子 α = n/m （n 表示实际装载数据长度， m 为表长）