Java性能调优实战
刘超
金山软件西山居技术经理
立即订阅
7535 人已学习
课程目录
已完结 48 讲
0/4登录后,你可以任选4讲全文学习。
开篇词 (1讲)
开篇词 | 怎样才能做好性能调优?
免费
模块一 · 概述 (2讲)
01 | 如何制定性能调优标准?
02 | 如何制定性能调优策略?
模块二 · Java编程性能调优 (10讲)
03 | 字符串性能优化不容小觑,百M内存轻松存储几十G数据
04 | 慎重使用正则表达式
05 | ArrayList还是LinkedList?使用不当性能差千倍
加餐 | 推荐几款常用的性能测试工具
06 | Stream如何提高遍历集合效率?
07 | 深入浅出HashMap的设计与优化
08 | 网络通信优化之I/O模型:如何解决高并发下I/O瓶颈?
09 | 网络通信优化之序列化:避免使用Java序列化
10 | 网络通信优化之通信协议:如何优化RPC网络通信?
11 | 答疑课堂:深入了解NIO的优化实现原理
模块三 · 多线程性能调优 (10讲)
12 | 多线程之锁优化(上):深入了解Synchronized同步锁的优化方法
13 | 多线程之锁优化(中):深入了解Lock同步锁的优化方法
14 | 多线程之锁优化(下):使用乐观锁优化并行操作
15 | 多线程调优(上):哪些操作导致了上下文切换?
16 | 多线程调优(下):如何优化多线程上下文切换?
17 | 并发容器的使用:识别不同场景下最优容器
18 | 如何设置线程池大小?
19 | 如何用协程来优化多线程业务?
20 | 答疑课堂:模块三热点问题解答
加餐 | 什么是数据的强、弱一致性?
模块四 · JVM性能监测及调优 (6讲)
21 | 磨刀不误砍柴工:欲知JVM调优先了解JVM内存模型
22 | 深入JVM即时编译器JIT,优化Java编译
23 | 如何优化垃圾回收机制?
24 | 如何优化JVM内存分配?
25 | 内存持续上升,我该如何排查问题?
26 | 答疑课堂:模块四热点问题解答
模块五 · 设计模式调优 (6讲)
27 | 单例模式:如何创建单一对象优化系统性能?
28 | 原型模式与享元模式:提升系统性能的利器
29 | 如何使用设计模式优化并发编程?
30 | 生产者消费者模式:电商库存设计优化
31 | 装饰器模式:如何优化电商系统中复杂的商品价格策略?
32 | 答疑课堂:模块五思考题集锦
模块六 · 数据库性能调优 (8讲)
33 | MySQL调优之SQL语句:如何写出高性能SQL语句?
34 | MySQL调优之事务:高并发场景下的数据库事务调优
35 | MySQL调优之索引:索引的失效与优化
36 | 记一次线上SQL死锁事故:如何避免死锁?
37 | 什么时候需要分表分库?
38 | 电商系统表设计优化案例分析
39 | 数据库参数设置优化,失之毫厘差之千里
40 | 答疑课堂:MySQL中InnoDB的知识点串讲
模块七 · 实战演练场 (4讲)
41 | 如何设计更优的分布式锁?
42 | 电商系统的分布式事务调优
43 | 如何使用缓存优化系统性能?
44 | 记一次双十一抢购性能瓶颈调优
结束语 (1讲)
结束语 | 栉风沐雨,砥砺前行!
Java性能调优实战
登录|注册

07 | 深入浅出HashMap的设计与优化

刘超 2019-06-04
你好,我是刘超。
在上一讲中我提到过 Collection 接口,那么在 Java 容器类中,除了这个接口之外,还定义了一个很重要的 Map 接口,主要用来存储键值对数据。
HashMap 作为我们日常使用最频繁的容器之一,相信你一定不陌生了。今天我们就从 HashMap 的底层实现讲起,深度了解下它的设计与优化。

常用的数据结构

