哈希表是基于数组的一种数据结构，他可以快速的插入和查找，不论哈希表中有多少数据，操作需要的时间 都接近常量的时间：O(1)的时间级。但哈希表也有一些缺点，数组创建后难以扩展。某些哈希表被基本填满 时，性能下降的非常厉害。而且，也没有一种渐变的方法可以以任何一种顺序(例如从小到大)遍历表中数据 项。如果需要这种能力，就只能选择其他数据结构。然而，如果不需要有序遍历数据，并且可以提前预测数 据量的大小，那么哈希表在速度和易用性方面是无与伦比的。

哈希化

哈希化，就是如何把关键字转换成数组下标，在哈希表中，这个转换通过哈希函数来完成。对于特定的关键 字，并不需要哈希函数，关键字的值可以直接用于数组下标。

冲突

把巨大的数字空间压缩成较小的数字空间，必然要付出代价，即不能保证哈希化后取得的下标地址是空白 单元。那有两种方法解决这个冲突问题：开放地址法 和 链地址法。

开放地址法

在开放地址法中，若数据不能直接放在由哈希函数计算出来的数组下标所指的单元时，就要寻找数组的其他 位置。有三种不同的方法：线性探测、二次探测 和 再哈希法。

线性探测

在线性探测中，线性地查找空白单元。如果5421是要插入数据的位置，它已经被占用了，那么就使用5422， 如果5422也被使用了，然后判断5423，以此类推，数组下标一直递增，直到找到空位。这就叫做线性探测。

聚集

哈希表中，一串连续的已填充单元叫做填充序列。增加越来越多的数据项时，填充序列变得越来越长。这 叫做 聚集。

当哈希表边的越来越满时，聚集变得越来越严重。这导致产生非常长的探测长度，意味着存取序列最后的 单元会非常耗时。数组填的越满，聚集越可能发生。数组由一半数据项时，这通常不是问题，当三分之二 满的时候，情况也不会太坏。然后，如果超过这个界限，随着聚集越来越严重，性能下降也很严重。因此， 设计哈希表的关键是确保它并不会超过整个数组容量的一半，最多到三分之二。

二次探测

在开放地址法的线性探测中会发生聚集，一旦聚集形成，它会变得越来越大。哪些哈希化后的落在聚集范围 内的数据项，都要一步一步移动，并插在聚集的最后，因此使聚集变得更大。聚集越大，它增长的也越快。 二次探测是防止聚集产生的一种尝试，思想是探测相隔较远的单元，而不是和原始位置相邻的单元。

步骤是步数的平方：在线性探测中，如果哈希函数计算的原始下标是x，线性探测就是 x+1，x+2，x+3， 以此类推；而在二次探测中，探测的过程是 x+1，x+4，x+9，x+16，以此类推。也就是到原始位置的距离 是步数的平方：x+1^2，x+2^2，x+3^2，x+4^2，等。

虽然二次探测解决了线性探测中产生的聚集问题，但依然会产生冲突的情况，这个现象叫做二次聚集。这 虽然不是一个严重的问题，但二次探测不会经常使用，因为还有稍微好些的解决方案。

再哈希法

二次聚集产生的原因是，二次探测的算法产生的探测序列步长总是固定的:1、4、9、16，以此类推。现在 需要一种方法产生一种依赖关键字的探测序列，而不是每个关键字都一样。那么，不同的关键字即使映射到 相同的数组下标，也可以使用不同的探测序列。方法是把关键字用不同的哈希函数再做一次哈希化，用这个 结果作为步长，对指定的关键字，步长在整个探测中是不变的，不过不同的关键字使用不同的步长。经验 说明，第二个哈希函数必须具备如下特点：

• 和第一个哈希函数不同
• 不能输出0

链地址法

链地址法中解决冲突的方式，不是寻找新的下标地址，而是将相同下标的元素组成链表，放在同一个下标 位置。装载因子通常为1，在这种情况下，大约三分之一的单元是空白单元，三分之一的单元有一个数据项， 三分之一的单元有两个或更多的数据项。

参考资料

• Java数据结构和算法 - 哈希表
• Java数据结构和算法