数据结构与算法之美
王争
前 Google 工程师
283752 人已学习
新⼈⾸单¥68
登录后,你可以任选4讲全文学习
课程目录
已完结/共 81 讲
基础篇 (38讲)
数据结构与算法之美
15
15
1.0x
00:00/00:00
登录|注册

19 | 散列表(中):如何打造一个工业级水平的散列表?

红黑树
链表法的优化
适用场景
缺点
优点
适用场景
缺点
优点
时间复杂度分析
数据搬移操作
扩容操作
散列冲突解决方法选择
装载因子和动态扩容
散列函数设计
散列函数
散列冲突解决方法
装载因子和动态扩容
初始大小
链表法
开放寻址法
装载因子阈值的选择
动态缩容
动态扩容
装载因子过大的处理
其他设计方法
数据分析法
分布均匀
简单高效
课后思考
内容小结
设计思路
设计工业级散列表的要求
工业级散列表举例分析
散列冲突解决方法
装载因子和动态扩容
散列函数设计
总结
散列表设计

该思维导图由 AI 生成,仅供参考

通过上一节的学习,我们知道,散列表的查询效率并不能笼统地说成是 O(1)。它跟散列函数、装载因子、散列冲突等都有关系。如果散列函数设计得不好,或者装载因子过高,都可能导致散列冲突发生的概率升高,查询效率下降。
在极端情况下,有些恶意的攻击者,还有可能通过精心构造的数据,使得所有的数据经过散列函数之后,都散列到同一个槽里。如果我们使用的是基于链表的冲突解决方法,那这个时候,散列表就会退化为链表,查询的时间复杂度就从 O(1) 急剧退化为 O(n)。
如果散列表中有 10 万个数据,退化后的散列表查询的效率就下降了 10 万倍。更直接点说,如果之前运行 100 次查询只需要 0.1 秒,那现在就需要 1 万秒。这样就有可能因为查询操作消耗大量 CPU 或者线程资源,导致系统无法响应其他请求,从而达到拒绝服务攻击(DoS)的目的。这也就是散列表碰撞攻击的基本原理。
今天,我们就来学习一下,如何设计一个可以应对各种异常情况的工业级散列表,来避免在散列冲突的情况下,散列表性能的急剧下降,并且能抵抗散列碰撞攻击?

如何设计散列函数?

散列函数设计的好坏,决定了散列表冲突的概率大小,也直接决定了散列表的性能。那什么才是好的散列函数呢?
首先,散列函数设计不能太复杂。过于复杂的散列函数,势必会消耗很多计算时间,也就间接地影响到散列表的性能。其次,散列函数生成的值要尽可能随机并且均匀分布,这样才能避免或者最小化散列冲突,而且即便出现冲突,散列到每个槽里的数据也会比较平均,不会出现某个槽内数据特别多的情况。
确认放弃笔记?
放弃后所记笔记将不保留。
新功能上线,你的历史笔记已初始化为私密笔记,是否一键批量公开?
批量公开的笔记不会为你同步至部落
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线
笔记
复制
AI
  • 深入了解
  • 翻译
    • 英语
    • 中文简体
    • 中文繁体
    • 法语
    • 德语
    • 日语
    • 韩语
    • 俄语
    • 西班牙语
    • 阿拉伯语
  • 解释
  • 总结

本文深入探讨了如何打造工业级水平的散列表,涵盖了散列函数设计、装载因子处理、冲突解决方法等关键因素。针对动态扩容耗时过多的问题,提出了分批完成扩容操作的解决方案,有效避免了一次性扩容导致的性能问题。此外,对开放寻址法和链表法两种冲突解决方法进行了详细比较,指出了它们各自的优劣和适用场景。最后,通过分析Java中的HashMap实现,展示了初始大小、装载因子、动态扩容、散列冲突解决方法等关键技术在工业级散列表中的应用。整体而言,本文内容丰富,涵盖了散列表设计的关键技术,对于想要提升散列表性能的读者具有很高的参考价值。

仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《数据结构与算法之美》
新⼈⾸单¥68
立即购买
登录 后留言

全部留言(182)

  • 最新
  • 精选
  • Jerry银银
    int hash(Object key) { int h = key.hashCode(); return (h ^ (h >>> 16)) & (capitity -1); //capicity 表示散列表的大小 } 先补充下老师使用的这段代码的一些问题:在JDK HashMap源码中,是分两步走的: 1. hash值的计算,源码如下: static final int hash(Object key) { int hash; return key == null ? 0 : (hash = key.hashCode()) ^ hash >>> 16; } 2. 在插入或查找的时候,计算Key被映射到桶的位置: int index = hash(key) & (capacity - 1) ---------------------------- JDK HashMap中hash函数的设计,确实很巧妙: 首先hashcode本身是个32位整型值,在系统中,这个值对于不同的对象必须保证唯一(JAVA规范),这也是大家常说的,重写equals必须重写hashcode的重要原因。 获取对象的hashcode以后,先进行移位运算,然后再和自己做异或运算,即:hashcode ^ (hashcode >>> 16),这一步甚是巧妙,是将高16位移到低16位,这样计算出来的整型值将“具有”高位和低位的性质 最后,用hash表当前的容量减去一,再和刚刚计算出来的整型值做位与运算。进行位与运算,很好理解,是为了计算出数组中的位置。但这里有个问题: 为什么要用容量减去一? 因为 A % B = A & (B - 1),所以,(h ^ (h >>> 16)) & (capitity -1) = (h ^ (h >>> 16)) % capitity,可以看出这里本质上是使用了「除留余数法」 综上,可以看出,hashcode的随机性,加上移位异或算法,得到一个非常随机的hash值,再通过「除留余数法」,得到index,整体的设计过程与老师所说的“散列函数”设计原则非常吻合! --------- 有分析不准确的地方,请指正!

    作者回复: 👍

    2018-11-04
    31
    764
  • 天王
    能否每节讲完都有个代码的demo?

    作者回复: 是个好建议 我考虑下

    2018-11-02
    2
    80
  • 老师能不能就具体的题,讲讲数据结构呀。这种高大上的,对我来说有点难😔

    作者回复: 我后面还打算把所有的课后题集中写一写答案 那个时候会具体分析题目对应的就解决思路

    2018-11-02
    41
  • 辰陌
    python的字典就是封装好的散列吧

    作者回复: 嗯嗯

    2018-11-05
    3
    23
  • 喜欢你的笑
    能分析一下HashMap的散列函数吗?

    作者回复: 不建议搞得这么详细 :)你就看一眼 有个印象就好了

    2018-11-02
    18
  • Infinite_gao
    老师可以分享一下,你对hashmap的默认负载因子是0.75的理解吗?是与泊松分布有关吗?

    作者回复: 大牛 能否详细说说

    2018-11-02
    5
    15
  • w1sl1y
    我怎么hashmap记得红黑树树化的阈值是8,退化的阈值是6,回头看看源码确认下

    作者回复: 确认好留言给我啊

    2018-11-03
    2
    14
  • Lee
    JDK1.8 红黑树退化成链表阈值好像是6

    作者回复: 嗯嗯 多谢指正

    2018-11-19
    2
    12
  • Allen Zou
    老师,开放寻址法如果冲突了,占用其它hash code对应的位置,那该位置真正的数据来的时候怎么办,接着往后放么?删除的时候是否要搬回来?

    作者回复: 不存在真正的数据的说法 都是先来先占坑

    2018-11-03
    3
    7
  • 小喵喵
    为什么是78978呢?是随便给的一个数字吗?

    作者回复: 是的;)

    2019-10-16
    6
收起评论
显示
设置
留言
99+
收藏
沉浸
阅读
分享
手机端
快捷键
回顶部