HashMap简介（jdk1.8）

在jdk1.8中，HashMap底层由数组+链表+红黑树来实现，性能较之前有了较大的提升。如下为HashMap的继承体系结构：

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

在这里，AbstractMap已经实现了Map接口，再实现一遍并没有任何用处，java集合框架的创始人也承认其为一个小失误。

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
70
71
72
/**
  * 默认的初始化容量为16
  */
 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

 /**
  * 最大容量
  */
 static final int MAXIMUM_CAPACITY = 1 << 30;

 /**
  * 默认负载因子为0.75
  */
 static final float DEFAULT_LOAD_FACTOR = 0.75f;

 /**
  * 链表转红黑树的阈值，当有8个节点的时候转换
  */
 static final int TREEIFY_THRESHOLD = 8;

 /**
  * 红黑树转链表的阈值，当有6个节点的时候转换
  */
 static final int UNTREEIFY_THRESHOLD = 6;

 /**
  * 转红黑树时table的最小容量，如果当前容量小于64则进行扩容而非转换
  */
 static final int MIN_TREEIFY_CAPACITY = 64;

 /**
  * 基本hash节点
  */
 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 String toString() { return key + "=" + value; }

     public final int hashCode() {
         return Objects.hashCode(key) ^ Objects.hashCode(value);
     }

     public final V setValue(V newValue) {
         V oldValue = value;
         value = newValue;
         return oldValue;
     }

     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;
     }
 }

注意：在HashMap中，table的容量只为2的n次方。

构造函数

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
//指定了初始容量和负载因子
   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;
       this.threshold = tableSizeFor(initialCapacity);
   }
//指定了初始容量，将会设置默认负载因子
   public HashMap(int initialCapacity) {
       this(initialCapacity, DEFAULT_LOAD_FACTOR);
   }

   public HashMap() {
       this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
   }

   public HashMap(Map<? extends K, ? extends V> m) {
       this.loadFactor = DEFAULT_LOAD_FACTOR;
       putMapEntries(m, false);
   }

在构造函数中，并没有对table数组进行初始化，而是在第一次put的时候进行初始化，这会在下文进行详细介绍。

tableSizeFor

tableSizeFor方法的主要功能是返回一个比给定整数大且最接近的2的幂次方整数，如给定10，返回2的4次方16。

1
2
3
4
5
6
7
8
9
10
static final int tableSizeFor(int cap) {
 //防止当容量已经是2的幂次方(2^m)了，进行如下操作得到的最终结果会多乘个2，即2^(m+1)
    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;
}

这个方法比较巧妙，n|=n>>>1这一操作确保第一次出现1的位及其后一位（也就是头两位）都是1，而n |= n >>> 2确保头四位都是1，n |= n >>> 4确保头八位都是1，以此类推，一直到n |= n >>> 16结束后就能确保第一次出现1的位及其后面所有位都为1。而此时，n+1即为最接近指定容量的2的幂次方整数。举个例子：

1
2
3
4
5
6
7
8
9
n:         0000 0000 0110 0001  = 97  
n|=n>>>1:  0000 0000 0111 0001  
n|=n>>>2:  0000 0000 0111 1001
n|=n>>>2:  0000 0000 0111 1101  
n|=n>>>4:  0000 0000 0111 1111
...
n|=n>>>16: 0000 0000 0111 1111

n+1:       0000 0000 1000 0000  = 128

hash

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

这个方法先得到key的hashCode，然后将其与高16位进行异或运算重新得到哈希值，之后再通过hash & (table.length - 1) 定位到key在table中的索引位置。假设table的长度为16，具体过程如下：

1
2
3
4
5
h = key.hashCode():    1111 1111 1111 1111 0000 0000 0011 0101
h >>> 16:              0000 0000 0000 0000 1111 1111 1111 1111
hash = h ^ (h >>> 16): 1111 1111 1111 1111 1111 1111 1100 1010
table.length - 1:      0000 0000 0000 0000 0000 0000 0000 1111
hash & (table.length - 1):0000 0000 0000 0000 0000 0000 0000 1010

其中，>>>为无符号右移，左边都将补0，而之所以要进行这一步，是为了当table的值很小时，能让hashCode的高位也参与运算，以减少碰撞的几率，否则仅在高位发生变化总是会发生碰撞。

