数据结构与算法之美
王争
前Google工程师
立即订阅
71638 人已学习
课程目录
已完结 75 讲
0/4登录后,你可以任选4讲全文学习。
开篇词 (1讲)
开篇词 | 从今天起,跨过“数据结构与算法”这道坎
免费
入门篇 (4讲)
01 | 为什么要学习数据结构和算法?
02 | 如何抓住重点,系统高效地学习数据结构与算法?
03 | 复杂度分析(上):如何分析、统计算法的执行效率和资源消耗?
04 | 复杂度分析(下):浅析最好、最坏、平均、均摊时间复杂度
基础篇 (38讲)
05 | 数组:为什么很多编程语言中数组都从0开始编号?
06 | 链表(上):如何实现LRU缓存淘汰算法?
07 | 链表(下):如何轻松写出正确的链表代码?
08 | 栈:如何实现浏览器的前进和后退功能?
09 | 队列:队列在线程池等有限资源池中的应用
10 | 递归:如何用三行代码找到“最终推荐人”?
11 | 排序(上):为什么插入排序比冒泡排序更受欢迎?
12 | 排序(下):如何用快排思想在O(n)内查找第K大元素?
13 | 线性排序:如何根据年龄给100万用户数据排序?
14 | 排序优化:如何实现一个通用的、高性能的排序函数?
15 | 二分查找(上):如何用最省内存的方式实现快速查找功能?
16 | 二分查找(下):如何快速定位IP对应的省份地址?
17 | 跳表:为什么Redis一定要用跳表来实现有序集合?
18 | 散列表(上):Word文档中的单词拼写检查功能是如何实现的?
19 | 散列表(中):如何打造一个工业级水平的散列表?
20 | 散列表(下):为什么散列表和链表经常会一起使用?
21 | 哈希算法(上):如何防止数据库中的用户信息被脱库?
22 | 哈希算法(下):哈希算法在分布式系统中有哪些应用?
23 | 二叉树基础(上):什么样的二叉树适合用数组来存储?
24 | 二叉树基础(下):有了如此高效的散列表,为什么还需要二叉树?
25 | 红黑树(上):为什么工程中都用红黑树这种二叉树?
26 | 红黑树(下):掌握这些技巧,你也可以实现一个红黑树
27 | 递归树:如何借助树来求解递归算法的时间复杂度?
28 | 堆和堆排序:为什么说堆排序没有快速排序快?
29 | 堆的应用:如何快速获取到Top 10最热门的搜索关键词?
30 | 图的表示:如何存储微博、微信等社交网络中的好友关系?
31 | 深度和广度优先搜索:如何找出社交网络中的三度好友关系?
32 | 字符串匹配基础(上):如何借助哈希算法实现高效字符串匹配?
33 | 字符串匹配基础(中):如何实现文本编辑器中的查找功能?
34 | 字符串匹配基础(下):如何借助BM算法轻松理解KMP算法?
35 | Trie树:如何实现搜索引擎的搜索关键词提示功能?
36 | AC自动机:如何用多模式串匹配实现敏感词过滤功能?
37 | 贪心算法:如何用贪心算法实现Huffman压缩编码?
38 | 分治算法:谈一谈大规模计算框架MapReduce中的分治思想
39 | 回溯算法:从电影《蝴蝶效应》中学习回溯算法的核心思想
40 | 初识动态规划:如何巧妙解决“双十一”购物时的凑单问题?
41 | 动态规划理论:一篇文章带你彻底搞懂最优子结构、无后效性和重复子问题
42 | 动态规划实战:如何实现搜索引擎中的拼写纠错功能?
高级篇 (9讲)
43 | 拓扑排序:如何确定代码源文件的编译依赖关系?
44 | 最短路径:地图软件是如何计算出最优出行路径的?
45 | 位图:如何实现网页爬虫中的URL去重功能?
46 | 概率统计:如何利用朴素贝叶斯算法过滤垃圾短信?
47 | 向量空间:如何实现一个简单的音乐推荐系统?
48 | B+树:MySQL数据库索引是如何实现的?
49 | 搜索:如何用A*搜索算法实现游戏中的寻路功能?
50 | 索引:如何在海量数据中快速查找某个数据?
51 | 并行算法:如何利用并行处理提高算法的执行效率?
实战篇 (5讲)
52 | 算法实战(一):剖析Redis常用数据类型对应的数据结构
53 | 算法实战(二):剖析搜索引擎背后的经典数据结构和算法
54 | 算法实战(三):剖析高性能队列Disruptor背后的数据结构和算法
55 | 算法实战(四):剖析微服务接口鉴权限流背后的数据结构和算法
56 | 算法实战(五):如何用学过的数据结构和算法实现一个短网址系统?
加餐:不定期福利 (6讲)
不定期福利第一期 | 数据结构与算法学习书单
不定期福利第二期 | 王争:羁绊前行的,不是肆虐的狂风,而是内心的迷茫
不定期福利第三期 | 测一测你的算法阶段学习成果
不定期福利第四期 | 刘超:我是怎么学习《数据结构与算法之美》的?
总结课 | 在实际开发中,如何权衡选择使用哪种数据结构和算法?
《数据结构与算法之美》学习指导手册
加餐:春节7天练 (7讲)
春节7天练 | Day 1:数组和链表
春节7天练 | Day 2:栈、队列和递归
春节7天练 | Day 3:排序和二分查找
春节7天练 | Day 4:散列表和字符串
春节7天练 | Day 5:二叉树和堆
春节7天练 | Day 6:图
春节7天练 | Day 7:贪心、分治、回溯和动态规划
加餐:用户学习故事 (2讲)
用户故事 | Jerry银银:这一年我的脑海里只有算法
用户故事 | zixuan:站在思维的高处,才有足够的视野和能力欣赏“美”
结束语 (3讲)
结束语 | 送君千里,终须一别
第2季回归 | 这一次,我们一起拿下设计模式!
打卡召集令 | 60 天攻克数据结构与算法
免费
数据结构与算法之美
登录|注册

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

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

