Java基础:JDK8 HashMap源码及数据结构分析

HashMap 是 Java 中非常重要的集合类型,其具有快速存储,快速查找(时间复杂度非常低,非效非常高),自动扩容等特点,在实际开发中经常用到。

关于 HashMap 特性,底层原理也是面试中被问到概率极高的问题,因为 HashMap 涉及到好几个基本数据结构及相关算法知识,如组数,链表,二叉树及变种,Hash算法等。所以有必要对其深入理解。

哈希表

HashMap 使用了基本的数据结构,先了解下有助于理解。详细可能考 数据结构与算法(一):数组、链表、哈希表

哈希表(Hash Table):,提供键(Key) 和值(Value)映射关系。只要给出 key ,就可以高效查找到映射的 Value,时间复杂度接近于 Ο(1),在哈希表中添加,删除,查找等操作,性能非常高 。

哈希表在本质上也是一个数组,通过 哈希函数 将 Key 的哈希值转换为数组的索引,使 key:hashcode -> index 建立映射关系。

例如一个长度为 8 的数组,key 为 001121,使用取模运算,转换为数组下标 index = hashcode("001121") % Array.length = 1420036703 / 8 = 7

哈希冲突

通过哈希函数得出的元素在数组中的索引位已被占用, 就出现了哈希冲突。将哈希值转换为有限的数组索引,很大概率出现哈希冲突的问题。解决此问题通常有两种方式:一种是开放 寻址法,一种是 链表法(数组+链表)。

HashMap 用到了链表法,数组中的每一个元素不仅是一个 Entry 对象,还可能是一个链表的头节点。每一个 Entry 对象通过 next 指针指向它的下一个 Entry 节点。当新来的 Entry 映射到与之冲突的数组位置时,只需插入到对应的链表中即可。

链表法缺点:如果链表越来越长,则链表查找的性能就会越来越差,在 HashMap 中执行插入和查询操作的时间复杂度就提高到了 O(n)。(HashMap 是遍历到链表尾节插入)。

JDK 7 的 HashMap 的数据结构是基于 哈希表+链表

JDK 8 对 HashMap 的数据结构进行了优化,引入了 红黑树,即采用了 哈希表+链表 / 红黑树 的数据结构,当链表长度超过 8 时,则将链表树化,这样就避免了超长链表的缺点,红黑树的查询插入的时间复杂度是 O(logn),提高了性能。

HashMap

相关特性

Java 语言中,要了解某一功能特性,最好的方式是阅读源码上的注释,JDK 源码的注释是非常严谨和规范的。这一点值的学习。

HashMap 是基于 哈希表 的 Map 接口的实现,提供所有可选的 Map 操作。

  • 允许 Key 为 null 值和 Value 为 null 值。
  • 不同步,非线程安全。
  • 不保证有序(如插入顺序),也不保证恒定时间顺序不变(若扩容的话则会重新分布)。

假设哈希函数将元素适当地分布在存储桶(Buckets)之间,为基本的 get/put 操作提供了稳定的性能。迭代 Collection 视图所需的时间与 HashMap 实例的容量(capacity:桶的数量)及其大小(键/值映射的元素数量)成比例。所以,如果迭代性能很重要,则不要将初始容量设置得太高(或将加载因子设置得太低)。

源码分析

类继承

1
2
3
4
5
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {

private static final long serialVersionUID = 362498820763181265L;
//.......省略其它.......
}

HashMap 继承自父类(AbstractMap),实现了MapCloneableSerializable 接口。

  • Map 接口定义了一组通用的操作。
  • Cloneable 接口表示可以进行拷贝,在HashMap中,实现的是浅层次拷贝,即拷贝的是对象的引用,而不是对象本身,被拷贝对象的改变会影响被拷贝的对象。
  • Serializable 接口表示 HashMap 实现了序列化,设置了序列化版本号。即 HashMap 对象会保存至本地,之后可以恢复。

构造方法

HashMap 实例有两个影响其性能的参数:初始容量和负载因子。容量是哈希表中存储桶的数量,初始容量只是创建哈希表时的容量。

  • size(个数):Map 中 Key-Value 元素的个数。

  • Capacity(容量):是哈希表中存储桶(Buckets)的数量,初始容量(initialCapacity)只是创建哈希表时的容量,默认是 16,最大容量是 1073741824

  • loadFactor(负载因子):是在哈希表的容量自动扩容之前,衡量哈希表满表的系数,默认是 0.75f

    当哈希表中的元数个数超过了负载因子和当前容量的乘积时,则认为满表并对哈希表进行重置(即,内部数据结构被重建),使得新哈希表的存储桶数大约是之前桶数的两倍。

    默认负载因子(0.75f)在时间和空间成本之间提供了一个较好的权衡。较高的值会减少空间开销,但会增加查找成本。

    设置初始容量,应考虑 Map 中预期的元数个数及其负载因子,以最大程序地减少重新哈希操作的次数。

    如果设置了初始容量且大于最大容量除以负载因子的值,则不会发生任何重新哈希操作。附加参考load factor in HashMap

  • threshold(扩容前阀值):threshold = capacity * loadFactor,当 size 大于 threshold 时会执行 resize 扩容操作。

