发表更新Java / Java基础1 小时读完 (大约9608个字)

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），实现了Map、Cloneable、Serializable 接口。

  • 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>[] table 和 newTab 的容量必定是 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

许可协议

#

喜欢这篇文章？打赏一下作者吧

评论

关注我
×