HashMap,ConcurrentHashMap 全解析

[TOC]

HashMap从1.7到1.8

简介

hashmap.jpg

数据结构:引入了红黑树

主要介绍

红黑树.png

红黑树

存储流程

main.jpg

数组元素&链表中的实现类

  • HashMap中的数组元素&链表节点采用Node类实现

    与1.7相比(Entry),仅仅只是换了名字

  • 源码见 jdk1.8

红黑树节点实现类

  • HashMap中的红黑树节点采用TreeNode实现

具体使用

主要使用API和使用流程

  • 基本与JDK1.7相同

基础知识:HashMap中的重要参数

主要参数(与1.7相同)

  • 容量(capacity):必须是2的幂 & < 2^30
  • 加载因子(load factor):HashMap在其容量自动增加前可达到多满的一种尺度
  • 扩容阈值(threshold):当哈希表的大小 ≥ 扩容阈值时,就会扩容哈希表(即扩充HashMap的容量)
  • 其他
    • Node - 存储数据的Node类型 数组,长度 = 2的幂;数组的每个元素 = 1个单链表
    • size - HashMap的大小,即 HashMap中存储的键值对的数量

其他参数(与红黑树相关)

  1. 桶的树化阈值:即 链表转成红黑树的阈值,在存储数据时,当链表长度 > 该值时,则将链表转换成红黑树

    static final int TREEIFY_THRESHOLD = 8;

  2. 桶的链表还原阈值:即 红黑树转为链表的阈值,当在扩容(resize())时(此时HashMap的数据存储位置会重新计算),在重新计算存储位置后,当原有的红黑树内数量 < 6时,则将 红黑树转换成链表

    static final int UNTREEIFY_THRESHOLD = 6; 3.

  3. 最小树形化容量阈值:即 当哈希表中的容量 > 该值时,才允许树形化链表 (即 将链表 转换成红黑树) // 否则,若桶内元素太多时,则直接扩容,而不是树形化 // 为了避免进行扩容、树形化选择的冲突,这个值不能小于 4 * TREEIFY_THRESHOLD

    static final int MIN_TREEIFY_CAPACITY = 64;

加载因子

factor.jpg

主要区别

版本 存储的数据结构 数组&链表节点的实现类 红黑树的实现类 核心参数
JDK8 数组+链表+红黑树 Node TreeNode 主要参数相同,1.8增加了红黑树参数
JDK7 数组+链表 Entry / 1. 桶的树化阈值,即 链表转化为红黑树的阈值
2. 桶的链表还原阈值,即红黑树转为链表的阈值
3. 最小树形化容量阈值
- 当哈希表中的容量>该值时,才允许树形化链表
- 否则当桶内元素太多时,则直接扩容,而不是树形化
- 为了避免扩容,树形化选择的冲突,这个值不能小于4*THEEIFY_THRESHOLD

源码分析

  1. 声明HashMap对象

  2. 添加数据,put操作

    • hash操作

      Hash.jpg

    • 1.8 hash过程

      hash8.jpg

    • 计算过程

      com8.jpg

    • 为了解决 “哈希码与数组大小范围不匹配” 的问题,HashMap给出了解决方案:哈希码 与运算(&) (数组长度-1)

    • 扰动处理:加大哈希码低位的随机性,使得分布更均匀,从而提高对应数组存储下标位置的随机性 & 均匀性,最终减少Hash冲突

  3. putVal操作

    • 具体流程

      putval.png

    • put.jpg

    • 扩容机制(resize())

      resize.jpg

      扩容机制对比,

      对比.jpg

  1. 结论

References

Java源码分析:HashMap 1.8 相对于1.7 到底更新了什么?

HashMap? ConcurrentHashMap? 相信看完这篇没人能难住你!

Java7/8 中的 HashMap 和 ConcurrentHashMap 全解析

HASHMAP之扰动函数和低位掩码

美团面试题:Hashmap的结构,1.7和1.8有哪些区别,史上最深入的分析

HashMap源码分析,基于1.8,对比1.7

歧途老农 wechat