Java 性能调优实战
刘超
前金山软件技术经理
58205 人已学习
新⼈⾸单¥59
登录后,你可以任选4讲全文学习
课程目录
已完结/共 49 讲
开篇词 (1讲)
模块一 · 概述 (2讲)
结束语 (1讲)
Java 性能调优实战
15
15
1.0x
00:00/00:00
登录|注册

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

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

常用的数据结构

我在 05 讲分享 List 集合类的时候,讲过 ArrayList 是基于数组的数据结构实现的,LinkedList 是基于链表的数据结构实现的,而我今天要讲的 HashMap 是基于哈希表的数据结构实现的。我们不妨一起来温习下常用的数据结构,这样也有助于你更好地理解后面地内容。
数组:采用一段连续的存储单元来存储数据。对于指定下标的查找,时间复杂度为 O(1),但在数组中间以及头部插入数据时,需要复制移动后面的元素。
链表:一种在物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
链表由一系列结点(链表中每一个元素)组成,结点可以在运行时动态生成。每个结点都包含“存储数据单元的数据域”和“存储下一个结点地址的指针域”这两个部分。
由于链表不用必须按顺序存储,所以链表在插入的时候可以达到 O(1) 的复杂度,但查找一个结点或者访问特定编号的结点需要 O(n) 的时间。
确认放弃笔记?
放弃后所记笔记将不保留。
新功能上线,你的历史笔记已初始化为私密笔记,是否一键批量公开?
批量公开的笔记不会为你同步至部落
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线
笔记
复制
AI
  • 深入了解
  • 翻译
    • 英语
    • 中文简体
    • 中文繁体
    • 法语
    • 德语
    • 日语
    • 韩语
    • 俄语
    • 西班牙语
    • 阿拉伯语
  • 解释
  • 总结
仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《Java 性能调优实战》
新⼈⾸单¥59
立即购买
登录 后留言

全部留言(64)

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

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

    6
    125
  • giserway
    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 这几个位置永远都不能存放元素了,空间浪费相当大,更糟的是这种情况中,数组可以使用的位置比数组长度小了很多,这意味着进一步增加了碰撞的几率,减慢了查询的效率!这样就会造成空间的浪费。

    作者回复: 回答非常到位

    4
    57
  • Sdylan
    装载因子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个的时候,转为红黑树的性价比比较合适。

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

    作者回复: 你好,JDK1.7是考虑新增数据大多数是热点数据,所以考虑放在链表头位置,也就是数组中,这样可以提高查询效率,但这种方式会出现插入数据是逆序的。在JDK1.8开始hashmap链表在节点长度达到8之后会变成红黑树,这样一来在数组后节点长度不断增加时,遍历一次的次数就会少很多,相比头插法而言,尾插法操作额外的遍历消耗已经小很多了。 也有很多人说避免多线程情况下hashmap扩容时的死循环问题,我个人觉得避免死循环的关键不在尾插法的改变,而是扩容时,用了首尾两个指针来避免死循环。这个我会在后面的多线程中讲到hashmap扩容导致死循环的问题。

    4
    31
  • 嘉嘉☕
    加载因子那块儿,感觉有点跳跃,为什么加载因子越大,对空间利用越充分呢?

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

    3
    30
  • 孙志强
    以前看源码,我记得好像链表转换红黑树不光链表元素大于8个,好像还有一个表的大小大于64

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

    22
  • 小小征
    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 移动到高位

    10
    12
  • -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是基于红黑树实现的,所以时间复杂度你也清楚了吧。

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

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

    2
    8
  • M.c
    “这是因为链表的长度超过 8 后,红黑树的查询效率要比链表高,所以当链表超过 8 时,HashMap 就会将链表转换为红黑树”,此处转换为红黑树少了个条件吧?MIN_TREEIFY_CAPACITY要同时大于64

    作者回复: 是的,在源码中可以查到对于的代码,链表长度大于8而且整个map中的键值对大于等于MIN_TREEIFY_CAPACITY (64)时,才进行链表到红黑树的转换。

    3
收起评论
显示
设置
留言
64
收藏
沉浸
阅读
分享
手机端
快捷键
回顶部