最近关于hash的攻击很火，这个问题存在的时间很久了。有几点想法，写出来和大家分享一下。

    hash的好处是查找速度快，但是通过特殊的输入，会造成冲突链过长，查找会退化成一个链表遍历操作。对于hash来说，有几个重要的参数

    1)hash table size，也就是hash的映射空间，很显然，hash表越大，映射的冲突几率就越小。

    2)hash function，冲突取决于几个因素，一是输入源，二是hash function。好的hash function可以把非随机的输入源映射成随机的，比如MD5或者SHA这样的哈希函数，不同的输入，映射值肯定是不同的。但是MD5或者SHA的映射空间太大了，没法用做查找，而且映射速度也比较慢。所以一般用于校验而非查找。

    3)冲突解决方法。链表法，相同哈希值的项，组成一个链表；开放地址法，有冲突，用另一个函数重新映射，这个方法对于冲突很多的情况是没办法解决的，只能覆盖或者丢弃冲突项。

    对于完全随机的输入源，简单的哈希函数就可以保证映射也是随机的。好的哈希函数应该把输入的每个bit都考虑进来，并增加一个随机因子(系统初始化是设定，这样对相同的输入，每次系统重启后，映射值不同，对不同的系统，映射值也不同)。由于哈希表项是一个资源，每一个输入会占用一个资源，哈希表项并不是无限的，所以只要有足够多的无效输入就能耗尽哈希表项。所以这里的问题并不在于特殊构造的输入，而是如何能够识别哪些输入是无效的输入；再就是哈希表项的超时时间可以短一点。当冲突链退化到一定程度，应该启动攻击检测机制，限制来自同一源的输入。所以问题的核心是如何检测攻击，基于统计的方法应该是适用的。

    在资源有限的情况下，对攻击源的识别就是重点，这也是DDoS检测和预防的重点。

    http://en.wikipedia.org/wiki/Hash_table

建议继续学习：

1. HashMap解决hash冲突的方法    (阅读：11037)
2. 关于memcache分布式一致性hash    (阅读：10635)
3. MinHash原理与应用    (阅读：5698)
4. LVS hash size解决4096个并发的问题    (阅读：5363)
5. 无锁HashMap的原理与实现    (阅读：5096)
6. 如果用户在5分钟内重复上线，就给他发警告，问如何设计？    (阅读：4815)
7. Ubuntu 下Hash校验和不符问题的解决    (阅读：4290)
8. 分布式系统hash策略    (阅读：3676)
9. redis源代码分析 - hash table    (阅读：3434)
10. 一致性hash算法    (阅读：3365)