JDK1.8下的HashMap源码、特性_hashmap新特性

作者：你好赵伟 | 2024-05-13 16:43:55

踩

hashmap新特性

1、hashMap特点

在这里插入图片描述

hashMap通过key的hashcode值将数据存储到数组中，数组中的每个元素都像图中<Key,Value>结构。当然，在计算key的hash值的时候可能会出现相同的情况，也就是hash冲突，当出现hash冲突时，将会用链表进行存储，也就是在链表尾部增加元素。(JDK1.8中若链表长度大于8则转换为红黑树)
HashMap线程不安全，由于线程不安全，所以相对的性能较高
HashMap可以存储null键和null值（只允许一个key值为null）
HashMap存储不保证顺序存储
HashMap迭代整个集合的时间和容量及键值对有关，HashMap的一个实例有两个影响其性能的参数：初始容量和负载因子。
HashMap是以哈希桶方式存储的。
其Iterator迭代器采用的是快速失败机制

2、HashMap常用功能源码分析

在 JDK1.8 中，HashMap 是由数组+链表+红黑树构成，新增了红黑树作为底层数据结构，结构变得复杂了，但是效率也变的更高效。接下来我们看下源码。
　 2.1.

     //默认容量16
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
     //最大容量1<<30=1073741824个,1<<31=-2147483648（如果移动的位数超过了该类型的最大位数(32)，那么编译器会对移动的位数取模。如对int型移动33位，实际上只移动了33%32=1位。）
    static final int MAXIMUM_CAPACITY = 1 << 30;
    //负载因子，用于扩容使用。（元素超过16*0.75=12 时会进行扩容，jdk1.7与1.8扩容代码不同，下面会讲到）
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    //某个位置链表长度大于8时会转红黑树
    static final int TREEIFY_THRESHOLD = 8;
	//树节点小于6时转为链表
    static final int UNTREEIFY_THRESHOLD = 6;

    //hashMap中数量大于64时转为红黑树
    static final int MIN_TREEIFY_CAPACITY = 64;
1
2
3
4
5
6
7
8
9
10
11
12
13
14

3、添加元素

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

①：可以看到putVal方法传了一个hash(key)方法计算出的hash值。我们看下hash(key)方法。

 static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }
1
2
3
4

这里为什么要用key的hashcode与他的高16位做运算呢？因为这样运算返回的结果在计算数组位置的时候效率更高（如下图）。

 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)
            n = (tab = resize()).length;
            //就是这里(n - 1) & hash
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
1
2
3
4
5
6
7
8
9