我们知道，hash如果对table.length取模将得到key在table长度范围内的索引位置，但由于模运算效率较低，这里便采用了与运算进行优化，提高了效率。

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
public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }

final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        //哈希表不为null && 表的长度大于0 && 根据hash值算出表索引的第一个节点不为null
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            //如果第一个节点的key与传入的key相同，则直接返回第一个节点
            if (first.hash == hash && //always check first node
                ((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 { //向下遍历链表直至找到key相同的节点并返回
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        //未找到符合要求的节点，返回null
        return null;
    }

getTreeNode

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
final TreeNode<K,V> getTreeNode(int h, Object k) {
 //如果当前节点有父节点，则先找到其根节点，之后再调用find方法
    return ((parent != null) ? root() : this).find(h, k, null);
}

final TreeNode<K,V> root() {
    for (TreeNode<K,V> r = this, p;;) {
     //如果当前节点的父节点为空，则当前节点为根节点，将其返回
        if ((p = r.parent) == null)
            return r;
        r = p;
    }
}

final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
    TreeNode<K,V> p = this;
    do {
        int ph, dir; K pk;
        TreeNode<K,V> pl = p.left, pr = p.right, q;
        //传入的哈希值小于当前节点的哈希值，则向左遍历
        if ((ph = p.hash) > h)
            p = pl;
        //传入的哈希值大于当前节点的哈希值，则向右遍历
        else if (ph < h)
            p = pr;
        //传入的哈希值等于当前节点的哈希值，则再判断key值是否相同，因为不同的key有可能有相同的hash，这也正是哈希冲突所在
        else if ((pk = p.key) == k || (k != null && k.equals(pk)))
            return p;
        //如果左节点为空，则向右开始遍历
        else if (pl == null)
            p = pr;
        //如果右节点为空，则向左开始遍历
        else if (pr == null)
            p = pl;
        //走到这里说明左右节点都不为空，要开始判断究竟往左还是往右
        else if ((kc != null ||
                  (kc = comparableClassFor(k)) != null) &&  //如果不为null，说明key实现了Comparable接口
                 (dir = compareComparables(kc, k, pk)) != 0)  //比较k和pk的大小，若k<pk则dir<0，k>pk则dir>0
            p = (dir < 0) ? pl : pr;
        //key所属类没有实现Comparable接口，则直接向右开始遍历
        else if ((q = pr.find(h, k, kc)) != null)
            return q;
        //向右没有找到，则向左开始遍历
        else
            p = pl;
    } while (p != null);
 //找不到符合的返回null
    return null;
}

在这个方法中有些人可能会疑虑在同一个索引位置下的红黑树各节点hash值不应该相同吗，为什么还会有判断哈希值大小进入左右节点的操作。其实，不同的hash值在与table的长度相与后，是有可能进入同一个索引位置下的，考虑以下这种情况：

1
2
3
节点1的hash值：  1110 0000 0000 1000 0111
节点2的hash值：  1001 1111 0000 1010 0111
table.length-1：0000 0000 0000 0000 0111

可以看出，节点1与节点2在进行了hash & (table.length - 1)后值都为0000 0000 0000 0000 0111，因此会放置在table中同一个索引位置下。

comparableClassFor、compareComparables

comparableClassFor方法判断对象x所属类c是否实现了Comparable接口，如果实现了则返回所属类c，否则返回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
static Class<?> comparableClassFor(Object x) {
    if (x instanceof Comparable) {
        Class<?> c; Type[] ts, as; Type t; ParameterizedType p;
        //如果x是个字符串对象则直接返回String类，因为String类本身就已经实现了Comparable接口
        if ((c = x.getClass()) == String.class) // bypass checks
            return c;
        //Type[] getGenericInterfaces，此方法将返回带泛型参数信息的本类直接实现的接口
        if ((ts = c.getGenericInterfaces()) != null) {
            for (int i = 0; i < ts.length; ++i) {
             //如果此接口为泛型接口
                if (((t = ts[i]) instanceof ParameterizedType) &&
                 //如果该泛型接口的原始类型为Comparable
                    ((p = (ParameterizedType)t).getRawType() ==
                     Comparable.class) &&
                     //如果该泛型接口只有一个泛型参数，且此泛型参数类型为c，则返回c
                    (as = p.getActualTypeArguments()) != null &&
                    as.length == 1 && as[0] == c) // type arg is c
                    return c;
            }
        }
    }
    //如果该对象所属类没有实现Comparable接口，则返回null
    return null;
}

以上代码中，for (int i = 0; i < ts.length; ++i)下的一系列判断其实就是想要看x所属类c是否实现了Comparable<c>。

1
2
3
4
static int compareComparables(Class<?> kc, Object k, Object x) {
    return (x == null || x.getClass() != kc ? 0 :
            ((Comparable)k).compareTo(x));
}

此方法中，如果x与k的类相同，则进行比较。否则，返回0。

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
 public V put(K key, V value) {
     return putVal(hash(key), key, value, false, true);
 }

 /**
  * @param onlyIfAbsent 如果为true，则不改变已经存在的value，仅仅当不存在value的时候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为空或者长度为0，则先调用resize()方法进行扩容
     if ((tab = table) == null || (n = tab.length) == 0)
         n = (tab = resize()).length;
     //如果通过hash计算得到的table该索引位置还没有节点，则创建一个新节点作为头节点
     if ((p = tab[i = (n - 1) & hash]) == null)
         tab[i] = newNode(hash, key, value, null);
     //该索引位置已存在节点
     else {
         Node<K,V> e; K k;
         //判断当前节点的hash与key是否与参数中的hash与key相同，如果相同，则说明p为要查找的节点，将其赋值给e
         if (p.hash == hash &&
             ((k = p.key) == key || (key != null && key.equals(k))))
             e = p;
         //判断节点是否为红黑树节点，如果是则调用红黑树的相关方法
         else if (p instanceof TreeNode)
             e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
         else {
         //如果节点不为红黑树节点而是链表节点，则遍历链表节点，并统计该链表的节点数binCount
             for (int binCount = 0; ; ++binCount) {
              //如果已经到了链表尾部，则根据传入的hash与key等创建一个新节点加入链表尾部
                 if ((e = p.next) == 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))))
                     //此时e节点即为目标节点，跳出循环
                     break;
                 //将p设置为下一个节点
                 p = e;
             }
         }
//如果e节点不为null，则说明链表中包含目标节点，用新值覆盖旧值并返回旧值
         if (e != null) { // existing mapping for key
             V oldValue = e.value;
             if (!onlyIfAbsent || oldValue == null)
                 e.value = value;
             afterNodeAccess(e);
             return oldValue;
         }
     }
     //走到这一步说明插入了新的节点，size大小需要加一
     ++modCount;
     if (++size > threshold)
      //如果size超过了阈值，则进行扩容
         resize();
     afterNodeInsertion(evict);
     return null;
 }

putTreeVal

在进行红黑树的操作时，依然会维护链表的结构。

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
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
                               int h, K k, V v) {
    Class<?> kc = null;
    boolean searched = false;
    TreeNode<K,V> root = (parent != null) ? root() : this;
    for (TreeNode<K,V> p = root;;) {
        int dir, ph; K pk;
        //如果目标节点的hash值小于当前节点，则将dir设为-1，代表向左查找
        if ((ph = p.hash) > h)
            dir = -1;
        //如果目标节点的hash值大于当前节点，则将dir设为1，代表向右查找
        else if (ph < h)
            dir = 1;
        //如果目标节点的hash值等于当前节点，则判断key是否相等，如果相等，则说明当前节点为目标节点，将其返回
        else if ((pk = p.key) == k || (k != null && k.equals(pk)))
            return p;
        //如果要查找的key没有实现Comparable接口或者pk与k的所属类不同
        else if ((kc == null &&
                  (kc = comparableClassFor(k)) == null) || 
                 (dir = compareComparables(kc, k, pk)) == 0) {
            //第一次执行查找
            if (!searched) {
                TreeNode<K,V> q, ch;
                searched = true;
                //左右子树分别调用find进行查找，如果找到了则返回
                if (((ch = p.left) != null &&
                     (q = ch.find(h, k, kc)) != null) ||
                    ((ch = p.right) != null &&
                     (q = ch.find(h, k, kc)) != null))
                    return q;
            }
            //如果依然没有找到，则再进行最后一次比较
            dir = tieBreakOrder(k, pk);
        }

        TreeNode<K,V> xp = p;
        //如果p节点的左节点或者右节点为null，则说明找到了要放入的位置
        if ((p = (dir <= 0) ? p.left : p.right) == null) {
            Node<K,V> xpn = xp.next;
            TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
            if (dir <= 0)
                xp.left = x;
            else
                xp.right = x;
            //到这里维护了xp->x->xpn这一链表结构
            xp.next = x;
            x.parent = x.prev = xp;
            if (xpn != null)
                ((TreeNode<K,V>)xpn).prev = x;
            //进行红黑树的插入平衡操作
            moveRootToFront(tab, balanceInsertion(root, x));
            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
final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    //如果老table为空，则老t
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {  //如果老table不为空
        if (oldCap >= MAXIMUM_CAPACITY) {  //且老table的容量已经大于最大容量
            //将阈值设置为最大整型
            threshold = Integer.MAX_VALUE;
            //直接返回老table，不再扩容
            return oldTab;
        }
        //将新容量设置为老容量的两倍
        //如果新容量小于最大容量且老容量大于十六，则将新阈值也提高到原来的两倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    //如果table为空，但老阈值大于0，说明构造函数时指定了初始化容量但从未加入过元素，此时将老阈值赋给新容量，详解见下文
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    //老table为空，且老阈值为0，说明构造函数时未指定初始化容量
    else {               // zero initial threshold signifies using defaults
     //将新容量设置为默认初始化容量
        newCap = DEFAULT_INITIAL_CAPACITY;
        //将新阈值设置为默认负载因子*默认初始化容量
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    //如果新阈值为0，则用新容量*负载因子赋值
    if (newThr == 0) {
        float ft = (float)newCap * loadFactor;
        //如果新容量或者新阈值大于最大容量，则将新阈值设为最大整型，以后不再扩容
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                  (int)ft : Integer.MAX_VALUE);
    }
    //将新阈值赋值给阈值属性
    threshold = newThr;
    @SuppressWarnings({"rawtypes","unchecked"})
    //用新容量大小创建一个新table
        Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    //将新table赋值给table属性
    table = newTab;
    //如果老table不为空，则将其中的元素全部放到新table中去
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            //如果该索引位置头节点不为空
            if ((e = oldTab[j]) != null) {
             //将老表该索引位置设为空，方便垃圾收集器回收
                oldTab[j] = null;
                //如果该索引位置只有一个节点，则根据其hash计算值放入新表中
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                //如果为树节点，则调用红黑树相关方法
                else if (e instanceof 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;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        //如果hash与oldCap相与为0则存储在原索引位置，详解见下方
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                             //e为头节点的情况
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        //如果hash与oldCap相与不为0则存储在原索引位置+原容量，详解见下方
                        else {
                            if (hiTail == null)
                                //e为头节点的情况
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
                     //尾节点的next属性为空
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                     //尾节点的next属性为空
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    //返回新表
    return newTab;
}

我们可以看到在此方法中有一个条件判断else if (oldThr > 0)，当table为空但阈值却大于零时，将阈值赋值给新容量。这里有个疑问是为什么会发生table为空但阈值却大于零这种情况？我们可以回过头看看构造函数，可以发现在所有构造函数中都没有对数组table进行过分配，而仅仅设置了阈值this.threshold = tableSizeFor(initialCapacity);，既然在构造时没有分配，那肯定就是在第一次扩容时分配的，也就正是上面的代码。

此处还有一个疑问是：为什么扩容后新的存储位置只为原位置或原位置+原容量？请看这么一个例子，假设oldCap=0100, newCap=1000,节点a的hash为1110,节点b的hash为1010。oldCap-1的值为0011，显然对于节点来说只有后两位决定了它们的位置（因为前两位无论如何都为0），而newCap-1的值为0111，此时后三位决定了它们的位置，与之前不同正在于节点的第三位是0还是1，而第三位的值正可以通过oldCap(在此也就是0100)相与来进行判断，如果相与结果为0000，则说明第三位的值为0，在和newCap-1相与后结果将不变，依然在原索引位置；而如果相与结果为0100，则说明节点第三位值是1，也就是原索引值加上原容量。

treeifyBin

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
final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    //如果table为空或者table的长度小于可转换为红黑树的最小容量，则调用resize方法扩容
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize();
    //如果根据hash计算得到的索引位置下的节点不为空，则遍历整条链表
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        do {
         //将链表节点转换为红黑树节点
            TreeNode<K,V> p = replacementTreeNode(e, null);
            //如果为第一次循环
            if (tl == null)
             //将p设置为头节点
                hd = p;
            //否则，不为第一次循环
            else {
             //将当前节点与上一个节点关联起来，维护链表结构
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        //将hash计算得到的索引位置的头节点赋为新的树节点
        if ((tab[index] = hd) != null)
         //以头节点为根构建红黑树
            hd.treeify(tab);
    }
}

TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
    return new TreeNode<>(p.hash, p.key, p.value, next);
}

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
final void treeify(Node<K,V>[] tab) {
    TreeNode<K,V> root = null;
    //x的初始值为根节点，但开始时还未赋值给root
    for (TreeNode<K,V> x = this, next; x != null; x = next) {
        next = (TreeNode<K,V>)x.next;
        x.left = x.right = null;
        //如果root还未被赋值，则将根节点赋值给它
        if (root == null) {
         //根节点没有父节点
            x.parent = null;
            //红黑树根节点必须为黑色
            x.red = false;
            root = x;
        }
        else {
      //见下文
            K k = x.key;
            int h = x.hash;
            Class<?> kc = null;
            for (TreeNode<K,V> p = root;;) {
                int dir, ph;
                K pk = p.key;
                if ((ph = p.hash) > h)
                    dir = -1;
                else if (ph < h)
                    dir = 1;
                else if ((kc == null &&
                          (kc = comparableClassFor(k)) == null) ||
                         (dir = compareComparables(kc, k, pk)) == 0)
                    dir = tieBreakOrder(k, pk);

                TreeNode<K,V> xp = p;
                if ((p = (dir <= 0) ? p.left : p.right) == null) {
                    x.parent = xp;
                    if (dir <= 0)
                        xp.left = x;
                    else
                        xp.right = x;
                    //红黑树的插入平衡调整
                    root = balanceInsertion(root, x);
                    break;
                }
            }
        }
    }
    //将根节点移到table索引位置的头节点
    moveRootToFront(tab, root);
}

treeify方法用来构建一棵以调用该方法的节点为根节点的红黑树。由于红黑树依然维护着链表结构，每次通过next属性获得下一个节点时，都会从根节点开始向下查找，根据hash值的大小找到合适的位置放入，并设置好parent与left或right属性以关联节点。

remove

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
public V remove(Object key) {
    Node<K,V> e;
    //如果未找到要删除的节点则返回空，否则返回要删除的节点的value值
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

/**
 * @param matchValue 如果为true，则只有当value也相等的时候才移除
 */
final Node<K,V> removeNode(int hash, Object key, Object value,
                           boolean matchValue, boolean movable) {
    Node<K,V>[] tab; Node<K,V> p; int n, index;
 //如果table不为空且table的长度不为0且table该索引位置的头节点不为空
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (p = tab[index = (n - 1) & hash]) != null) {
        Node<K,V> node = null, e; K k; V v;
        //如果当前节点的hash值和key都与传入的相等，则当前节点就是目标节点，将其赋值给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 {
                 //如果当前节点是目标节点，则将其赋值给node，并跳出循环
                    if (e.hash == hash &&
                        ((k = e.key) == key ||
                         (key != null && key.equals(k)))) {
                        node = e;
                        break;
                    }
                    //将p设为下一节点
                    p = e;
                } while ((e = e.next) != null);
            }
        }
        //如果找到了要删除的节点且要删除的节点的value与传入的value相等或者压根不需要匹配value
        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;
            afterNodeRemoval(node);
            //返回被移除的节点
            return node;
        }
    }
    //未找到要删除的节点，直接返回null
    return null;
}

常见问题

有关HashMap的常见面试题总结请移步 HashMap常见面试题总结