• 开快递店也要知道点算法知识
  • 发布于 2个月前
  • 167 热度
    0 评论
  • 张犇
  • 1 粉丝 9 篇博客
  •   
生意红火

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

快递一多,为了取件人方便找到快递,于是你按照快递手机号码的最后两位数字来给快递分类,例如尾号为 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)。

尾声

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

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

最后,邻居把店铺拆了,开了一家网吧…..
用户评论