成员变量:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
* map 中包含 key/value 元素个数
*/
transient int size;

/**
* 默认的初始容量 - 必须是2的幂数
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

/**
* 最大的容量, 如果构造方法传入的容量超过此值时,则使用此最大值
* 必须是2的幂数, MAXIMUM_CAPACITY = 1 << 30 = 1073741824
*/
static final int MAXIMUM_CAPACITY = 1 << 30;

/**
* 默认负载因子,如果没有显式指定负载因子时使用
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;

HashMap 构造方法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
/**  
* 传入初始容量和负载因子(0.75)构造一个空的实例
*/
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
//threshold=(capacity * loadFactor), 是决定是否扩容的阀值(注意,此代表容易误解)
this.threshold = tableSizeFor(initialCapacity);
}

/**
* 传入初始容量,使用默认的负载因子(0.75)构造一个空的实例
*/
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

/**
* 使用默认的初始容量(16) 和 默认的负载因子(0.75)构造一个空的实例
*/
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

/**
* 将其它 Map 的元素添加到此 HashMap
*/
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}

/**
* 利用已存在的 map 创建 HashMap
* 被 Map 构造方法,Map.putAll 和 Map.clone 调用
*/
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
//得到 m 中的元素总数
int s = m.size();
if (s > 0) {
//判断是否需要初始化 table
if (table == null) { // pre-size
//计算HashMap容量
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
if (t > threshold)
//重新计算阀值
threshold = tableSizeFor(t);
}
//判断是否进行扩容
else if (s > threshold)
resize();
//遍历原始的 Map,调用 putVal 方法添加元素
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
//插入元素
putVal(hash(key), key, value, false, evict);
}
}
}
  • public HashMap(int initialCapacity, float loadFactor)

    在此构造方法中设置了 threshold 的值, 这个值是扩容前的阀值,当 HashMap 的 size 大于 threshold 时,就执行 resize(),也就是扩容。

    扩容操作是在调用 putVal 方法添加元素时触发的,源码如下:

    1
    2
    3
    4
    5
    6
    7
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    //...........省略........
    if (++size > threshold)
    //size 大于 threshold,执行扩容
    resize();
    //...........省略........
    }

    构造方法中 this.threshold = tableSizeFor(initialCapacity) 不易理解,若写成 this.threshold = tableSizeFor(initialCapacity) * this.loadFactor,就更易理解 threshold = capacity * loadFactor 的定义。

    注意,此构造方法中并没有对 table 这个成员变量初始化,而是被推迟到第一次执行 put 方法时赋值,初始化 table会调用 resize() 方法,在 resize 方法中对 threshold 进行重新赋值。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    transient Node<K,V>[] table;

    public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
    }

    final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab;
    Node<K,V> p;
    int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
    //第一次执行 put 方法时进入,调用 resize 方法
    n = (tab = resize()).length;
    //.......省略......
    }

    final Node<K,V>[] resize() {
    //第一次执行put, table == null
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length; // oldCap=0
    int oldThr = threshold;//实例传入的容量
    int newCap, newThr = 0;
    if (oldCap > 0) {
    //.....省略.....
    }
    else if (oldThr > 0)
    // 初始化容量,threshold 初始值也是初始容量
    newCap = oldThr;
    else {
    // 若没有赋值,则使用默认值
    newCap = DEFAULT_INITIAL_CAPACITY;
    newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    if (newThr == 0) {
    float ft = (float)newCap * loadFactor;
    //小于允许的最大容量,返回 ft = (float)newCap * loadFactor; newCap = oldThr = threshold;
    newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
    (int)ft : Integer.MAX_VALUE);
    }
    //重新给 threshold 赋值
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    //创建容量为 newCap 的 newTab
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    //.......省略.......
    return newTab;
    }
  • static final int tableSizeFor(int cap)

    该方法返回一个大于等于且最接近 cap 的 2 的幂次方整数。如给定 9,返回 2 的 4 次方 16,以给 threshold 赋初始值。

    在构建 HashMap 实例时会给 threshold 赋初始值,调用 tableSizeFor 方法得到的,此值实际也是 HashMap 的初始容量

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    /**
    * 返回一个大于等于且最接近 cap 的2的幂次方整数。如给定9,返回2的4次方16。
    */
    static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

    从上代码可以看出,HashMap 的容量必定是 2 的幂数(即 Node<K,V>[] tablenewTab 的容量必定是 2 的幂数),就是如果构建实例时传入了的容量值不是 2 的幂数,例如给定 9,则容量实际是 16,即在的创建实例传入的容量可能不是 HashMap 实际的容量,实际容量是调用 tableSizeFor 方法计算得出,是最接近 cap 的 2 的幂次方整数,等于或大于指定的的容量值

    方法执行逻辑分析:

    第一行代码 int n = cap - 1 是为了防止 cap 已经是 2 的幂时,执行完后面逻辑后返回的值是 cap 的 2 倍,因为 cap 已经是 2 的幂,就已经满足条件了,2倍就存在浪费了。。

    n 转为二进制执行>>> 无符号右移,高位直接补 0,再执行或|运行,然后赋值。可将 n |= n>>>1翻译为n = n | (n>>>1)。此算法的核心是让某些二进制位全部都变为 1。

    tableSizeFor 算法解析