可见当我们put一个元素时，hash(）方法返回的int hash的值，通过
(n - 1) & hash的方法确定位置。因为我们要计算数组中的位置会用hash % n的方法计算，但是当length总是2的n次方时（这也是为什么数组长度总是2的n次方的原因），(n - 1) & hash运算等价于对length取模。但是&比%具有更高的效率。
而采用高16位和低16位进行异或，也可以让所有的位数都参与越算，使得在length比较小的时候也可以做到尽量的散列。

public V put(K key, V value) {
        /**四个参数，第一个hash值，第四个参数表示如果该key存在值，如果为null的话，则插入新的value，最后一个参数，在hashMap中没有用，可以不用管，使用默认的即可**/
        return putVal(hash(key), key, value, false, true);
    }
 
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        //tab 哈希数组，p 该哈希桶的首节点，n hashMap的长度，i 计算出的数组下标
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        //获取长度并进行扩容，使用的是懒加载，table一开始是没有加载的，等put后才开始加载
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        /**如果计算出的该哈希桶的位置没有值，则把新插入的key-value放到此处，此处就算没有插入成功，也就是发生哈希冲突时也会把哈希桶的首节点赋予p**/
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        //发生哈希冲突的几种情况
        else {
            // e 临时节点的作用， k 存放该当前节点的key 
            Node<K,V> e; K k;
            //第一种，插入的key-value的hash值，key都与当前节点的相等，e = p，则表示为首节点
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            //第二种，hash值不等于首节点，判断该p是否属于红黑树的节点
            else if (p instanceof TreeNode)
                /**为红黑树的节点，则在红黑树中进行添加，如果该节点已经存在，则返回该节点（不为null），该值很重要，用来判断put操作是否成功，如果添加成功返回null**/
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            //第三种，hash值不等于首节点，不为红黑树的节点，则为链表的节点
            else {
                //遍历该链表
                for (int binCount = 0; ; ++binCount) {
                    //如果找到尾部，则表明添加的key-value没有重复，在尾部进行添加
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        //判断是否要转换为红黑树结构
                        if (binCount >= TREEIFY_THRESHOLD - 1) 
                            treeifyBin(tab, hash);
                        break;
                    }
                    //如果链表中有重复的key，e则为当前重复的节点，结束循环
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            //有重复的key，则用待插入值进行覆盖，返回旧值。
            if (e != null) { 
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        //到了此步骤，则表明待插入的key-value是没有key的重复，因为插入成功e节点的值为null
        //修改次数+1
        ++modCount;
        //实际长度+1，判断是否大于临界值，大于则扩容
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        //添加成功
        return 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
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

4、扩容机制

扩容（resize），我们知道集合是由数组+链表+红黑树构成，向 HashMap 中插入元素时，如果HashMap 集合的元素已经大于了最大承载容量threshold（capacity * loadFactor），这里的threshold不是数组的最大长度。那么必须扩大数组的长度，Java中数组是无法自动扩容的，我们采用的方法是用一个更大的数组代替这个小的数组，就好比以前是用小桶装水，现在小桶装不下了，我们使用一个更大的桶。

JDK1.8融入了红黑树的机制，比较复杂，这里我们先介绍 JDK1.7的扩容源码，便于理解，然后在介绍JDK1.8的源码。

	//参数 newCapacity 为新数组的大小
    void resize(int newCapacity) {
        Entry[] oldTable = table;//引用扩容前的 Entry 数组
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {//扩容前的数组大小如果已经达到最大(2^30)了
            threshold = Integer.MAX_VALUE;///修改阈值为int的最大值(2^31-1)，这样以后就不会扩容了
            return;
        }

        Entry[] newTable = new Entry[newCapacity];//初始化一个新的Entry数组
        transfer(newTable, initHashSeedAsNeeded(newCapacity));//将数组元素转移到新数组里面
        table = newTable;
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);//修改阈值
    }
    void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        for (Entry<K,V> e : table) {//遍历数组
            while(null != e) {
                Entry<K,V> next = e.next;
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                int i = indexFor(e.hash, newCapacity);//重新计算每个元素在数组中的索引位置
                e.next = newTable[i];//标记下一个元素，添加是链表头添加
                newTable[i] = e;//将元素放在链上
                e = next;//访问下一个 Entry 链上的元素
            }
        }
    }

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

通过方法我们可以看到，JDK1.7中首先是创建一个新的大容量数组，然后依次重新计算原集合所有元素的索引，然后重新赋值。如果数组某个位置发生了hash冲突，使用的是单链表的头插入方法，同一位置的新元素总是放在链表的头部，这样与原集合链表对比，扩容之后的可能就是倒序的链表了。

下面我们在看看JDK1.8的。

	//参数 newCapacity 为新数组的大小
    void resize(int newCapacity) {
        Entry[] oldTable = table;//引用扩容前的 Entry 数组
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {//扩容前的数组大小如果已经达到最大(2^30)了
            threshold = Integer.MAX_VALUE;///修改阈值为int的最大值(2^31-1)，这样以后就不会扩容了
            return;
        }

        Entry[] newTable = new Entry[newCapacity];//初始化一个新的Entry数组
        transfer(newTable, initHashSeedAsNeeded(newCapacity));//将数组元素转移到新数组里面
        table = newTable;
        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);//修改阈值
    }
    void transfer(Entry[] newTable, boolean rehash) {
        int newCapacity = newTable.length;
        for (Entry<K,V> e : table) {//遍历数组
            while(null != e) {
                Entry<K,V> next = e.next;
                if (rehash) {
                    e.hash = null == e.key ? 0 : hash(e.key);
                }
                int i = indexFor(e.hash, newCapacity);//重新计算每个元素在数组中的索引位置
                e.next = newTable[i];//标记下一个元素，添加是链表头添加
                newTable[i] = e;//将元素放在链上
                e = next;//访问下一个 Entry 链上的元素
            }
        }
    }

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

该方法分为两部分，首先是计算新桶数组的容量 newCap 和新阈值 newThr，然后将原集合的元素重新映射到新集合中。
　　相比于JDK1.7，1.8使用的是2次幂的扩展(指长度扩为原来2倍)，所以，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。我们在扩充HashMap的时候，不需要像JDK1.7的实现那样重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”。

/**
     * Initializes or doubles table size.  If null, allocates in
     * accord with initial capacity target held in field threshold.
     * Otherwise, because we are using power-of-two expansion, the
     * elements from each bin must either stay at same index, or move
     * with a power of two offset in the new table.
     *  @return the table
     * 
     * 
     *
     * 初始化或者翻倍表大小。
     * 如果表为null，则根据存放在threshold变量中的初始化capacity的值来分配table内存
     * （这个注释说的很清楚，在实例化HashMap时，capacity其实是存放在了成员变量threshold中，
     * 注意，HashMap中没有capacity这个成员变量）
     * 。如果表不为null，由于我们使用2的幂来扩容，
     * 则每个bin元素要么还是在原来的bucket中，要么在2的幂中
     * 
     * 此方法功能：初始化或扩容
     */
    final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        //新的容量值，新的扩容阀界值
        int newCap, newThr = 0;
        //oldTab!=null,则oldCap>0
        if (oldCap > 0) {
            //如果此时oldCap>=MAXIMUM_CAPACITY(1 << 30)，表示已经到了最大容量，这时还要往map中放数据，则阈值设置为整数的最大值 Integer.MAX_VALUE，直接返回这个oldTab的内存地址。 
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            //如果(当前容量*2<最大容量&&当前容量>=默认初始化容量（16）)
            //并将将原容量值<<1(相当于*2)赋值给 newCap
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && 
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                //如果能进来证明此map是扩容而不是初始化
                //操作：将原扩容阀界值<<1(相当于*2)赋值给 newThr
                newThr = oldThr << 1; // double threshold
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
            //进入此if证明创建map时用的带参构造：public HashMap(int initialCapacity)或 public HashMap(int initialCapacity, float loadFactor)
            //注：带参的构造中initialCapacity（初始容量值）不管是输入几都会通过 “this.threshold = tableSizeFor(initialCapacity);”此方法计算出接近initialCapacity参数的2^n来作为初始化容量（初始化容量==oldThr）
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
            //进入此if证明创建map时用的无参构造：
            //然后将参数newCap（新的容量）、newThr(新的扩容阀界值)进行初始化
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        if (newThr == 0) {
            
            //进入此if有两种可能
            // 第一种：进入此“if (oldCap > 0)”中且不满足该if中的两个if
            // 第二种：进入这个“else if (oldThr > 0)”
            
            //分析：进入此if证明该map在创建时用的带参构造，如果是第一种情况就说明是进行扩容且oldCap（旧容量）小于16，如果是第二种说明是第一次put
            float ft = (float)newCap * loadFactor;
            //计算扩容阀界值
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        //如果“oldTab != null”说明是扩容，否则直接返回newTab
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                        //如果该元素是TreeNode的实例
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        Node<K,V> loHead = null, loTail = null;//此对象接收会放在原来位置
                        Node<K,V> hiHead = null, hiTail = null;//此对象接收会放在“j + oldCap”（当前位置索引+原容量的值）
                        Node<K,V> next;
                        do {
                            next = e.next;
                            //以下是扩容操作的核心，详情见我的博客：https://www.cnblogs.com/shianliang/p/9204942.html
                            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;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }
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

5、删除元素

HashMap 删除元素首先是要找到桶的位置，然后如果是链表，则进行链表遍历，找到需要删除的元素后，进行删除；如果是红黑树，也是进行树的遍历，找到元素删除后，进行平衡调节，注意，当红黑树的节点数小于 6 时，会转化成链表。

    public V remove(Object key) {
        //临时变量
        Node<K,V> e;
        /**调用removeNode(hash(key), key, null, false, true)进行删除，第三个value为null，表示，把key的节点直接都删除了，不需要用到值，如果设为值，则还需要去进行查找操作**/
        return (e = removeNode(hash(key), key, null, false, true)) == null ?
            null : e.value;
    }
    
    /**第一参数为哈希值，第二个为key，第三个value，第四个为是为true的话，则表示删除它key对应的value，不删除key,第四个如果为false，则表示删除后，不移动节点**/
    final Node<K,V> removeNode(int hash, Object key, Object value,
                               boolean matchValue, boolean movable) {
        //tab 哈希数组，p 数组下标的节点，n 长度，index 当前数组下标
        Node<K,V>[] tab; Node<K,V> p; int n, index;
        //哈希数组不为null，且长度大于0，然后获得到要删除key的节点所在是数组下标位置
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (p = tab[index = (n - 1) & hash]) != null) {
            //nodee 存储要删除的节点，e 临时变量，k 当前节点的key，v 当前节点的value
            Node<K,V> node = null, e; K k; V v;
            //如果数组下标的节点正好是要删除的节点，把值赋给临时变量node
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                node = p;
            //也就是要删除的节点，在链表或者红黑树上，先判断是否为红黑树的节点
            else if ((e = p.next) != null) {
                if (p instanceof TreeNode)
                    //遍历红黑树，找到该节点并返回
                    node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
                else { //表示为链表节点，一样的遍历找到该节点
                    do {
                        if (e.hash == hash &&
                            ((k = e.key) == key ||
                             (key != null && key.equals(k)))) {
                            node = e;
                            break;
                        }
                        /**注意，如果进入了链表中的遍历，那么此处的p不再是数组下标的节点，而是要删除结点的上一个结点**/
                        p = e;
                    } while ((e = e.next) != null);
                }
            }
            //找到要删除的节点后，判断!matchValue，我们正常的remove删除，!matchValue都为true
            if (node != null && (!matchValue || (v = node.value) == value ||
                                 (value != null && value.equals(v)))) {
                //如果删除的节点是红黑树结构，则去红黑树中删除
                if (node instanceof TreeNode)
                    ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
                //如果是链表结构，且删除的节点为数组下标节点，也就是头结点，直接让下一个作为头
                else if (node == p)
                    tab[index] = node.next;
                else /**为链表结构，删除的节点在链表中，把要删除的下一个结点设为上一个结点的下一个节点**/
                    p.next = node.next;
                //修改计数器
                ++modCount;
                //长度减一
                --size;
                /**此方法在hashMap中是为了让子类去实现，主要是对删除结点后的链表关系进行处理**/
                afterNodeRemoval(node);
                //返回删除的节点
                return node;
            }
        }
        //返回null则表示没有该节点，删除失败
        return 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
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

6、查找元素

①、通过 key 查找 value

首先通过 key 找到计算索引，找到桶位置，先检查第一个节点，如果是则返回，如果不是，则遍历其后面的链表或者红黑树。其余情况全部返回 null。

    public V get(Object key) {
        Node<K,V> e;
        //也是调用getNode方法来完成的
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }
 
    final Node<K,V> getNode(int hash, Object key) {
        //first 头结点，e 临时变量，n 长度,k 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) {
            //如果是头结点，则直接返回头结点
            if (first.hash == hash && 
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            //不是头结点
            if ((e = first.next) != null) {
                //判断是否是红黑树结构
                if (first instanceof TreeNode)
                    //去红黑树中找，然后返回
                    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);
            }
        }
        //找不到，表示不存在该节点
        return 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

7总结

为什么引入红黑树而不是其他结构？

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/你好赵伟/article/detail/564482