如何设计散列函数?

散列函数设计的好坏,决定了散列表冲突的概率大小,也直接决定了散列表的性能。那什么才是好的散列函数呢?
首先,散列函数设计不能太复杂。过于复杂的散列函数,势必会消耗很多计算时间,也就间接的影响到散列表的性能。其次,散列函数生成的值要尽可能随机并且均匀分布,这样才能避免或者最小化散列冲突,而且即便出现冲突,散列到每个槽里的数据也会比较平均,不会出现某个槽内数据特别多的情况。
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《数据结构与算法之美》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(125)

  • 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
    9
    327
  • Flash
    经过一番资料查阅理解之后,说说我的理解:
    JDK hashMap源码,hash表中数组位置的计算分两步:
    1.计算hash值:
     hash(Object key) {
            int h;
            return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
    这一步有一种说法,叫它扰动函数,为什么要右移16位再与本身异或呢?
    1.1 首先hashCode()返回值int最高是32位,如果直接拿hashCode()返回值作为下标,大概40亿的映射空间,只要哈希函数映射得比较均匀松散,一般是很难出现碰撞的。
    问题是一个40亿长度的数组,内存是放不下的。
    1.2 所以,用自己的高半区和低半区做异或,混合原始哈希码的高位和低位,关键是以此来加大低位的随机性。为后续计算index截取低位,保证低位的随机性。
    1.3 这样设计保证了对象的hashCode的32位值只要有一位发生改变,整个hash()返回值就会改变,高位的变化会反应到低位里,保证了hash值的随机性。

    2.在插入或查找的时候,计算Key被映射到桶的位置:
    int index = hash(key) & (capacity - 1)
    hash()扰动函数计算的值和hash表当前的容量减一,做按位与运算。
    这一步,为什么要减一,又为什么要按位与运算?
    因为A % B = A & (B - 1),当B是2的指数时,等式成立。
    本质上是使用了「除留余数法」,保证了index的位置分布均匀。

    为什么HashMap的数组长度必须是2的整次幂?
    数组长度是2的整次幂时,(数组长度-1)正好相当于一个**“低位掩码”**,“与”操作的结果就是散列值的高位全部归零,只保留低位值,用来做数组下标访问。

    以初始长度16为例,16-1=15。2进制表示是00000000 00000000 00001111。“与”操作的结果就是截取了最低的四位值。也就相当于取模操作。
    2019-01-07
    4
    87
  • SCu
    可能会有同学对那个mod (capacity-1)有疑问 这个很正常,因为缺少前置描述条件 即当且仅当 capacity是2的整数倍的时候该公式才成立 当capacity为2的整数倍时(无符号)仅有一位是1其余位为0 减1后 后续为为1当前位为0 做与运算等于取后面的所有位的值 比如capacity=8 即00001000 减1为00000111 如has code=5 即00000101 此时5%8=00000101&00000111=00000101=5 其他大家举一反三即可
    2018-11-16
    2
    63
  • 天王
    能否每节讲完都有个代码的demo?

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

    2018-11-02
    51
  • 拉欧
    比如Redis中的hash,set,hset,都是散列表实现,他们的动态扩容策略是同时维护两个散列表,然后一点点搬移数据
    2018-11-02
    1
    50
  • 姜威
    总结:散列表(中)
    面试题目:如何设计一个工业级的散列函数?
    思路:
    何为一个工业级的散列表?工业级的散列表应该具有哪些特性?结合学过的知识,我觉的应该有这样的要求:
    1.支持快速的查询、插入、删除操作;
    2.内存占用合理,不能浪费过多空间;
    3.性能稳定,在极端情况下,散列表的性能也不会退化到无法接受的情况。
    方案:
    如何设计这样一个散列表呢?根据前面讲到的知识,我会从3个方面来考虑设计思路:
    1.设计一个合适的散列函数;
    2.定义装载因子阈值,并且设计动态扩容策略;
    3.选择合适的散列冲突解决方法。
    知识总结:
    一、如何设计散列函数?
    1.要尽可能让散列后的值随机且均匀分布,这样会尽可能减少散列冲突,即便冲突之后,分配到每个槽内的数据也比较均匀。
    2.除此之外,散列函数的设计也不能太复杂,太复杂就会太耗时间,也会影响到散列表的性能。
    3.常见的散列函数设计方法:直接寻址法、平方取中法、折叠法、随机数法等。
    二、如何根据装载因子动态扩容?
    1.如何设置装载因子阈值?
    ①可以通过设置装载因子的阈值来控制是扩容还是缩容,支持动态扩容的散列表,插入数据的时间复杂度使用摊还分析法。
    ②装载因子的阈值设置需要权衡时间复杂度和空间复杂度。如何权衡?如果内存空间不紧张,对执行效率要求很高,可以降低装载因子的阈值;相反,如果内存空间紧张,对执行效率要求又不高,可以增加装载因子的阈值。
    2.如何避免低效扩容?分批扩容
    ①分批扩容的插入操作:当有新数据要插入时,我们将数据插入新的散列表,并且从老的散列表中拿出一个数据放入新散列表。每次插入都重复上面的过程。这样插入操作就变得很快了。
    ②分批扩容的查询操作:先查新散列表,再查老散列表。
    ③通过分批扩容的方式,任何情况下,插入一个数据的时间复杂度都是O(1)。
    三、如何选择散列冲突解决方法?
    ①常见的2中方法:开放寻址法和链表法。
    ②大部分情况下,链表法更加普适。而且,我们还可以通过将链表法中的链表改造成其他动态查找数据结构,比如红黑树、跳表,来避免散列表时间复杂度退化成O(n),抵御散列冲突攻击。
    ③但是,对于小规模数据、装载因子不高的散列表,比较适合用开放寻址法。
    2018-11-03
    21
  • 老师能不能就具体的题,讲讲数据结构呀。这种高大上的,对我来说有点难😔

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

    2018-11-02
    18
  • w1sl1y
    看了下,的确是TREEFY_THRESHOLD等于8
    UNTREEFY_THRESHOLD等于6
    2018-11-05
    16
  • kakasi
    对于回答点赞第一的 @Jerry银银 有疑问:首先hashcode本身是个32位整型值,在系统中,这个值对于不同的对象必须保证唯一(JAVA规范),这也是大家常说的,重写equals必须重写hashcode的重要原因。
    hashcode不一定是唯一的,重写equals必须重写hashcode的原因是:java中有很多集合类是基于散列工作的,如果不重写hashcode, 两只值相等的对象就无法相等,因为object的hashcode是32位内存地址。
    2018-11-16
    14
  • Infinite_gao
    老师可以分享一下,你对hashmap的默认负载因子是0.75的理解吗?是与泊松分布有关吗?

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

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

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

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

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

    2018-11-02
    9
  • angel😇txy🤓
    我来谈谈为何hashmap每次扩容试都要扩两倍,resize()时为何每次要扩两倍?
    计算桶位置,i = (n - 1) & hash,n 为2的幂时,(n-1) & hash = hash % n, 相当于对length求模,位运算效率更高。
    rehash时需要重新计算桶位置,如果不是2的幂,n -1转为二进制后,最低位始终是0,导致最低位为0的桶被浪费,造成更多的hash碰撞。
    如果length不为2的幂,比如15。那么length-1的2进制就会变成1110。在h为随机数的情况下,和1110做&操作。尾数永远为0。那么0001、1001、1101等尾数为1的位置就永远不可能被entry占用。这样会造成浪费,不随机等问题。 length-1 二进制中为1的位数越多,那么分布就平均。
    所以HashMap的初始容量是2的n次幂,扩容也是2倍的形式,元素均匀分布在HashMap中的数组上,减少hash碰撞,避免形成链表的结构,使得查询效率降低!
    2019-08-29
    7
  • 强哥
    X % 2^n = X & (2^n - 1)
    2^n表示2的n次方,也就是说,一个数对2^n取模 == 一个数和(2^n - 1)做按位与运算 。
    所以说评论第一个说A%B=A&(B-1),并不成立。
    2019-03-07
    7
  • 猫头鹰爱拿铁
    集合类的带hash的,例如hashmap、hashset、hashtable等。hashmap中散列函数是key的hashcode与key的hashcode右移16位异或,这是为了把key的高位考虑进去,如果key是0,hash值为0。在put的时候,如果表没有初始化,需要初始化下,在计算key的位置的时候很巧妙,使用表的length-1和key的hash值与计算的,实际上就是对key的hash值对表长取模,基于hashmap是2的幂次方特性,这种位运算速度更快。如果put后hashmap的数据容量超过了表的容量*负载因子,就会自动扩容,默认是两倍,自动扩容方法是将key的hash与表长直接与判断是否有高位,有高位就把这个node放到新表里旧表对应位置加旧表长的地方。没有高位就直接是新表旧位置。这是hashmap1.8的处理方法。hashmap1.7还是对key的hash取模。如果是个非常大的数,赋值为integer.max。hashmap采用的是链地址法结合红黑树解决hash冲突,当桶中链表长度大于8就会将桶中数据结构转化为红黑树。hashtable默认的初使容量11,负载因子也是0.75,如果要指定初始化hashtable容量最好是给一个素数。这是因为放入table的时候需要对表长取模,尽量分散地映射。hashtable通过链地址法解决hash冲突,当数据容量大于数据容量*负载因子自动扩容,扩容原表长两倍+1。
    2018-11-02
    7
  • Yishem
    关于HashMap的loadFactor为什么是0.75?已经有网友整理好了(https://www.jianshu.com/p/64f6de3ffcc1),可以看看,很详细
    2018-12-14
    6
  • 辰陌
    python的字典就是封装好的散列吧

    作者回复: 嗯嗯

    2018-11-05
    6
  • Ruhm
    NOTE 这节课给我的启发太大了,以前去阅读go的源码,总是感觉异常吃力,看完这节课之后去读了go关于map这个内置类型的源码,发现思路一下就清晰起来了,阅读效率高了很多,做到了有的放矢。那么以后阅读代码之前,先了解相关知识的方法论是很有必要的,这样比拿到源码就开始读,实际从长远看是节省了时间的。
    2018-12-29
    5
  • Allen Zou
    老师,开放寻址法如果冲突了,占用其它hash code对应的位置,那该位置真正的数据来的时候怎么办,接着往后放么?删除的时候是否要搬回来?

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

    2018-11-03
    2
    5
  • Zhangwh
    链表和哈希表结合成lru 缓存,老师能讲讲不,记得老师在链表那块说过

    作者回复: 下一节课就要讲了

    2018-11-02
    5
收起评论
99+
返回
顶部