Hash算法

HashMap 底层的数据结构是 数组+链表/红黑树,主干是数组。

get / put 方法通过对 key 进行 hash 运算,再通过算法将 hash 值转换为数组索引, 实际是建立一个 key -> index 的映射关系,这样在每次根据 Key 查找时,就可以计算出对应的数组索引,就可以直接找到对应的 key-value对象,时间复杂度是 O(1)

HashMap 的 get/put 都是先对 Key 执行hash后再做业务操作,源码如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
public boolean containsKey(Object key) {
return getNode(hash(key), key) != null;
}
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}

/** 要理解HashMap中的Hash算法的精秒之处,最好先看下方法的注释。
* Computes key.hashCode() and spreads (XORs) higher bits of hash
* to lower. Because the table uses power-of-two masking, sets of
* hashes that vary only in bits above the current mask will
* always collide. (Among known examples are sets of Float keys
* holding consecutive whole numbers in small tables.) So we
* apply a transform that spreads the impact of higher bits
* downward. There is a tradeoff between speed, utility, and
* quality of bit-spreading. Because many common sets of hashes
* are already reasonably distributed (so don't benefit from
* spreading), and because we use trees to handle large sets of
* collisions in bins, we just XOR some shifted bits in the
* cheapest possible way to reduce systematic lossage, as well as
* to incorporate impact of the highest bits that would otherwise
* never be used in index calculations because of table bounds.
*/
static final int hash(Object key) {
int h;
//当 key 为 null 时,存储的是索引为 0 的位置,即第一个位置
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

key.hashCode() 得到散列值为 32位有符号 int 整数,取值范围从 -2,147,483,648‬ 到 2,147,483,647,前后加起来大概 40亿的映射空间,如果直接用来做为数组索引,不一定有这么大连续的内存,且太浪费没必要。HashMap 的初始容量才 16,Key 的 hash 值是不能直接拿来用的,需要通过一定算法映射成数组索引来找到在哈希表中的位置。

HashMap 中的 hash 方法是先调用 hashCode() 方法取得 hash 值,再将 hash 值无符号右移 16 位,正好是 32位的一半,高位全补 0,再与原 hash 值做异或^运算(高半区与低半区做异或运算),对低位进行了**扰动**,混合了原始哈希码的高位和低位,异或后的值的高区 16 位 与原始 hash 值相比没有变化,低区的 16 位发生了变化,增加了低位的随机性,使该 hashCode 映射成数组下标时可以更均匀。

  • 哈希表数组索引计算:

    从 HashMap 的 get / put 源码中可以看到计算数组index方式是:

    index =(n - 1) & hash

    • n 是哈希表的容量,是 2 的 幂次方,是数组table 的长度。
    • hash 是对 key 执行 hashCode 再将高16位 与 低16位做异或运算后的值。

    写个测试例子,看看 (n - 1) & hash 这个算法计算出来的索引。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    @Test
    public void arrayIndex() {
    int n = 16;
    //假如有20个元素,数组容量是16, key 分别是 0-19, 使用索引算法计算出结果
    for (int i = 0; i < 20; i++) {
    int key = i;
    int keyHash = new Integer(key).hashCode();
    int val = keyHash >>> 16;
    int hash = keyHash ^ val;

    int index = ((n - 1) & hash);
    //int index = hash % n;
    System.out.print(index + ", ");
    }
    System.out.println();
    }
    //输出结果:
    // & 与运算 :0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0, 1, 2, 3,
    // % 取余运算:0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0, 1, 2, 3,

    从上输出结果可以看出,计算索引的**&与运算** 与 求余运算 得出的结果一致的,超过数组容量计算出的索引位存在冲突。

  • 计算索引算法解析:

    (n - 1) & hash:(数组长度-1)正好相当于一个 低位掩码,低位全是 1, &与操作时的结果是将散列值的高位全部归零,只保留低位值,这个值一定是小于 n 的,就满足数组索引取值范围,所以用来做数组下标。效果等同于 hash % n,但计算机的位运算算术运算 高效的多。

    1
    2
    3
    4
    	10100101 11000100 00100101
    & 00000000 00000000 00001111
    -----------------------------------------
    00000000 00000000 00000101 // & 与运算,高位全归零,只保留低位值

    如果直接使用 key 的 hash 进行&与运算,就算 hash 分布再松散,要是只取最后几位的话,冲突就会很严重。

    如果散列本身做得不好,分布上成等差数列的漏洞,恰好使最后几个低位呈现规律性重复,就极其糟糕。

    这时扰动函数的价值就体现出来了,将高半区与低半区进行异或运算,使高半位充分参与 Hash 运算。看下面这个图。

    哈希表数组索引计算逻辑

  • 为什么数组长度必须是2的幂:

    从上面内容可知,数组长度 n是 2 的幂,n - 1 转二进制后,低位全是 1,而扩容后的容量是原来的 2 倍,扩容后的容量二进制表示正好是在 n -1的二进制全为1的前一位加1,即扩容后只有一位差,也就是多出了最左位的 1。

    这样在通过 (n - 1) & hash 的时候,只要 hash 对应的最左边的那一个差异位为0,就能保证得到的新的数组索引和老数组索引一致。

put方法

HashMap 通过 put 方法插入元素,Key 和 Value 可以为 null。put 方法调用了 putVal 方法来插入元素。

HashMap 的主干是一个 Node<K,V> 类型的 Entry 数组,Entry 是 HashMap 的基本组成单元,每一个 Entry 包含一个key-value键值对(其实就是一个保存了两个对象之间映射关系的一种集合)。

HashMap 的插入操作分两步:先进行查找,如果 key 已经存在,则覆盖 Value;否则根据查找到的位置,新建节点完成插入。

  • 成员变量

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    /**
    * 第一次使用时初始化, 必要会调用大小。分配时, 长度一定是 2 的幂次方
    * 实际存储 key-value 数组, key和value被封装成了 Node
    * JDK 1.8 之前存放链表的表头,1.8中引入红黑树,链表树化后,就是树的根
    */
    transient Node<K,V>[] table;

    /**
    * map 中 key-value 元素个数
    */
    transient int size;

    /**
    * HashMap 结构被修改的次数
    */
    transient int modCount;

    /**
    * threshold = capacity * loadFactor
    * 扩容前的阀值
    */
    int threshold;

    /**
    * 扩容因子
    */
    final float loadFactor;

    /**
    * JDK 1.8 对Hash冲突可能导致超长链表做了优化,引入了红黑树。
    * 当链表中节点个数大于 TREEIFY_THRESHOLD, 就会将链表树化,以提高查询效率。
    * 链表转为树的阀值。此值必须大于2,且至少等于8,
    */
    static final int TREEIFY_THRESHOLD = 8;

    /**
    * 非树化的阀值。对于已经是树形的桶,会做一个split操作
    * 若剩下的元素个数小于 UNTREEIFY_THRESHOLD, 则将其非树化,重新转回链表结构
    * 此值应小于 UNTREEIFY_THRESHOLD, 且最大值为 6
    */
    static final int UNTREEIFY_THRESHOLD = 6;

    /**
    * 树化的最小 table 容量,如果没达到容量但节点又太多,则使用扩容
    * 当一个链表中的元素个数大于树化阀值并请求 treeifyBin 操作
    * 值至少为 4 * TREEIFY_THRESHOLD 的值, 以避免 resize 和 树化阀值之间的冲突
    */
    static final int MIN_TREEIFY_CAPACITY = 64;
  • Node<K, V>源码:是 HashMap 的内部静态类

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;//链表元素

    Node(int hash, K key, V value, Node<K,V> next) {
    this.hash = hash;
    this.key = key;
    this.value = value;
    this.next = next;
    }

    public final K getKey() { return key; }
    public final V getValue() { return value; }
    public final V setValue(V newValue) {
    V oldValue = value;
    value = newValue;
    return oldValue;
    }

    public final String toString() { return key + "=" + value; }

    //重写了 hashCode() 方法
    public final int hashCode() {
    return Objects.hashCode(key) ^ Objects.hashCode(value);
    }

    //判断两个node是否相等,若key和value都相等,返回true。可以与自身比较为true
    public final boolean equals(Object o) {
    if (o == this)
    return true;
    if (o instanceof Map.Entry) {
    Map.Entry<?,?> e = (Map.Entry<?,?>)o;
    if (Objects.equals(key, e.getKey()) &&
    Objects.equals(value, e.getValue()))
    return true;
    }
    return false;
    }
    }
  • put 方法源码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    public V put(K key, V value) {
    //调用 putVal, 传入了 key 的 hash 值
    return putVal(hash(key), key, value, false, true);
    }

    /**
    * Map.put 和相关方法的实现
    */
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab;
    Node<K,V> p;
    int n, i;
    //如果是第一次执行, table 为 null, 调用 resize() 扩容初始化 table
    if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length;
    //确定传入Key的hashd在数组中对应的下标 i, p 在这里被赋值
    if ((p = tab[i = (n - 1) & hash]) == null)
    //槽位如果为 null,则创建节点插入(可能是链表头节点或树根)
    tab[i] = newNode(hash, key, value, null);
    else {
    //进入这里,说明桶位置已被占用(可能链表或红黑树)
    Node<K,V> e; K k;
    if (p.hash == hash &&
    ((k = p.key) == key || (key != null && key.equals(k))))
    //若该位置上的第一个元素p与传入的元素信息匹配,则将使用 p 给 e 赋值
    e = p;
    else if (p instanceof TreeNode)
    //如果 p 是树形节点, 一棵红黑树的根节点,调用 putTreeVal 执行操作
    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
    else {
    //走到这里,说明 p 是个链表头,则遍历链表, binCount 表示链表节点数
    for (int binCount = 0; ; ++binCount) {
    // e 指向 p 的下一个节点
    if ((e = p.next) == null) {
    //如果为 null,即链尾,新建节点并插入
    p.next = newNode(hash, key, value, null);
    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
    //如果节点数已达到树化阀值,则将链表树化
    treeifyBin(tab, hash);
    break;
    }
    if (e.hash == hash &&
    ((k = e.key) == key || (key != null && key.equals(k))))
    //如果在链表中匹配到 Key,跳出循环
    break;
    //用于遍历桶中的链表,
    p = e;
    }
    }

    if (e != null) { // existing mapping for key
    //走到这里,说明找到了与 key 相匹配的节点 e
    //暂存有节点当前的值为 oldValue
    V oldValue = e.value;
    if (!onlyIfAbsent || oldValue == null)
    //如果 onlyIfAbsent=true,则已存在的值不被覆盖,随非旧值为 null
    //onlyIfAbsent=false, 则用新值覆盖旧值
    e.value = value;
    //钩子方法,HashMap中是个空方法,但是在其子类LinkedHashMap中会被Override
    //通知子类:节点e被访问过了
    afterNodeAccess(e);
    //返回已被覆盖的节点e的oldValue
    return oldValue;
    }
    }
    /*******执行到这里,说明没有匹配的 Key,是新节点插入******/
    //结构修改计数 +1,创建迭代器后结构被并发修改,引发 fail-fast
    ++modCount;
    //插入元数后, size+1, 如果已大于扩容的阀值
    if (++size > threshold)
    // 如果 size 大于扩容阀值,则调用 resize()执行扩容
    resize();
    //钩子方法,通知子类有新节点插入
    afterNodeInsertion(evict);
    //新节点插入,无旧值可返回,返回null
    return null;
    }

