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

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

链地址法
再哈希函数法
开放定址法
由n个有限结点组成的具有层次关系的集合
通过哈希函数映射关键码值到表中位置
查找时间复杂度为O(n)
插入时间复杂度为O(1)
插入数据时需要复制移动后面的元素
时间复杂度为O(1)
数组+链表+红黑树的数据结构
设置初始容量和加载因子
HashMap存储键值对的高效性
JDK 1.8扩容方式
JDK 1.7扩容方式
重写key值的hashCode()方法
链表转换为红黑树
(n - 1) & hash计算存储位置
hash()方法
边界值(threshold)
加载因子(loadFactor)
Node数组
哈希冲突解决方法
哈希表实现
哈希表
链表
数组
思考题
总结
HashMap扩容优化
HashMap获取元素优化
HashMap添加元素优化
HashMap的重要属性
HashMap的实现结构
常用的数据结构
深入浅出HashMap的设计与优化

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

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

常用的数据结构

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

HashMap是Java中常用的容器类之一,它通过哈希表数据结构存储键值对,提高了查询效率。本文深入浅出地介绍了HashMap的设计与优化。首先,文章回顾了常用的数据结构,为读者提供了数据结构的基础知识。接着,详细解释了HashMap的实现结构,强调了其基于哈希表的设计,并介绍了解决哈希冲突的方法。文章重点解释了Node数组、加载因子和边界值的作用,以及它们对HashMap性能的影响。此外,还提到了加载因子对空间利用和查询效率的影响,以及边界值对HashMap数组的重新分配和效率的影响。在JDK1.8中,HashMap引入了红黑树数据结构来提升链表的查询效率。文章还介绍了HashMap的扩容优化,以及如何在编码中优化HashMap的性能。总的来说,通过深入浅出的方式,帮助读者全面了解了HashMap的设计与优化,为读者提供了宝贵的技术知识。HashMap的设计与优化是Java中常用的容器类之一,通过哈希表数据结构存储键值对,提高了查询效率。文章深入浅出地介绍了HashMap的设计与优化,包括其实现结构、解决哈希冲突的方法、加载因子和边界值的作用,以及在JDK1.8中引入的红黑树数据结构。此外,还介绍了HashMap的扩容优化和在编码中优化HashMap的性能。通过本文,读者可以全面了解HashMap的设计与优化,获得宝贵的技术知识。

仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《Java 性能调优实战》
新⼈⾸单¥59
立即购买
登录 后留言

全部留言(64)

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

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

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

    作者回复: 回答非常到位

    2019-06-04
    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个的时候,转为红黑树的性价比比较合适。

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

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

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

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

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

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

    2019-06-05
    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 移动到高位

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

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

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

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

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

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