1. 导语
背过java面经或者研读过jdk源码的同学都会知道：相对于jdk7中的hash表，java8以后的hash表中相同键值元素超过8个时，会自动将hash表的底层实现链表转成平衡树，而jdk7得hash表底层则只使用链表进行实现，那么，为什么jdk会突然修改hash表的底层实现呢？究其原因在于，2011年时，产生了一种专门针对于hash表结构的攻击方案——哈希洪水攻击。本文将对于哈希洪水攻击（Hash-Flooding Attack）进行讲解，并说明jdk中hash表底层使用混合数据结构实现所带来的好处。
2. 什么是哈希洪水攻击？
哈希洪水攻击（Hash-Flooding Attack） 是一种 拒绝服务攻击（Denial of Service） ，一旦后端接口存在合适的攻击面，攻击者就能通过哈希洪水攻击轻松让整台服务器陷入瘫痪。
3. 哈希洪水攻击的基本原理
那么哈希洪水攻击的基本原理是什么呢？这个需要从数据结构谈起
在各种常用的数据结构里，有些数据结构的“平均运行时间”和“最差运行时间”会差很远，比如哈希表（Hash Table）。假设我们想要连续插入NNN个元素到哈希表中：
- 如果这些元素的键（Key）极少出现相同哈希值，这项任务就只需O(N)O(N)O(N)的时间。
- 如果这些键频繁出现相同的哈希值（频繁发生碰撞），这项任务就需要 O(N2)O(N^2)O(N2)的时间。
2003年，Scott A. Crosby 和 Dan S. Wallach 两位研究人员发表了一篇论文：Denial of Service via Algorithmic Complexity Attacks。在这篇论文里他们首次提出：既然有些数据结构的最差运行时间极高，那么我们完全可以利用算法上的漏洞，强行构造出一个最差情况，让服务器把全部的资源都浪费在处理这个最差情况上，从而无法为正常的用户提供服务。从而进行拒绝服务攻击。
3.1 哈希表最差时间复杂度的说明
假定有一个空的单链表哈希表，我们向其中连续插入nnn个元素。这nnn个元素的键两两均不相同，但是全部有相同的哈希值，也就是说会被插入到同一个位置上去。
每一次插入时，都需要两个步骤：首先遍历整条单链表，确认现在这个键确实不在表中。确认不存在的话，就将新的元素追加到单链表结尾。
这样一来，插入第1个元素需要0+1个常数时间操作；插入第2个元素需要1+1个常数时间操作；……；插入第n个元素时需要n-1+1个常数时间操作。最后总共需要
1+2+…+n=0.5n(n+1)=O(n2)1+2+…+n=0.5n(n+1)=O(n^2)1+2+…+n=0.5n(n+1)=O(n2)
个常数时间操作，才能把nnn个元素插入到哈希表中。
3.2 攻击方案
以老版本的 java.lang.String.hashCode()为例，该函数计算一个字符串的哈希值的方法为：
hash(s)=s[0]∗31n−1+s[1]∗31n−2+...+s[n−1]hash(s) = s[0]*31^{n-1} + s[1]*31^{n - 2} + ... + s[n - 1]hash(s)=s[0]∗31n−1+s[1]∗31n−2+...+s[n−1]
由此，可以构建出能够构建出大量具有相同哈希值的字符串，然后将其插入到哈希表中，就会导致系统必须去处理一个O(n2)O(n^2)O(n2)的算法。
4. 针对哈希洪水攻击的防御方案
4.1 带密钥哈希算法
能够构建大量具有相同哈希值的输入的前提，是攻击者能够白盒的掌握系统中所使用的哈希算法的全部细节，由此，就产生了带密钥的哈希算法，即：
每建立一张哈希表时，就产生一个随机种子，这个随机种子是私有的，每当计算哈希值时，对于要计算的值上加上这个随机种子后再进行计算，从而防止攻击方生成大量相同哈希值的输入。
4.2 JAVA的解决方案
从JDK 8开始，HashMap、LinkedHashMap和ConcurrentHashMap三个类引入了一套新的策略来处理哈希碰撞。
- 当一个位置存储的元素个数小于8个时，仍然使用链表存储。
- 当一个位置存储的元素个数大于等于8个时，改为使用平衡树来存储。
这样一来，就能保证最差的运行时间是 O(nlogn)O(nlogn)O(nlogn) 了。
