散列表(哈希表)概览
# 散列表(哈希表)概览
参考地址：https://www.cnblogs.com/longbensong/p/14702970.html (opens new window)
散列表英文叫 Hash table，也叫哈希表，是根据关键码值(Key value)而直接进行访问的数据结构。
也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找速度。这个映射函数叫做散列函数，存放记录的数组叫散列表
# Hash 冲突及解决方法
哈希冲突：若两个不相等的 key 产生了相等的 哈希值 ，这时则需要采用 哈希冲突 。
解决 hash 冲突的办法分为两大类：
开散列法：拉链法，再哈希法，
闭散列法：开放定址法
开散列法把发生冲突的关键码存储在散列表主表之外，而闭散列法把发生冲突的关键码存储在表中另一个槽内。
# 1. 拉链法
Java 标准库的 HashMap 基本上就是用 拉链法 实现的。 拉链法 的实现比较简单，将链表和数组相结合。也就是说创建一个链表数组，数组中每一格就是一个链表。若遇到哈希冲突，则将冲突的值加到链表中即可。
优点：
① 对于记录总数频繁可变的情况，处理的比较好（也就是避免了动态调整的开销）
② 由于记录存储在结点中，而结点是动态分配，不会造成内存的浪费，所以尤其适合那种记录本身尺寸（size）很大的情况，因为此时指针的开销可以忽略不计了
③ 删除记录时，比较方便，直接通过指针操作即可
缺点：
① 存储的记录是随机分布在内存中的，这样在查询记录时，相比结构紧凑的数据类型（比如数组），哈希表的跳转访问会带来额外的时间开销
② 如果所有的 key-value 对是可以提前预知，并之后不会发生变化时（即不允许插入和删除），可以人为创建一个不会产生冲突的完美哈希函数（perfect hash function），此时封闭散列的性能将远高于开放散列
③ 由于使用指针，记录不容易进行序列化（serialize）操作
# 2.再哈希法
就是同时构造多个不同的哈希函数：Hi = RHi(key) i= 1,2,3 ... k;
其中 RHi 为不同的哈希函数。当 H1 = RH1(key) 发生冲突时，再用 H2 = RH2(key) 进行计算，直到冲突不再产生，这种方法不易产生聚集，但是增加了计算时间。
# 3. 开放定址法
开放寻址法又叫做开放定址法、开地址法，从发生冲突的那个单元起，按照一定的次序，从哈希表中找到一个空闲的单元。然后把发生冲突的元素存入到该单元的一种方法。开放定址法需要的表长度要大于等于所需要存放的元素。
在开放定址法中根据探查序列生成方式的不同，细分有：线性探查法、平方探查法、双散列函数探查法、伪随机探查法等。
开放定址法的缺点在于删除元素的时候不能真的删除，否则会引起查找错误，只能做一个特殊标记。只到有下个元素插入才能真正删除该元素。
优点：
① 记录更容易进行序列化（serialize）操作
② 如果记录总数可以预知，可以创建完美哈希函数，此时处理数据的效率是非常高的
缺点：
① 存储记录的数目不能超过桶数组的长度，如果超过就需要扩容，而扩容会导致某次操作的时间成本飙升，这在实时或者交互式应用中可能会是一个严重的缺陷
② 使用探测序列，有可能其计算的时间成本过高，导致哈希表的处理性能降低
③ 由于记录是存放在桶数组中的，而桶数组必然存在空槽，所以当记录本身尺寸（size）很大并且记录总数规模很大时，空槽占用的空间会导致明显的内存浪费
④ 删除记录时，比较麻烦。比如需要删除记录 a，记录 b 是在 a 之后插入桶数组的，但是和记录 a 有冲突，是通过探测序列再次跳转找到的地址，所以如果直接删除 a，a 的位置变为空槽，而空槽是查询记录失败的终止条件，这样会导致记录 b 在 a 的位置重新插入数据前不可见，所以不能直接删除 a，而是设置删除标记。这就需要额外的空间和操作。
- 线性探查法：
线行探查法是开放定址法中最简单的冲突处理方法，它从发生冲突的单元起，依次判断下一个单元是否为空，当达到最后一个单元时，再从表首依次判断。直到碰到空闲的单元或者探查完全部单元为止。
- 平方探查法
平方探查法即是发生冲突时，用发生冲突的单元 d[i], 加上 1²、 2² 等。即 d[i] + 1²，d[i] + 2², d[i] + 3²… 直到找到空闲单元。
在实际操作中，平方探查法不能探查到全部剩余的单元。不过在实际应用中，能探查到一半单元也就可以了。若探查到一半单元仍找不到一个空闲单元，表明此散列表太满，应该重新建立。
- 双散列函数探查法
双散列函数探查法又叫做双重散列探查法（出自算法导论），是开发寻址法中的最好方法之一，因为它所产生的探查序列具有随机性。
关于叫法推荐叫双散列函数探查法，因为双重散列探查法的名字有歧义，是使用两个散列函数还是使用一个散列函数做两次散列计算呢，没有那么直白。
这种方法使用两个散列函数 h1 和 h2。其中 h1 和前面的 h 一样，以关键字为自变量，产生一个 0 至 m-1 之间的数作为散列地址；h2 也以关键字为自变量，产生一个 1 至 m-1 之间的并和 m 互素的数（即 m 不能被该数整除）作为探查序列的地址增量（即步长）。这样做是使探查序列能够分布在整个 Hash 表。
- 伪随机探查法
具体实现时，建立一个伪随机数发生器来生成探查序列。
例如，假设哈希表长度 m=11，哈希函数为：H(key)= key % 11，则 H(47)=3，H(26)=4，H(60)=5，假设下一个关键字为 69，则 H(69)=3，与 47 冲突。如果用伪随机探测再散列处理冲突，且伪随机数序列为：2，5，9，…，则下一个哈希地址为 H1=(3+2)%11=5，仍然冲突，再找下一个哈希地址为 H2=(3+5)%11=8，此时不再冲突，将 69 填入 8 号单元。
- 小结
四种不同的开放寻址法，根据其探查序列可以看出，线性探查法的步长值固定为 1；平方探查法步长值是探查次数 i 的两倍减 1；双散列函数探查法，其探查序列的步长值是同一关键字的另一散列函数的值。对于伪随机探查法，探查序列是随机的，所以步长也是随机的。
# 4. 建立一个公共溢出区
将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。