插入操作的大致流程:

  1. 先通过 Key 的 hash 定位到 table 数组中的一个桶位。

  2. 如果桶位没有被占用,则新建节点插入,记录结构修改数,判断是否扩容,结束。

    如果桶被占用,则与第一个元素(节点)进行匹配,若成功,则无需后续的树判断和链表遍历操作,直接覆盖;否则的话则判断节点类型。

  3. 如果桶的第一个节点 p 是 TreeNode 类型,则表示桶中存在的是一棵红黑树,则调用 putTreeVal 方法来处理。否则,该桶中就是一个链表,则对有进行遍历。

  4. 若遍历链表的某个节点匹配到了 e,就跳出循环执行覆盖;否则循环直到链表尾节点(必为 null),新建节点,挂在链表尾节点上,自己成为新的链表尾。

  5. 在链表插入新节点时,还会判断链表的长度是否达到树化的阀值,如果大于阀值,则调用 treeifyBin 方法来树化。

  6. 每插入一个新元素,size 会加 1,最后根据 size 是否大于扩容阀值,如果大于阀值,则调用 resize 执行扩容操作。

get方法

了解了 HashMap 的 Hash 算法和 put 方法的逻辑,get 方法就更容易理解了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
* 返回 key 映射的值, 如果没有映射就返回 null
*/
public V get(Object key) {
Node<K,V> e;
//null 判断,返回值
return (e = getNode(hash(key), key)) == null ? null : e.value;
}

