开篇

先前看到 HashMap 到一些东西，其中 JDK7 和 JDK8 的 hash 方式不同让我很是好奇，虽然已经知道这两个版本间实现的区别是 JDK8 中将链地址法做了优化，将链表改成类红黑树，将查询的复杂度从 O(n) 优化到了 O(logn)。

其实 hash 表这种东西在大学的 数据结构 课程上就已经学过，只是时隔太久，只知道有这样一种很棒的数据结构，但是具体怎么实现，有哪些实现方式等都已忘却。今天总结一下算是温故知新了。

Let's Hash

Hash 即散列，设计一个散列表，其实就是设计一个散列函数，通过这个散列函数计算出来的散列地址尽量均匀，同时计算方式尽量简洁明了。

散列方法主要有两种：1. 开放地址法。2. 链地址法。（3.直接定址法）

直接定址法

个人以为 直接定址法 是最简单粗暴的散列方式了。形如：f(key) = a * key + b就可以作为直接定址法的散列函数。直接定址法虽然简单，但是并不常用，因为这种简单粗暴的计算散列地址的前提是需要待散列值的分布情况，如果不能事先知道分布情况，遇到散列冲突就没法处理了。

开放地址法

开放地址法相较于直接定址法，无非就是多了个 求余取模再散列 的过程。

开放地址法又可分多种方式来处理 Hash 冲突的方式。这里主要介绍 线性探测法，二次探测法和双散列法。

线性探测法

线性探测法的散列函数为：f(key) = (f(key) + di) % m (1 <= di < m)

从这个函数就可以看出来，线性探测法在遇到散列冲突的时候（即像表中的一个位置插入一个数据时发现已经有一个元素在这个位置上了），那么我们要做的就是从这个位置开始往后一次移动一个位置，直到找到空位置再把要插入的元素放到空位置上。

可以说线性探测法的空间复杂度和时间复杂度都是非常高的。

二次探测法

二次探测法和线性探测法实现思想上差不多。f(key) = (f(key) + di) % m (di = 1^1,-1^1,2^2,-2^2,...k^k,-k^k)

二次探测法在遇到散列冲突的时候不再依次往后寻找空位置了，而是利用了平方运算，让散列尽可能分散开，并且是双向寻找的。

二次探测法虽然空间和时间复杂度只比线性探测法优化了那么点，但是却让散列更均匀了。

双散列法

双散列法需要提供两个散列函数：
D = f1(key)

p = f2(key) (1 <= p < m, p 与 m 互质，为了防止重复计算出原来的散列地址)

NextAddress = (D + p) % m

双散列法首先用 D 作为地址，看该位置是否为空，如果为空就放入元素，如果不为空，就用 NextAddress 作为再散列的地址。其实 p 可以看作是一个伪随机数。

总体来说，双散列法是比较优秀的。

链地址法

链接法不再像开放定址法那样在散列函数上求索，而是加入了链表结构。

链地址法处理散列冲突不再是去寻找另一个另一个空位置，而是就地解决。如何解决呢？

这就要用上我们的链表了，很难描述，如图：



在遇到散列冲突的时候我们就直接在对应位置的链表后面加一个节点来存储元素。

链地址法是比较常用的散列方法。

链表 ---》 红黑树

待添加

总结

个人感觉链表法比开放定址法优秀许多，从查询时间复杂度，添加元素，删除元素都非常好，特别是在用 表+树 形式来实现 hash 的情况，简直绝了。

参考：

https://baike.baidu.com/item/%E5%BC%80%E6%94%BE%E5%9C%B0%E5%9D%80%E6%B3%95

http://www.nowamagic.net/academy/detail/3008010