我在 05 讲分享 List 集合类的时候,讲过 ArrayList 是基于数组的数据结构实现的,LinkedList 是基于链表的数据结构实现的,而我今天要讲的 HashMap 是基于哈希表的数据结构实现的。我们不妨一起来温习下常用的数据结构,这样也有助于你更好地理解后面地内容。
数组:采用一段连续的存储单元来存储数据。对于指定下标的查找,时间复杂度为 O(1),但在数组中间以及头部插入数据时,需要复制移动后面的元素。
链表:一种在物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
链表由一系列结点(链表中每一个元素)组成,结点可以在运行时动态生成。每个结点都包含“存储数据单元的数据域”和“存储下一个结点地址的指针域”这两个部分。
由于链表不用必须按顺序存储,所以链表在插入的时候可以达到 O(1) 的复杂度,但查找一个结点或者访问特定编号的结点需要 O(n) 的时间。
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《Java性能调优实战》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(51)

  • 陆离
    2的幂次方减1后每一位都是1,让数组每一个位置都能添加到元素。
    例如十进制8,对应二进制1000,减1是0111,这样在&hash值使数组每个位置都是可以添加到元素的,如果有一个位置为0,那么无论hash值是多少那一位总是0,例如0101,&hash后第二位总是0,也就是说数组中下标为2的位置总是空的。
    如果初始化大小设置的不是2的幂次方,hashmap也会调整到比初始化值大且最近的一个2的幂作为capacity。

    作者回复: 回答正确,就是减少哈希冲突,均匀分布元素。

    2019-06-04
    39
  • AiSmart4J
    1)通过将 Key 的 hash 值与 length-1 进行 & 运算,实现了当前 Key 的定位,2 的幂次方可以减少冲突(碰撞)的次数,提高 HashMap 查询效率;
    2)如果 length 为 2 的次幂,则 length-1 转化为二进制必定是 11111…… 的形式,在于 h 的二进制与操作效率会非常的快,而且空间不浪费;如果 length 不是 2 的次幂,比如 length 为 15,则 length-1 为 14,对应的二进制为 1110,在于 h 与操作,最后一位都为 0,而 0001,0011,0101,1001,1011,0111,1101 这几个位置永远都不能存放元素了,空间浪费相当大,更糟的是这种情况中,数组可以使用的位置比数组长度小了很多,这意味着进一步增加了碰撞的几率,减慢了查询的效率!这样就会造成空间的浪费。

    作者回复: 回答非常到位

    2019-06-04
    1
    21
  • 嘉嘉☕
    加载因子那块儿,感觉有点跳跃,为什么加载因子越大,对空间利用越充分呢?

    作者回复: 加载因子是扩容的参考标准,如果加载因子越大,例如默认数组初始化大小为16,加载因子由0.75改成1.0,原来数组长度到了12就扩容,变成数组大小为16,也就是说被占满了,才会进行扩容,这也可能意味着已经发生了很多哈希冲突,这样导致某些数组中的链表长度增加,影响查询效率。

    2019-06-13
    1
    12
  • tyul
    老师,您好,请教一个问题,为什么 HashMap 的容量等于数组长度?但是扩容的时候却是根据 Map 里的所有元素总数去扩容,这样会不会导致数组中的某一个 node 有很长的链表或红黑树,数组中的其他位置都没有元素?谢谢

    作者回复: 这种数据倾斜的可能性比较小

    2019-06-05
    1
    6
  • 大虫子
    老师您好,能解答下,为什么JDK1.8之前,链表元素增加采用的是头插法,1.8之后改成尾插法了。1.8之前采用头插法是基于什么设计思路呢?

    作者回复: 你好,JDK1.7是考虑新增数据大多数是热点数据,所以考虑放在链表头位置,也就是数组中,这样可以提高查询效率,但这种方式会出现插入数据是逆序的。在JDK1.8开始hashmap链表在节点长度达到8之后会变成红黑树,这样一来在数组后节点长度不断增加时,遍历一次的次数就会少很多,相比头插法而言,尾插法操作额外的遍历消耗已经小很多了。

    也有很多人说避免多线程情况下hashmap扩容时的死循环问题,我个人觉得避免死循环的关键不在尾插法的改变,而是扩容时,用了首尾两个指针来避免死循环。这个我会在后面的多线程中讲到hashmap扩容导致死循环的问题。

    2019-06-04
    6
  • 小小征
    0 的话索引不变,1 的话索引变成原索引加上扩容前数组。 这句有点不理解 老师

    作者回复: 以下是resize中判断是否位移的部分代码,我们可以看到元素的hash值与原数组容量运算,如果运算结果为0,保持原位,如果运算结果为1,则意向扩容的高位。

    if ((e.hash & oldCap) == 0) {
                                 if (loTail == null)
                                     loHead = e;
                                 else
                                     loTail.next = e;
                                 loTail = e;
                             }
                             else {
                                 if (hiTail == null)
                                     hiHead = e;
                                 else
                                     hiTail.next = e;
                                 hiTail = e;
                             }

    假设链表中有4、8、12,他们的二进制位00000100、00001000、00001100,而原来数组容量为4,则是 00000100,以下与运算:

    00000100 & 00000100 = 0 保持原位
    00001000 & 00000100 = 1 移动到高位
    00001100 & 00000100 = 1 移动到高位

    2019-06-05
    4
    5
  • -W.LI-
    老师好。hashmap的put和get的时间复杂度算多少啊?最好O(1)。最坏复杂度是O(log(n))平均是O(1)么?。。。treeMap的,treeMap,putO(n),getO(1)?之前面试被问了,不晓得哪错了

    作者回复:

    面试的时候,问到时间复杂度,大部分是考察你对数据结构的了解程度。建议可以多复习下数据结构的知识。

    hashmap的最优时间复杂度是O(1),而最坏时间复杂度是O(n)。

    在没有产生hash冲突的情况下,查询和插入的时间复杂度是O(1);

    而产生hash冲突的情况下,如果是最终插入到链表,链表的插入时间复杂度为O(1),而查询的时候,时间复杂度为O(n);

    在产生hash冲突的情况下,如果最终插入的是红黑树,插入和查询的平均时间复杂度是O(logn)。

    而TreeMap是基于红黑树实现的,所以时间复杂度你也清楚了吧。

    2019-06-04
    1
    5
  • 晓杰
    初始容量2的n次方是偶数,在计算key的索引位置时,是通过(n-1)&hash计算的,这样n-1得到的奇数,那么通过在进行与操作时,如果hash的第一位是0,那么(n-1)&hash得到的是偶数,如果hash的第一位是1,那么(n-1)&hash得到的是奇数,因此可以让数据分布更加均匀,减少hash冲突,相反如果n-1是偶数,那无论hash的第一位是偶数还是奇数,(n-1)&hash得到的都是偶数,不利于数据的分布
    2019-06-05
    4
  • yunfeng
    装载因子0.75是怎么算出来了,是经验值还是什么? 另外为什么链表长度8就要转红黑树呢

    作者回复: 加载因子过高,虽然提高了空间的利用率,但增加了查询时间的成本;加载因子过低,虽然减少查询时间的成本,但是空间利用率又很低了。所以0.75是一个折中的选择。
    链表长度为8转为红黑树的原因是,官方根据泊松分布实验发现,假设hashmap长度length为16,假设放入12(0.75*16)个数据到hashmap中,链表中存放8个节点的概率仅为0.00000006,而链表中存放1~7节点的概率为:

    0: 0.60653066

    1: 0.30326533

    2: 0.07581633

    3: 0.01263606

    4: 0.00157952

    5: 0.00015795

    6: 0.00001316

    7: 0.00000094

    从以上可知,实际上一个链表被放满8个节点的概率非常小,实际上链表转红黑树是非常耗性能的,而链表在8个节点以内的平均查询时间复杂度与黑红树相差无几,超过8个节点,黑红树的查询复杂度会好一些。所以,当链表的节点大于等于8个的时候,转为红黑树的性价比比较合适。

    2019-10-12
    3
  • luzero
    使用2的次幂是因为进行&运算的时候,每次都能落到tables数组内,并且2的次幂进行&运算和直接模运算(%)的值是一样的,也就是说(n-1)&hash==hash%n,如果直接使用(%)模运算最终也会转换成二进制的去计算性能不如&运算,还有就是&计算分布均匀,减少哈希冲突,如果是2的次幂,假设n=16,(16-1)&0==0、(16-1)&1==1、16-1)&2==2、........、(16-1)&19==3、(16-1)&20==4、(16-1)&21==5、。如果不是2的次幂的话,假设是n=15,(15-1)&1==0、(15-1)&1==2、(15-1)&3==2、......、(15-1)&4==4、(15-1)&5==4. 哈哈、不知道我回答的沾不沾边?望老师您点评一下哈

    作者回复: 理解正确,赞

    2019-06-28
    2
  • bro.
    编程中有遇到这种情况,当判断一个数n 是否为偶数使用n%2 == 0 ,计算机语言已经做了优化为 n&(2-1) = n & 1 == 0,对于二进制来说与操作只需要一个电路即可完成比取余速度快多了,相同的对于hash扩容,只需要判断前一位hash值是0还是1,如果是0保持数组位置不变,如果为1增加原来扩容前数组长度即可,而且由于hash值计算每一位都是平均分配0或者1,所以保持均匀分布
    2019-06-10
    2
  • 孙志强
    以前看源码,我记得好像链表转换红黑树不光链表元素大于8个,好像还有一个表的大小大于64

    作者回复: 对的,有这样一个条件。

    2019-06-05
    2
  • Jxin
    一下子追到最新了。老师集合这块讲得是真不错。弱弱补个小点。空集合或空map返回不要new,走常量不可变集合或map。尽量减少对象的创建。毕竟创建和回收都是有开销的。
    2019-06-04
    2
  • Darren
    因为选择下标和扩容的时候都依赖和(n-1)按位与,2的幂次方满足n-1都是1的情况,因此必须选择2的幂次方,且如果使用时传入的参数不是2的幂次方,HashMap会自动转成大于传入参数的最小的2的幂次方来确保下标和扩容机制的正常运行
    2019-06-04
    2
  • 迎风劲草
    主要是为了减少hash冲突,hash & (n-1) n为2的n次幂,n-1换成比特位都是1
    2019-06-05
    1
  • Liam
    Hash字典发生扩容时,需要复制元素,请问这个过程是一次完成的吗?redis里的字典是准备了两个字典,一个原始字典,一个rehash字典,扩容后,不是一次完成数据迁移的,每次操作字典都考虑两个数组并复制数据,扩容完毕后交换两个数组指针

    作者回复: HashMap的扩容是一次性完成的。

    2019-06-05
    1
  • 强哥
    最主要的原因是位运算替代%取模操作,提高运算性能,说什么降低冲突的,是否比较过质数和偶数冲突概率呢?

    作者回复: 用与运算是提高了运算性能,而容量大小为2的幂次方是为了降低哈希冲突。

    2019-06-04
    1
  • WolvesLeader
    hashmap在多线程情况下数据丢失,大师,能不能分析分析原因

    作者回复: 你好,这个在后面多线程中会讲到,可以留意关注下。

    2019-06-04
    1
  • 陆劲
    要是早一天发这个就好了,昨天面试被问到哈希函数给问懵了。老师很棒!这几乎是我在极客跟的最紧的课。

    作者回复: 哈希表在面试中是出现较频繁的,不仅因为它在平时工作中用的比较多,还由于它优秀的设计和优化思想。

    2019-06-04
    1
  • FelixFly
    老师,实际应用中,我们设置初始容量,一般得是 2 的整数次幂,这个HashMap在初始化容量的时候会重新计算,会重新计算为2 的整数次幂
    我们设置初始容量的要考虑加载因子,设置的初始容量是预知数据量 / 加载因子,假如预知容量是20,算出来的结果是26.6,这样设置的初始容量应该为27,但是计算出来的容量是32(也就是2的5次幂),也就是说这时候的默认边界值为32*0.75=24
    还有另一种方法是设置加载因子改为1.0,预售容量是20,设置初始容量为20,加载因子为1.0,这样计算出来的容量是32,也就是说默认边界值是32
    这两种方法在实际应用中哪种比较好点

    作者回复: 第一种,加载因子考虑的更多的是扩容

    2019-11-14
收起评论
51
返回
顶部