一个故事讲完哈希洪荒攻击

版权声明：本文为苦逼的码农原创。未经同意禁止任何形式转载，特别是那些复制粘贴到别的平台的，否则，必定追究。欢迎大家多多转发，谢谢。

来源公众号：苦逼的码农

作者：帅地

生意红火

有一天你和你的邻居同时开了一个快递驿站，不过你的运气很好，每天都有很多快递到你这里来，生意红红火火，然而，你的邻居生意很冷清。

快递一多，为了取件人方便找到快递，于是你按照快递手机号码的最后两位数字来给快递分类，例如尾号为 01 的放到柜子 1 中，尾号为 02 的放到柜子 2 。如果有人来取快递，他只需要报出他的手机号码，就可以快速找到对应的柜子，然后再根据完整的手机号码在这个柜子里找到对应的快件了。

心声恶意的邻居

日子一天天过去，你的店铺越来越火，然而，你邻居的生意冷清到哭晕在厕所里，但是你并没有去在意你的邻居，也没有分担点生意给他，于是，你的邻居心生坏意，决定搞搞你。

他知道你是采用按照快件手机号码末尾两位来分类的，于是他分批买了大量非常廉价的物品，并且把大部分快递的手机号码的末尾的两位弄成是一样的。

于是，你收到了大量的快递，并且大量的快递都被分到了同一个柜子里，导致有些柜子里堆放了大量的快件，挤满到不得不把一些放地下了，然而有些柜子里却是空荡荡的。

这也不仅导致了资源分配不均匀，每次顾客来取快件的时候，还得找好久才能找到。

于是你老爸和你说：要不加大柜子的容量吧。

你：加大容量没用，虽然能短暂不会出现挤满放地下的情况，但本质问题并没有解决。

更换策略

为了解决这个问题，于是你采取了別的策略，把手机号码当做一个数值，然后对这个数值进行取余，例如  手机号 % 99 = 柜子的编号。

每次客人来的时候，你把他的手机号码也进行取余，然后告诉他，去对应的柜子取，取余这个操作虽然麻烦了点，工作量比之前大了，但，躲开了你邻居的攻击，也算值得。

问题的本质

然而好景不长，你的邻居通过观察与测试，发现你是通过手机号码取余来映射到对应的柜子上的，于是，它又找了一堆手机号码取余后值相同的手机号码来搞定，于是，你又奔溃了。

你知道你侄子是学计算机专业的，于是你把这件事告诉了你的侄子，你的侄子一听到这个，就来了劲，于是管不住嘴吹了下面这一大堆：

告诉你，你的这种映射策略相当于我平时学的哈希算法,不管你如何改变你的算法策略，只要被别人知道了你的哈希算法，那么，都会容易遭受到别人的攻击，像你的邻居的那种攻击方式，就叫做哈希洪荒攻击。

我们都知道，在各种数据结构里，有平均时间复杂度和最差时间复杂度之分，对于哈希算法，我们插入 n 个到元素到数组里的话，平均时间复杂度是 O(n)，而最差的时间复杂度是 O(n^2)；查找某个元素的平均复杂度是 O(1)，最差时间复杂度是 O(n)，而哈希洪荒攻击就是攻击者有意给出一些特殊值，使得我们每次都遇到了最差时间复杂度。

如何防御？

刚才说了，哈希洪荒攻击的本质就是攻击者掌握了你的哈希算法，所以如何想要防御的话，就需要我们设计出优秀的哈希算法了，什么才算优秀的哈希算法？

1、映射出来的哈希码分布均匀。

2、不容易被破解。

当然，不管你如何设计，一旦攻击者掌握了你的算法细节，那么你都得凉。

那有没有比较好的防御措施呢？

其实，我们可以通过生成一些随机值来加强我们的哈希算法，例如，我们每次建立一张哈希表的时候，我们就随机生成一个新的随机值，来作为哈希算法的一部分。这样一来，即使是同样的内容，放在不同的表里也会产生完全不同的哈希码。

这样一来，攻击者就很难进行预测了，即使发生了碰撞，也是小概率的巧合，而不是攻击者在主动控制，我们也把这个随机的值称之为哈希种子（Hash Seed）。而这类使用哈希种子的哈希算法，我们称之为带密钥哈希算法（Keyed Hash Function）。

当然，上面这种方式只是防御哈希洪荒攻击的一种方式，对于哈希碰撞，在面试中问的最多的应该就是 Java 中的哈希表了，我跟大家补充讲讲 Java8 中是如何解决哈希碰撞的吧。

Java 中的哈希表如果出现了哈希冲突，就会用一个链表来存放哈希码相同的元素，但是如果出现大量哈希码相同的话，那么大量的元素都放在了同一条链表里，这样会导致哈希表的查找时间复杂度是 O(n)，为了解决这个问题，当链表中的元素大于等于 8 的时候，就把用红黑树来取代链表，这样一来，可以把最差时间复杂度控制在 O(logn)。

尾声

你侄子吹了一大堆专业名词，对于只读过小学的你，想不懵逼都难，这个时候你憋不住了，抛了一句给你侄子：能不能讲点人话？你只需要告诉我，我该怎么做就行了。

你侄子：我来去给你设计一个程序吧，你到时候只需要把你的手机号码进去就可以了，它会把你自动映射出对应的柜子。

最后，邻居把店铺拆了，开了一家网吧…..

你可能会喜欢