数据结构与算法之美——散列表——实战篇(上)分析

阿里 阅读:202 2021-06-15 11:20:49 评论:0

一、前言

       通过理论篇,我们知道,散列表的查询效率散列函数、装载因子、散列冲突等都有关系。如果散列函数设计得不好,或者装载因此过高,都可能导致散列冲突发生的概率升高,查询效率下降。

       在极端情况下,有些恶意的攻击者,还有可能通过精心构造的数据,使得所有的数据经过散列函数之后,都散列到同一个槽里。如果我们使用的是基于链表的冲突解决方法,那这个时候,散列表就会退化为链表,查询的时间复杂度从O(1)退化为O(n)。

       如果散列表中有10万个数据,退化后的散列表查询的效率就下降了10万倍。如何之前运行100次查询只需要0.1秒,那现在就需要1万秒。这样就有可能因为查询操作消耗大量CPU或者线程资源,导致系统无法响应其他请求,从而达到拒绝服务攻击(Dos)的目的。

       如何设计一个可以应对各种异常情况的工业级散列表,来避免在散列冲突的情况下,散列表性能的急剧下降,并且能抵抗散列碰撞攻击

二、如何设计散列函数

       散列函数设计的好坏,决定了散列表冲突的概率大小,也直接决定了散列表的性能,那什么才是好的散列函数呢?

       1、散列函数的设计不能太复杂

       2、散列函数生成的值要尽可能随机并且均匀分布

三、装载因子过大怎么办

       提及散列表的装载因子的时候说过,装载因子越大,说明散列表中的元素越多,空闲位置越少,散列冲突的概率就越大。不仅插入数据的过程要多次寻址或者拉很长的链,查找的过程也会因此变得很慢。

       对于动态散列表来说,数据集合是频繁变动的,我们事先无法预估要加入的数据个数,所以我们也无法事先申请一个足够大的散列表。随着数据慢慢加入,装载因子就会慢慢变大。当装载因子达到一定程度之后,散列冲突就会变得不可接受。这个时候,应该如何处理呢?

       还记得我们前面多次讲的“动态扩容”吗?回想一下,我们是如何做数组、栈、队列的动态扩容的。

       针对散列表,当装载因子过大时,我们可以进行动态扩容,重新申请一个更大的散列表,将数据搬移到这个新散列表中。因为散列表的大小变量,数据的存储位置也变了,所以我们需要通过散列函数重新计算每个数据的存储位置。

       装载因子阈值需要选择得当,如果太大,会导致冲突过大;如果太小,会导致内存严重浪费。装载因子阈值的设置要权衡时间、空间复杂度

四、如何选择冲突解决方法

       理论篇讲了两种主要的散列冲突的解决办法,开发寻址法和链表法。这两种冲突解决办法在实际的软件开发中都非常常用。比如,Java中LInkedHashMap就采用了链表法ThreadLocalMap是通过线性探测的开放寻址法来解决的。

       1、开发寻址法

        当数据量比较小、装载因子小的时候,适合采用开发寻址法。这也是Java中ThreadLocalMap使用开放寻址法解决冲突的原因。

       2、链表法

       基于链表的散列冲突处理方法比较适合存储大对象、大数据量的散列表,而且,比起开放寻址法,它更加灵活,支持更多的优化策略,比如用红黑树代替链表

五、什么是一个工业级的散列表?工业级散列表应该具有哪些特性

        (1)几点要求:

        1、支持快速的查询、插入、删除操作;

        2、内存占用合理,不能浪费过多的内存空间;

        3、性能稳定,极端情况下,散列表的性能也不会退化到无法接受的情况

        (2)如何实现这样一个散列表

        1、设计一个合适的散列函数

        2、定义装载因子阈值,并且设计动态扩容策略;

        3、选择合适的散列冲突解决方法


标签:程序员
声明

1.本站遵循行业规范,任何转载的稿件都会明确标注作者和来源;2.本站的原创文章,请转载时务必注明文章作者和来源,不尊重原创的行为我们将追究责任;3.作者投稿可能会经我们编辑修改或补充。

发表评论
搜索
KIKK导航

KIKK导航

排行榜
关注我们

一个IT知识分享的公众号