/**
* Map.get 和相关方法的实现
*/
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab;
Node<K,V> first, e;
int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//进入这里,表示 table 有元素,并且索引位不为 null
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
//如果第一个元素的 hash 相等, 且(key 相等 或 equals 为 true)
return first;
if ((e = first.next) != null) {
//进入这里,表示需要从链表或红黑树中查找
if (first instanceof TreeNode)
//如果槽位是 TreeNode 类型,表示是红黑树,调红黑树的 getTreeNode 查找
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
//进入这里,表示槽位是链表
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
//循环直到找到元素
return e;
} while ((e = e.next) != null);//do...while...循环
}
}
return null;
}

链表树化

如果数组桶位是个链表,在向链表插入元素后,会判断链表的长度是否大于树化阀值,如果大于,则调用 treeifyBin 方法将链表树化。树化过程是创建树和向树中插入节点。

  • TreeNode<K,V>:树形节点

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent; // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev; // needed to unlink next upon deletion
    boolean red;
    TreeNode(int hash, K key, V val, Node<K,V> next) {
    super(hash, key, val, next);
    }
    //.....省略方法.....
    }
  • treeifyBin 源码

    如果 table 数组为 null 或长度小于树化要求的最小容量,则用扩容取代树化

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    /**
    * Replaces all linked nodes in bin at index for given hash unless
    * table is too small, in which case resizes instead.
    * 将链表转化为红黑树
    */
    final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index;
    Node<K,V> e;
    //判断, 给 n 赋值,tab 的容量
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
    //如果 table 数组为 null 或长度小于树化要求的最小容量,则用扩容取代树化
    resize();
    else if ((e = tab[index = (n - 1) & hash]) != null) { //这里给数组索引index赋值
    //走进来,定位到hash对应的桶位,赋值给 e
    //定义两个树形节点指针,分别指向链表头,尾节点
    TreeNode<K,V> hd = null, tl = null;
    do {
    //将 Node 类型节点替换为 TreeNode 类型的 p
    TreeNode<K,V> p = replacementTreeNode(e, null);
    if (tl == null)
    //若为 null,则将 p 赋值给 hd
    hd = p;
    else {
    //将tl赋值为p的前节点
    p.prev = tl;
    //将p赋值为tl的下一节点
    tl.next = p;
    }
    //尾指针后移
    tl = p;
    //如果有子节点则继续循环
    } while ((e = e.next) != null);
    //将链表头节点插入table的index位置
    if ((tab[index] = hd) != null)
    //通过 treeify 方法将链表树化
    hd.treeify(tab);
    }
    }
  • treeify树化

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    /**
    * Forms tree of the nodes linked from this node.
    * @return root of tree
    * 将链表树化
    */
    final void treeify(Node<K,V>[] tab) {
    //声明根节点 root
    TreeNode<K,V> root = null;
    //声明变量 x,next,从调用节点 this 开始遍历
    for (TreeNode<K,V> x = this, next; x != null; x = next) {
    //下一节点
    next = (TreeNode<K,V>)x.next;
    //当前x节点的左右子树置为空
    x.left = x.right = null;
    if (root == null) {
    x.parent = null; //根节点的父节点为 null
    x.red = false; //红黑树根结点为黑色
    //若 root 为空,则将 x 赋值为根节点 root
    root = x;
    }
    //否则,将当前节点插入到已有的树中
    else {
    K k = x.key;
    int h = x.hash;
    Class<?> kc = null;
    for (TreeNode<K,V> p = root;;) {
    //第二层循环执行对一个节点的插入操作
    //从根结点开始循环寻找适合 x 的位置,并完成插入
    int dir, ph;
    K pk = p.key;
    if ((ph = p.hash) > h)
    //若 x.hash 小于p的,则往p的左子树中继续寻找
    dir = -1;
    else if (ph < h)
    //否则在右子树中寻找
    dir = 1;
    else if ((kc == null && (kc = comparableClassFor(k)) == null) ||
    (dir = compareComparables(kc, k, pk)) == 0)
    //若两节点hash值相等,且key不可比,则利用System.identityHashCode方法来决定一个方向
    dir = tieBreakOrder(k, pk);

    //将当前节点p暂存为xp
    TreeNode<K,V> xp = p;
    //根据上面算出的 dir 值选择将 p 向下左子树或右子树移
    //若为空,说明找到合适位置执行插入,否则继续循环
    if ((p = (dir <= 0) ? p.left : p.right) == null) {
    //将 parent 指针指向 xp
    x.parent = xp;
    if (dir <= 0) //根据dir决定x是作为xp的左孩子还是右孩子
    xp.left = x;
    else
    xp.right = x;
    //每次插入新节点后都需要做平衡操作(满足红黑树性质)
    root = balanceInsertion(root, x);
    break; //插入完成,跳出循环
    }
    }
    }
    }
    //对红黑树的平衡调整可能会更换根节点,
    //通过moveRootToFront方法确保table[index]中的节点与插入前相同
    moveRootToFront(tab, root);
    }

