浅析 HashTable 碰撞拒绝服务漏洞
（转载）
在去年（其实只是半个月前而已）,Tomcat就紧急发布安全漏洞通知，同时微软也发布了相应的安全漏洞通知，他们都是通过变通的方式来解决此拒绝服务漏洞。而在这风口浪的碰撞拒绝服务漏洞是什么呢？

1.什么是HashTable 碰撞?
我觉得有必要先阐述一下什么是HashTable碰撞,因为这个拒绝服务漏洞不是因为服务器的编码原因或是疏忽造成的，而是程序语言自身的问题，此问题除了perl,ruby外，几乎无一幸免，可怜的JAVA当然也在其中了.

HashTable是原意是将所有数据能足够散列的以键值对的形式存在，这样能极大的提高读取效率又能有一定的安全性，哪怕被截了包也不会轻易的让人读出数据。

在java中：

在上图中，你们可以看到 table中，只有两条记录存在 (BB=789, test123=123)，按道理来说，应该是三条，那么有一条记录(Aa=456)去了哪里了？


通过上图，大家应该恍然大悟了，那一条记录并没有消失，而是变成了链表结构追加到了key=BB 这条记录的下一个节点之上。。这样就打破了hashtable的结构，如果有N条这样的碰撞出现，那么hashTable的效率也将荡然无存了.数据就成了链表结构，而这时要获取一个在链表之上的节点的value，就会进行N次迭代进行获取，那么算法效率就从o(1)变成了o(n)……..

2.拒绝服务式攻击

接着上面阐述了hashTable的碰撞原理后，各位同学们也应该了解了这个拒绝服务式攻击了吧，其实就是因为这个hashTable的漏洞的存在，如果有人通过传递精心设计好的可以产生碰撞的超大数据，那么就会导致服务器不断的进行迭代读取，CPU一下子就会被全额占满，这是相当恐怖的。有数据说，10kb的数据量就会导致一个i7的CPU马上占用率飙升100%,本人没有试过，但也相信应该差不多..

3.如何是好？

关于tomcat 以及微软的解决之道就是很变通的告知大家，将请求参数据缓存值设小，也就是说，一次性的请求量不会导致CPU被全部占满。。。其实这也是无奈之举。

除此之外，就是设计好HASH算法，一定要保证必然碰撞事件的概率降低，也就是说提高生产位数，带来的痛苦就是请求效率降低。各有取舍吧，鱼与熊掌不可兼得.

做好异常检测，不要来者不拒，还是要理性的区分正常与恶意的数据请求.

==========================================
另外我验证以上说法的时候，碰到一个问题：

在上图中，hashtable中只有一条记录（BB=789），test的记录到哪里去了呢。请看下图：


为什么test会追加到Aa后面呢？他们的hashcode又不相同？