resize扩容

HashMap 在调用 put 方法添加元素后,发现元素总数(size)大于了阀值(threshold),就会执行扩容操作。

阀值(threshold) = 容量(capacity ) * 负载因子(loadFactor),默认的负载因子是 0.75f,可理解为当一个 Map 填满了 75% 的 Bucket 时,就会调用 resize 方法进行扩容。

putVal()源码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab;
Node<K,V> p;
int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
//首次put table==null
n = (tab = resize()).length;

//......中间代码忽略......

// 结构被修改次数
++modCount;
//修改 size 的值, 本次 put 成功后 ++size
if (++size > threshold)
//size 大于 threshold,则调用 resize() 进行扩容
resize();
afterNodeInsertion(evict);
return null;
}

resize()源码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
/**
* 初始化或翻倍增加表大小。如果为空,则根据阀值(threshold)来分配置初始容量(capacity)
* 否则,因为使用的是 2 的幂,所以每个 Bucket 中的元素必须保持相同的索引,或者在新表中以 2 的幂偏移。
*/
final Node<K,V>[] resize() {
// 当前已存在的 table
Node<K,V>[] oldTab = table;
// oldTab 为 null 表示 table 还未初始化, oldCap=0
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 如果使用空参构造没有指定容量,就不会给阀值赋值,默认就为 0
// 如果指定了初始容量,threshold 就会在构造方法中被赋值为最接近初始容量值的2的幂方整数
int oldThr = threshold;
// 初始化新的 table 容量和阀值
int newCap, newThr = 0;
// 如果 oldCap > 0 表示 table 已初始化,HashMap有执行 put 添加元素
if (oldCap > 0) {
//如果旧容量大于允许的最大值 1<< 30
if (oldCap >= MAXIMUM_CAPACITY) {
//则将阀值赋值为int类型最大值,表示充分使用空间
threshold = Integer.MAX_VALUE;
//不能执行扩容,返回旧表
return oldTab;
}
//将旧容量向左移一位,即增加1倍,再赋值给新的容量,若小于允许的最大容量,且大于默认的初始容量
//注意:在这个if判断条件里设置了扩容的大小 newCap = oldCap << 1
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//阀值也进行扩容,即增加1倍
newThr = oldThr << 1;
}
//如果旧阀值大于 0,即调用 HashMap 构造方法显式传入了阀值
//如果创建 HashMap 实例指定了初始容量,初始化 table 走进这里
else if (oldThr > 0)
//初始化容量为阀值(注意,是在这里赋初始化容量)
newCap = oldThr;
else {
//否则就使用默认的大小,计算阀值
//使用 HashMap 空参构造,初始化 table 会直接走到这里赋初始值
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//如果构造方法指定了容量,table初始化,此 newThr 初始值一直是 0
if (newThr == 0) {
//计算阀值
float ft = (float)newCap * loadFactor;
//给阀值赋值(新容量小于允许最大容量,且 ft 小于)
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
//赋新的阀值
threshold = newThr;

/**
* 下面是重点了,构建新的 table
*/
@SuppressWarnings({"rawtypes","unchecked"})
//创建一个新容量大小数组 newTab
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
//赋值
table = newTab;
if (oldTab != null) {
//老的桶不为 null, 就循环遍历转移元素
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
//oldTab[j] 上存在元素就赋值给 e
if ((e = oldTab[j]) != null) {
//旧的置为 null
oldTab[j] = null;
//如果 e 没有后续节点
if (e.next == null)
//直接计算 e 在 newTab 上的位置并放入。
newTab[e.hash & (newCap - 1)] = e;
//如果 e 是 TreeNode 类型节点, 要进行 红黑树的 rehash 操作
else if (e instanceof TreeNode)
//将红黑树分隔成2次插入到新桶中
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
//走取这里,说明该节点是个链表
//将连表拆成2个链表,分别找到新桶中的位置后插入
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
//获得子节点
next = e.next;
//因容量是 2 的幂次方,二进制表示只有 1 位是 1,其它全是 0
//容量再与 hash 做与运算,则得到的只能是 1 或 0
if ((e.hash & oldCap) == 0) {
//索引不变的链表
if (loTail == null)
//头,形成链表
loHead = e;
else
//尾,存在(hash冲突)则插入到子节点
loTail.next = e;
loTail = e;
}
else {
//索引发生改变的链表
if (hiTail == null)
//形成连表
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
//do...while循环,至少会执行一次
} while ((e = next) != null);
//定位2个链表在新桶中的位置,然手插入
if (loTail != null) { // 原 bucket 位置的尾指针不为空(即还有子节点)
loTail.next = null; // 链表最后得有个 null
newTab[j] = loHead; // 链表头指针放在新桶的相同下标(j)处
}
if (hiTail != null) {
hiTail.next = null;
//扩容是原来的2倍,原与旧容量与操作不为 0 的元素要迁移
//而这个新的位置正好是当前位置+旧容量
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}

16位扩容为32位的 resize 示意图

非线程安全

HashMap 使用同步,是非线程安全的。如果多个线程同时访问,且至少有一个线程修改了其结构,则必须在外部进行同步。(结构修改:指添加或删除一个或多个元素的任何操作;仅更改键的值不是结构修改)。

如果无法在外部进行同步,则应使用如下方式来包装 Map,最好是在创建实例时完成此操作。

1
Map m = Collections.synchronizedMap(new HashMap(...))

HashMap 的所有 集合视图 方法返回的迭代器都是快速失败(fail-fast)的,如果在创建迭代器后的任何时间结构被修改,除了迭代器自己的 remove 方法外,该迭代器都将抛出 ConcurrentModificationException 异常。因此,面对并发修改,迭代器会快速干净地失败,防止任何风险,迭代器的快速失败行为仅应用于检测错误。

HashMap非线程安全的,其主要体现:

  1. 在 JDK 1.7 中,在多线程环境下,扩容时会造成环形链或数据丢失。
  2. 在 JDK 1.8 中,在多线程环境下,会发生数据覆盖的情况。

具体分析可参考 HashMap 为什么线程不安全?

与HashTable区别

HashMap HashTable
线程安全 非线程案全,
性能相对高些。
线程安全,方法上使用synchronized
比较粗暴
NULL值 允许 Key / Value 为 Null,
Key 为 Null 时存在 table 数组第一个节点上。
判断键是否存在使用 containsKey() 方法
不允许 Key 为Null
继承关系 继承自 AbstractMap 继承自 Dictionary
初始容量与负载因子 初始容量:16
负载因子:0.75f
初始容量:11
负载因子:0.75f
扩容方式 原容量的2倍:newCap = oldCap << 1 原容量的2倍+1:
newCapacity = (oldCapacity << 1) + 1
底层结构 JDK 7 :数组 + 链表
JDK 8 :数组 + 链表 / 红黑树
数组 + 链表
哈希算法 hash = (h = key.hashCode()) ^ (h >>> 16)
index = (n - 1) & hash
hash = key.hashCode();
index = (hash & 0x7FFFFFFF) % tab.length;

与HashSet区别

HashSet 不是 Key / Value 结构,仅仅是存储不重复的元素。

HashSet 的内部实现是 HashMap,HashSet 里面的元素填充到 HashMap 的 Key,HashMap 的 Vaule 使用同一个 Object 对象填充。

因此 HashSet 也是非线程安全的,HashSet 可以理解为 HashMap 的简化版。

HashSet 构造方法

1
2
3
public HashSet() {
map = new HashMap<>();
}

HashSet add方法

1
2
3
4
private static final Object PRESENT = new Object();
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}

数据结构图

JDK 1.7

  1. HashMap 数据结构图

    HashMap 数据结构图

JDK 1.8

  1. HashMap 数据结构图

    HashMap 数据结构简图

  2. put 方法逻辑图

    HashMap Put 方法逻辑图

相关参考

  1. 解析HashMap的tableSizeFor方法
  2. 源码分析系列文章-HashMap
  3. 深入理解HashMap系列
  4. 美团:Java 8系列之重新认识HashMap
  5. 一文读懂 JDK8 HashMap
  6. HashMap中的hash算法总结
  7. HashMap中的hash算法中的几个疑问
  8. JDK 源码中 HashMap 的 Hash 方法原理
  9. HashMap死循环分析的修正版
  10. 重新认识JDK1.8 中不一样的HashMap:提供了 JDK1.7 VS JDK1.8 性能比较。
  11. 红黑树在HashMap中的应用:说明了红黑树的操作
  12. Java集合之 JDK7 HashMap:演示了容量为何为2的幂,重写 equals和 hashCode 方法
  13. HashMap分析之红黑树树化过程:描述了红黑树及树操作
  14. 关于 HashMap 1.8 的重大更新:对比了Jdk1.7与Jdk1.8的区别,脑图,流程图。
  15. HashMap 数组+链表+红黑树:比较多,但也比较杂,排版不好
  16. Jdk1.7 HashMap底层实现和原理:描述了链表的几种形式,补充了 1.8 的区别
  17. Jdk 1.8 扩容后的元素新位置为原位置+原数组长度:解释了 newTab[j + oldCap] = hiHead
  18. HashMap之put方法流程解读:详细描述 put 方法。
  19. 了解数据结构:Array、HashMap、List:描述了多数据结构的插入、查找、删除的时间复杂度比较
  20. 掌握 HashMap 看这一篇文章就够了:Jdk 1.7 和 1.8 较全面的比较分析
  21. 彻底理解HashMap的元素插入原理:图较多,比较清晰
  22. HashMap是如何工作的?:哈希冲突的解决方法,在维基百科中,总结出了四大类
  23. What is the significance of load factor in HashMap?

Java基础:JDK8 HashMap源码及数据结构分析

http://blog.gxitsky.com/2020/01/28/Java-jdk-14-hashmap-sourcecode/

作者

光星

发布于

2020-01-28

更新于

2022-06-17

许可协议

评论