leisurexi's Blog.

HashMap

集合
字数统计: 12.1k阅读时长: 52 min
2019/08/15 Share

这章开始我们对Map的具体实现类来进行介绍，首先是HashMap，而Map中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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
/**
 * The default initial capacity - MUST be a power of two.
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默认容量16

/**
 * The maximum capacity, used if a higher value is implicitly specified
 * by either of the constructors with arguments.
 * MUST be a power of two <= 1<<30.
 */
static final int MAXIMUM_CAPACITY = 1 << 30; //最大容量

/**
 * The load factor used when none specified in constructor.
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f; //默认负载因子0.75

/**
 * The bin count threshold for using a tree rather than list for a
 * bin.  Bins are converted to trees when adding an element to a
 * bin with at least this many nodes. The value must be greater
 * than 2 and should be at least 8 to mesh with assumptions in
 * tree removal about conversion back to plain bins upon
 * shrinkage.
 */
static final int TREEIFY_THRESHOLD = 8; //链表节点转红黑树节点阈值9个节点转

/**
 * The bin count threshold for untreeifying a (split) bin during a
 * resize operation. Should be less than TREEIFY_THRESHOLD, and at
 * most 6 to mesh with shrinkage detection under removal.
 */
static final int UNTREEIFY_THRESHOLD = 6; //红黑树转链表节点阈值6个节点转

/**
 * The smallest table capacity for which bins may be treeified.
 * (Otherwise the table is resized if too many nodes in a bin.)
 * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
 * between resizing and treeification thresholds.
 */
static final int MIN_TREEIFY_CAPACITY = 64; // 转红黑树时，table最小长度


/**
 * Basic hash bin node, used for most entries.  (See below for
 * TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
 */
static class Node<K,V> implements Map.Entry<K,V> { //基本的hash节点，继承自Map.Entry
    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;
    }
}

字段

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
/**
    * The table, initialized on first use, and resized as
    * necessary. When allocated, length is always a power of two.
    * (We also tolerate length zero in some operations to allow
    * bootstrapping mechanics that are currently not needed.)
    */
   transient Node<K,V>[] table; //存放节点的数组，又叫作桶（bucket）

   /**
    * Holds cached entrySet(). Note that AbstractMap fields are used
    * for keySet() and values().
    */
   transient Set<Map.Entry<K,V>> entrySet; //作为entrySet()的缓存

   /**
    * The number of key-value mappings contained in this map.
    */
   transient int size; //实际节点个数

   /**
    * The number of times this HashMap has been structurally modified
    * Structural modifications are those that change the number of mappings in
    * the HashMap or otherwise modify its internal structure (e.g.,
    * rehash).  This field is used to make iterators on Collection-views of
    * the HashMap fail-fast.  (See ConcurrentModificationException).
    */
   transient int modCount; //集合修改次数

   /**
    * The next size value at which to resize (capacity * load factor).
    *
    * @serial
    */
   // (The javadoc description is true upon serialization.
   // Additionally, if the table array has not been allocated, this
   // field holds the initial array capacity, or zero signifying
   // DEFAULT_INITIAL_CAPACITY.)
   int threshold; //扩容的阈值 = table.length * loadFactor 

   /**
    * The load factor for the hash table.
    *
    * @serial
    */
   final float loadFactor; //负载因子

静态工具方法

hash

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

key的hash值高16不变，低16位与高16位异或作为key的最终hash值 。（h >>> 16）代表无符号右移16位，高位补0，任何数跟0异或都是其本身，因此key的hash值高16位不变。

整个过程本质上就是三步：

  1. 拿到key的hashCode值
  2. 将hashCode值高位参与运算，重新计算hash值
  3. 将计算出的hash值与(table.length - 1)进行&运算

compareComparables

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
static Class<?> comparableClassFor(Object x) {
    if (x instanceof Comparable) {
        Class<?> c; Type[] ts, as; Type t; ParameterizedType p;
        if ((c = x.getClass()) == String.class) // bypass checks
            return c;
        if ((ts = c.getGenericInterfaces()) != null) {
            for (int i = 0; i < ts.length; ++i) {
                if (((t = ts[i]) instanceof ParameterizedType) &&
                    ((p = (ParameterizedType)t).getRawType() ==
                     Comparable.class) &&
                    (as = p.getActualTypeArguments()) != null &&
                    as.length == 1 && as[0] == c) // type arg is c
                    return c;
            }
        }
    }
    return null;
}

如果x实现了Comparable接口就返回x的Class对象，否则返回null。

compareComparables

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的Class对象等于kc，就调用compareTo返回比较结果，否则返回0。

tableSizeFor

1
2
3
4
5
6
7
8
9
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;
}

用于找到大于等于cap的最小2的幂，如果cap就是2的幂则返回的还是这个数。

对这个方法解释的比较好的一篇博客。

构造函数

1
2
3
4
5
6
7
8
9
10
11
12
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);
}
  1. 先检查initialCapacity和loadFactor参数值是否正确。
  2. 给loadFactor（负载因子）和 threshold（扩容阈值）赋值，这里threshold调用了tableSizeFor保证了时2的幂，但是没有乘table.length是因为table没有在构造函数中初始化还是在put方法中初始化，同时在put方法中也会重新对threshold赋值。
1
2
3
public HashMap(int initialCapacity) {
       this(initialCapacity, DEFAULT_LOAD_FACTOR);
   }

这个方法就是调用了上面的方法，只不过loadFactor给了默认值0.75。

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

这个方法没有任何参数，代表initialCapacity和loadFactor都使用默认值，分别为16和0.75。

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

这个方法给loadFactor赋默认值0.75，然后调用putMapEntries方法将参数传进来的Map元素全部加入到table中。

putMapEntries会在下面的常用方法介绍。

常用方法

与红黑树相关（TreeNode）的方法会在后面单独介绍。

get

1
2
3
4
public V get(Object key) {
     Node<K,V> e;
     return (e = getNode(hash(key), key)) == null ? null : e.value;
 }

调用getNode方法传入key和key的hash值，如果为null直接返回null否则返回节点的value值。

getNode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
  	//table不为空并且table长度大于0，table的根据hash计算出索引位置不为空
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
      	//检查第一个节点的hash和key是否和传进来的相等，相等则直接返回第一个节点
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
      	//如果第一个节点的next不为空，向下遍历
        if ((e = first.next) != null) {
          	//如果是红黑树节点调用红黑树查找节点方法getTreeNode
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            //向下遍历链表，如果找到和传进来key和hash相等的节点直接返回
          	do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}
  1. 先检查table是否为空，长度是否大于0。
  2. 使用table.length - 1和hash值进行位与运算，得出在table上具体位置，将该索引位置的节点赋值给first节点，检查该索引位置是否为空。
  3. 检查first节点的hash值和key是否和入参的一样，如果一样则first为目标节点，直接返回first节点。
  4. 如果first下一节点不为空，先判断first节点是否是红黑树节点，是则调用getTreeNode查找节点，否则遍历普通链表节点查找。
  5. 如果为找到直接返回null。

put

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

调用putVal方法，参数的第一个布尔值：true代表如果找到节点不替换值，并返回老值，节点为null时还是会替换，false代表找到节点会用新值替换老值，并返回老值；第二个是给LinkedHashMap使用，这里不多介绍。

putVal

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
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或者长度为0就调用resize方法初始化table
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
  	//通过hash计算索引位置，如果table表该索引位置节点为空则新增一个节点放在该位置上
    if ((p = tab[i = (n - 1) & hash]) == null) //将索引位置头节点赋值给p
        tab[i] = newNode(hash, key, value, null);
    else { //table表该索引位置不为空
        Node<K,V> e; K k;
      	//判断p节点hash值和key值是否和传进来的hash值和key值相等
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p; //如果相等则p即为要查找的目标节点，赋值给e
      	//判断p是否为TreeNode节点，如果是则调用putTreeVal方法查找目标节点
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else { //走到这代表普通链表节点
            for (int binCount = 0; ; ++binCount) { //遍历此链表，binCount用于统计节点数
                //p.next为空不存在目标节点，则新增一个节点插入链表尾部
              	if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                  	//计算节点是否超过8个减1是因为从循环p节点的下一个节点开始的
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);//调用treeifBin方法将该链表转为红黑树
                    break;
                }
              	//e节点的hash值和key值都与传入的相等，则e即为目标节点，跳出循环
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e; //将p指向下一节点
            }
        }
      	//e不为空代表找到了目标节点，将该节点的value覆盖返回oldValue
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e); //用于LinkedHashMap
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold) //插入节点后超过阈值则进行扩容
        resize();
    afterNodeInsertion(evict); //用于LinkedHashMap
    return null;
}
  1. 检查table是否为空或者length等于0，如果是则调用resieze方法进行初始化。
  2. 通过hash值计算索引位置，将该索引位置的头节点赋值给p节点，如果该索引位置节点为空则使用传入的参数新增一个节点并放在该索引位置。
  3. 判断p节点的key和hash值是否跟传入的相等，如果相等，则p节点即为要查找的目标节点，将p节点赋值给e节点。
  4. 如果p节点不是目标节点，则判断p节点是否为TreeNode，如果是则调用putTreeVal方法查找目标节点。
  5. p为普通链表节点，则调用普通链表的方法进行查找，并定于变量binCount来统计链表的节点数。
  6. 如果p的next节点为空时，则代表找不到目标节点，则新增一个节点插入链表尾部，并检查链表节点数是否超过8个，如果超过则调用treeifyBin将链表转成红黑树。
  7. 如果遍历的e节点存在hash值和key值都与传入的相同，则e节点即为目标节点，跳出循环。
  8. 如果e节点不为空，则代表目标节点存在，使用传入的value覆盖该节点的value，并返回oldValue。
  9. 如果插入节点后节点数超过阈值，则调用resize方法进行扩容。

##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
final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    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; //设置阈值为Integer.MAX_VALUE
            return oldTab;					
        }
      	//老table容量*2小于最大容量并且老table容量大于等于默认容量16，则将新阈值设置为原来的2倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
  	//老表的容量为0, 老表的阈值大于0, 是因为初始容量被放入阈值
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr; //将新表的容量设置为老表的阈值
  	//老表的容量为0, 老表的阈值为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"})
  	//定义新表，容量为刚计算出的新容量
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; 
    table = newTab; //将新表赋值为当前表
    if (oldTab != null) { //老表不为空, 则需遍历将节点赋值给新表
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) { //将索引值为j的头节点赋值给e
                oldTab[j] = null; //将老表的节点设置为空，方便垃圾回收器回收
              	//如果e.next为空，代表只有一个节点
              	//通过hash计算出新表的索引位置，直接将该节点放在该位置上
                if (e.next == null) 
                    newTab[e.hash & (newCap - 1)] = e;
              	//如果e是红黑树节点就调用调用treeNode的hash分布
                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; //将e的下一个节点赋值给next
                      	//如果e的hash值与老表的容量进行与运算为0，则扩容后的位置跟老表的位置一样
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null) //代表该节点是第一个节点
                                loHead = e; //将loHead赋值为第一个节点
                            else
                                loTail.next = e; //否则将节点添加在loTail后面
                            loTail = e; //将loTail设置为新增节点
                        }
                    //如果e的hash值与老表的容量进行与运算为1，则新的位置为：老表的索引位置+oldCap
                        else {
                            if (hiTail == null) //如果hiTail为空，代表该节点是第一个节点
                                hiHead = e; //将hiHead赋值为第一个节点
                            else
                                hiTail.next = e; //否则将节点添加在hiTail后面
                            hiTail = e; //将hiTail设置新增节点
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
                        loTail.next = null; //最后一个节点的next设置为空
                        newTab[j] = loHead; //将原索引位置的节点设置为对应的头节点
                    }
                    if (hiTail != null) {
                        hiTail.next = null; //最后一个节点的next设置为空
                      	//将索引位置j+oldCap的节点设置为对应的头节点
                        newTab[j + oldCap] = hiHead; 
                    }
                }
            }
        }
    }
    return newTab;
}
  1. 如果老表的容量大于0，判断老表的容量是否超过最大容量值：如果超过则将阈值设置为Integer.MAX_VALUE,并直接返回老表（此时oldCap * 2比Integer.MAX_VALUE大，因此无法进行重新分布，只是单纯的将阈值扩容到最大）；如果老容量*2小于最大容量并且老容量大于等于默认容量16，就将新的阈值设置为老阈值的2倍。
  2. 如果老表的容量为0，老表的阈值大于0，这种情况是穿了容量的new方法创建的空表，将新表的阈值设置为老表的阈值（这种情况发生在新创建的HashMap第一次put时，该HashMap初始化的时候传了初始容量，由于HashMap并没有capacity变量来存放容量值，因此传进来的初始容量时存放在threshold变量上），因此此时来表threshold的值就是我们要创建的HashMap的capacity，所以将新表的容量设置为老表的阈值。
  3. 如果老表的容量为0，老表的阈值为0，这种情况是没有传容量的new方法创建的空表，将阈值和容量设置为默认值。
  4. 如果新表的阈值为空，则通过新的容量*负载因子获得阈值（这种情况时初始化的时候传了初始容量，跟第2点相同情况，或者初始容量设置的太小导致老表的容量没有超过16导致的）。
  5. 将当前阈值设置刚计算出来的新的阈值，定义新表，容量为刚计算出来的新容量，将当前的表设置为新定义的表。
  6. 如果老表不为空，则需遍历所有节点，将节点赋值给新表。
  7. 将老表上索引为j的头节点赋值给e，并将老表上索引为j的节点设置为空。
  8. 如果e的next节点为空，则代表老表的该位置只有1个节点，通过hash值计算新表的位置，直接将该节点放在新表的位置上。
  9. 如果e的next节点不为空，并且e为TreeNode，则调用split方法进行hash分布。
  10. 如果e的next节点不为空，并且e为普通的链表节点，则进行普通的hash分布。
  11. 如果e的hash值与老表的容量（为一串只有1个为2的二进制数，例如16位0000 0000 0001 0000）进行位与运算为0，则说明e节点扩容后的索引位置跟来表的索引位置一样，进行链表拼接操作；如果loTail为空，代表该节点为第一个节点，则将loHead赋值为该节点；否则将节点添加在loTail后面，并将loTail赋值为新增的节点。
  12. 如果e的hash值与老表的容量（为一串只有1个为2的二进制数，例如16位0000 0000 0001 0000）进行位与运算为1，则说明e节点扩容后的索引位置：老表的索引位置+oldCap，进行链表拼接操作；如果hiTail为空，代表该节点为第一个节点，则将hiHead赋值为该节点；否则将节点添加在hiTail后面，并将hiTail赋值为新增的节点。
  13. 老表节点重新hash分布在新表结束后，如果loTail不为空（说明老表的数据有分布到新表上原索引位置的节点），则将最后一个节点的next设为空，并将新表上原索引位置的节点设置为对应的头节点；如果hiTail不为空（说明老表的数据有分布到新表上原索引+oldCap位置的节点），则将最后一个节点的next设为空，并将新表上索引位置为原索引+oldCap的节点设置为对应的头节点。
  14. 返回新表。

putAll

1
2
3
public void putAll(Map<? extends K, ? extends V> m) {
      putMapEntries(m, true);
  }

调用putMapEntries方法

putMapEntries

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
    int s = m.size();
    if (s > 0) {
      	//如果还未添加过任何元素，算出传进来Map的容量长度，如果该长度大于阈值，就根据该长度重新计算阈值
        if (table == null) { // pre-size
            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) //如果传进来的Map size大于扩容阈值，就调用扩容方法resize
            resize();
      	//循环传进来的Map，调用putVal方法将元素一一添加进table
        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);
        }
    }
}

remove

1
2
3
4
5
public V remove(Object key) {
    Node<K,V> e;
    return (e = removeNode(hash(key), key, null, false, true)) == null ?
        null : e.value;
}

调用removeNode方法传入key和key的hash值，如果为null直接返回null否则返回节点的value值。

removeNode

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 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通过hash计算索引位置的头节点不为空
        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;
          	//判断头节点是否就是要删除的节点
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                node = p;
          	//如果第一个节点的next不为空，向下遍历
            else if ((e = p.next) != null) {
              	//判断是否是红黑树节点，如果是调用getTreeNode寻找节点
                if (p instanceof TreeNode)
                    node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
                else { //普通链表节点
                  	//循环普通连接节点，寻找hash和key与传参相等的节点
                    do {
                        if (e.hash == hash &&
                            ((k = e.key) == key ||
                             (key != null && key.equals(k)))) {
                            node = e;
                            break;
                        }
                        p = e;
                    } while ((e = e.next) != null);
                }
            }
          	//寻找到目标节点
            if (node != null && (!matchValue || (v = node.value) == value ||
                                 (value != null && value.equals(v)))) {
              	//判断节点是否是红黑树节点，如果是调用removeTreeNode方法删除节点
                if (node instanceof TreeNode)
                    ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
              	//判断头节点是否就是寻找的节点，如果是，直接将node节点的next节点放在索引位置上
                else if (node == p)
                    tab[index] = node.next;
                else //走到这代表是普通链表节点，直接将头节点的next指针指向要删除节点的下一节点
                    p.next = node.next;
                ++modCount;
                --size;
                afterNodeRemoval(node); //用于LinkedHashMap
                return node;
            }
        }
        return null;
    }
  1. 判断table不为空，table长度大于0，table通过hash计算索引位置的头节点不为空，否则直接返回null。
  2. 判断头节点是否就是要删除的节点，如果是将p节点赋值给node节点。
  3. 头节点不是要要删除节点，判断p节点是否是TreeNode节点，如果是调用getTreeNode方法寻找对应节点。
  4. p为普通链表节点，则调用普通链表的方法遍历进行查找对应节点。
  5. 如果寻找到目标节点，判断是否是TreeNode节点，如果是调用removeTreeNode方法删除节点；不是TreeNode节点，判断要寻找的节点是否是头节点，如果是直接将p节点的next节点放在索引位置上；否则为普通链表节点，直接将p节点的next指针指向要删除节点的下一节点。

红黑树（TreeNode）相关方法

getTreeNode

1
2
3
final TreeNode<K,V> getTreeNode(int h, Object k) {
  return ((parent != null) ? root() : this).find(h, k, null);
}

使用根节点调用find方法。

find

  • 从调用此方法的节点开始查找，通过hash值和key找到对应的节点。

  • 此处是红黑树的遍历，红黑树是特殊的自平衡二叉查找树。

  • 平衡二叉数的特点：左节点 < 根节点 < 右节点。

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
final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
				//将p节点赋值为调用此方法的节点，即为红黑树根节点
         TreeNode<K,V> p = this;
				//从p节点开始向下遍历
         do {
             int ph, dir; K pk;
             TreeNode<K,V> pl = p.left, pr = p.right, q;
           	//如果传入的hash值小于p节点的hash值，则往p节点的左边遍历
             if ((ph = p.hash) > h)
                 p = pl;
           	//如果传入的hash值大于p节点的hash值，则往p节点的右边遍历
             else if (ph < h)
                 p = pr;
           	//如果传入的hash值和key之等于p节点的hash值和key值，则p节点为目标节点，返回p节点
             else if ((pk = p.key) == k || (k != null && k.equals(pk)))
                 return p;
           	//如果p节点的左节点为空，则向右遍历
             else if (pl == null)
                 p = pr;
           	//如果p节点的右节点为空，则向左遍历
             else if (pr == null)
                 p = pl;
           	//将p节点与k进行比较
             else if ((kc != null ||
                       //kc不为空代表k实现了Comparable
                       (kc = comparableClassFor(k)) != null) && 
                      	//k < pk则dir < 0，k > pk则dir > 0
                      (dir = compareComparables(kc, k, pk)) != 0)
               	//dir 小于0向左遍历，否则向右遍历
                 p = (dir < 0) ? pl : pr;
           	//代码走到此处，代表key所属类没有实现Comparable，直接指向p的右边遍历
             else if ((q = pr.find(h, k, kc)) != null)
                 return q;
           	//代码走到此处代表 pr.find(h, k, kc) 为空，因此直接向左遍历
             else
                 p = pl;
         } while (p != null);
         return null;
     }
  1. 将p节点赋值为调用此方法的节点，即为红黑树根节点。
  2. 从p节点开始向下遍历。
  3. 如果传入的hash值小于p节点的hash值，则往p节点的右边遍历。
  4. 如果传入的hash值大于p节点的hash值，则往p节点的右边遍历。
  5. 如果传入的hash和key值等于p节点的hash值和key值，则p节点为目标节点，返回p节点。
  6. 如果p节点的左节点为空，则向右遍历。
  7. 如果p节点的右节点为空，则向左遍历。
  8. 将p节点与k进行比较。如果传入的key所属的类实现了Comparable接口，则将k跟p节点的key进行比较（kc实现了Comparable接口，因此通过kc的比较方法进行比较），并将比较结果赋值给dir，如果dir < 0则代表k < pk，则向p节点的左边遍历（pl）；否则，向p节点的右边遍历（pr）。
  9. key所属类没有实现Comparable接口，因此直接向右遍历。
  10. pr.find(h, k, kc)为空，因此直接向左遍历。

putTreeVal

红黑树的put操作，红黑树插入会同时维护原来的链表属性，即原来的next属性。

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
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;
				//将根节点赋值给p节点，开始进行查找
         for (TreeNode<K,V> p = root;;) {
             int dir, ph; K pk;
           	//传入的hash值小于p节点的hash值，向p的左边查找树
             if ((ph = p.hash) > h)
                 dir = -1;
           	//传入的hash值大于p节点的hash值，向p的右边查找树
             else if (ph < h)
                 dir = 1;
           	//如果传入的hash值和key值等于p节点的hash值和key值，则p节点为目标节点，返回p节点
             else if ((pk = p.key) == k || (k != null && k.equals(pk)))
                 return p;
           	//如果所属的类没有实现Comparable接口 或者 k和p节点的key相等
             else if ((kc == null &&
                       (kc = comparableClassFor(k)) == null) ||
                      (dir = compareComparables(kc, k, pk)) == 0) {
               	//第一次符合条件，从p节点的左节点和右节点分别调用find方法进行查找，如果找到就返回
                 if (!searched) {
                     TreeNode<K,V> q, ch;
                     searched = true;
                     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;
                 }
               	//使用定义的一套规则来比较k和p节点的key的大小，用来决定向左还是向右查找
                 dir = tieBreakOrder(k, pk);//dir<0则代表k<pk，则向p左边查找；反之亦然
             }
					//xp赋值为x的父节点，中间变量，用于下面给x的父节点赋值
             TreeNode<K,V> xp = p;
           	//dir<=0则向p左边查找，否则向p右边查找，如果为null，则代表该位置即为x的目标位置
             if ((p = (dir <= 0) ? p.left : p.right) == null) {
               	//走进来代表以及找到x的位置，只需将x放到该位置即可
                 Node<K,V> xpn = xp.next; 
               	//创建新的节点，其中x的next节点为xpn，即将x节点插入xp与xpn之间
                 TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
               	//调整x、xp、xpn之间的属性关系
                 if (dir <= 0)
                     xp.left = x; //代表x节点为xp的左节点
                 else
                     xp.right = x; //代表x节点为xp的右节点
                 xp.next = x; //将xp的next节点设置为x
                 x.parent = x.prev = xp; //将x的parent和prev节点设置为xp
               	//如果xpn不为空，则将xpn的prev节点设置为x节点，与上文的x节点的next节点对应
                 if (xpn != null) 
                     ((TreeNode<K,V>)xpn).prev = x;
               	//进行红黑树的插入平衡调整
                 moveRootToFront(tab, balanceInsertion(root, x));
                 return null;
             }
         }
     }
  1. 查找根节点，索引位置的头节点不一定为红黑树的根节点。
  2. 将根节点赋值给p节点，开始进行查找。
  3. 如果传入的hash值小于p节点的hash值，将dir赋值为-1，代表向p的左边查找树。
  4. 如果传入的hash值大于p节点的hash值，将dir赋值为1，代表向p的右边查找树。
  5. 如果传入的hash值和key值等于p节点的hash值和key值，则p节点即为目标节点，返回p节点。
  6. 如果k所属的类型没有实现Comparable接口 或者 k和p节点的key相等；如果searched为false，从p节点的左节点和右节点分别调用find方法进行查找，如果查找到目标节点则返回；否则使用定义的一套规则来比较k和p节点的key的大小，用来决定向左还是向右查找。
  7. dir < 0则向p左边查找，否则向p右边查找，如果为null，则代表该位置即为x的目标位置。
  8. 创建新的节点，其中x的next节点为xpn，即将x节点插入xp与xpn之间。
  9. 调整x、xp、xpn之间的属性关系。
  10. 进行红黑树的插入平衡调整。

tieBreakOrder

1
2
3
4
5
6
7
8
9
static int tieBreakOrder(Object a, Object b) {
    int d;
    if (a == null || b == null ||
        (d = a.getClass().getName().
         compareTo(b.getClass().getName())) == 0)
        d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
             -1 : 1);
    return d;
}

用于不可比较或者hashCode相同时进行比较的方法，只是一个一直的插入规则，用来维护定位的等价性。

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
final void treeifyBin(Node<K,V>[] tab, int hash) {
     int n, index; Node<K,V> e;
		//如果table为空或者table的长度小于64，调用resize方法进行扩容
     if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
         resize();
		//根据hash值计算索引值，将该索引位置的节点赋值给e，从e开始遍历该索引位置的链表
     else if ((e = tab[index = (n - 1) & hash]) != null) {
         TreeNode<K,V> hd = null, tl = null;
         do {
           	//将链表节点转红黑树节点
             TreeNode<K,V> p = replacementTreeNode(e, null);
           	//如果是第一次遍历，将头节点赋值给hd
             if (tl == null) //t1为空代表为第一次循环
                 hd = p;
             else { //如果不是第一次遍历，则处理当前节点的prev属性和上一节点的next属性
                 p.prev = tl; //当前节点的prev属性设为上一节点
                 tl.next = p; //上一节点的next属性设置为当前节点
             }
 //将p节点赋值给t1，用于在下一次循环中作为上一节点进行一些链表的关联操作(p.prev = t1 和 t1.next = p)
             tl = p;
         } while ((e = e.next) != null);
   //将table该索引位置赋值为新转的TreeNode头节点，如果该节点不为空，则以头节点(hd)为根节点，构建红黑树
         if ((tab[index] = hd) != null)
             hd.treeify(tab);
     }
 }
  1. 如果table为空或者table的长度小于64，调用resize方法进行扩容。
  2. 根据hash值j计算索引值，将该索引值位置的节点赋值给e，从e开始遍历该索引位置的链表。
  3. 将链表节点转红黑树节点。
  4. 如果是第一次遍历，将头节点赋值给hd。
  5. 如果不是第一次遍历，则处理当前节点的prev属性和上一节点的next属性。
  6. 将p节点赋值给t1，用于在下一次循环中作为上一节点进行一些链表的关联操作(p.prev = t1 和 t1.next = p)。
  7. 将table该索引位置赋值新转的TreeNode的头节点，如果该节点不为空，则以头节点(hd)为根节点，构建红黑树。

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
final void treeify(Node<K,V>[] tab) {
         TreeNode<K,V> root = null;
				//将调用此方法的节点赋值给x，以x作为起点，开始进行遍历
         for (TreeNode<K,V> x = this, next; x != null; x = next) {
             next = (TreeNode<K,V>)x.next;//next赋值为x的下个节点
             x.left = x.right = null;//将x的左右节点设置为空
             //如果还没有根节点，则将x设置为根节点
           	if (root == null) {
                 x.parent = null; //根节点没有父节点
                 x.red = false; //根节点必须为黑色
                 root = x; //将x设置为根节点
             }
             else {
                 K k = x.key; //k赋值为x的key
                 int h = x.hash; //h赋值为x的hash值
                 Class<?> kc = null;
               	//如果当前节点x不是根节点，则从根节点开始查找属于该节点的位置
                 for (TreeNode<K,V> p = root;;) {
                     int dir, ph;
                     K pk = p.key;
                   	//如果x节点的hash值小于p节点的hash值，则将dir赋值为-1，代表向p的左边查找
                     if ((ph = p.hash) > h)
                         dir = -1;
                   	//如果x节点的hash值大于p节点的hash值，则将dir赋值为1，代表向p的右边查找
                     else if (ph < h)
                         dir = 1;
                   	//走到这代表x的hash值和p的hash值相等，则比较key值
                     else if ((kc == null &&
                               //如果k没有实现Comparable接口 或者 x节点的key和p节点的key相等
                               (kc = comparableClassFor(k)) == null) ||
                              (dir = compareComparables(kc, k, pk)) == 0)
                       	//使用定义的一套规则来比较x节点和p节点的大小，用来决定向左还是向右
                         dir = tieBreakOrder(k, pk);
									//xp赋值为x的父节点，中间变量用于下面给x的父节点赋值
                     TreeNode<K,V> xp = p;
                   	//dir<=0则向p左边查找，否则向p右边查找，如果为null，则代表该位置即为x的目标位置
                     if ((p = (dir <= 0) ? p.left : p.right) == null) {
                       	//x和xp节点的属性设置
                         x.parent = xp; //x的父节点即为最后一次遍历的p节点
                         if (dir <= 0) //如果是dir < 0，则代表x节点为父节点的左节点
                             xp.left = x;
                         else //如果是dir > 0，则代表x节点为父节点的右节点
                             xp.right = x;
                       	//进行红黑树的插入平衡
                         root = balanceInsertion(root, x);
                         break;
                     }
                 }
             }
         }
				//如果root节点不再table索引位置的头节点，则将其调整为头节点
         moveRootToFront(tab, root);
     }
  1. 将调用此方法的节点赋值给x，以x作为起点，开始进行遍历。
  2. 如果还没有根节点，则将x设置为根节点。
  3. 如果当前节点x不是根节点，则从根节点开始查找属于该节点的位置。
  4. 如果x节点的hash值小于p节点的hash值，则将dir赋值为-1，代表向p的左边查找。
  5. 如果x节点的hash值大于p节点的hash值，则将dir赋值为1，代表向p的右边查找。
  6. 走到这代表x的hash值和p的hash值相等，则比较key值。
  7. dir <= 0则向p左边查找，否则向p右边查找，如果为null，则代表该位置即为x的目标位置。
  8. x和xp节点的属性设置。
  9. 进行红黑树的插入平衡（通过左旋、右旋和改变节点颜色来保证当前数符合红黑树要求）。
  10. 如果root节点不再table索引位置的头节点，则将其调整为头节点。

moveRootToFront

将root放到头节点的位置，如果当前索引位置的头节点不是root节点，则将root的上一节点和下一节点进行关联，将root放到头节点的位置，原头节点放在root的next节点上。

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
static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
         int n;
				//检查root是否为空，table是否为空，table的length是否大于0
         if (root != null && tab != null && (n = tab.length) > 0) {
           	//计算root节点的索引位置
             int index = (n - 1) & root.hash;
             TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
           	//如果该索引位置的头节点不是root节点，则该索引位置的头节点替换为root节点
             if (root != first) {
                 Node<K,V> rn;
               	//将该索引位置的头节点赋值为root节点
                 tab[index] = root;
                 TreeNode<K,V> rp = root.prev; //root节点的上一个节点
           //如果root节点的next节点不为空，则将root节点的next节点的prev属性设置为root节点的prev节点
                 if ((rn = root.next) != null)
                     ((TreeNode<K,V>)rn).prev = rp;
           //如果root节点的next节点不为空，则将root节点的prev节点的next属性设置为root节点的next节点
                 if (rp != null)
                     rp.next = rn;
                 if (first != null)
                     first.prev = root;
               	//将root节点的next属性设置为原头节点
                 root.next = first;
               	//root此时已经被放到该位置头节点位置，因此将prev属性设为空
                 root.prev = null;
             }
           	//检查树是否正常
             assert checkInvariants(root);
         }
     }
  1. 检查root是否为空，table是否为空，table的length是否大于0。
  2. 计算root节点的索引位置。
  3. 如果该索引位置的头节点不是root节点，则该索引位置的头节点替换为root节点。
  4. 检查树是否正常。

checkInvariants

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
static <K,V> boolean checkInvariants(TreeNode<K,V> t) {//一些基本的检查
    TreeNode<K,V> tp = t.parent, tl = t.left, tr = t.right,
        tb = t.prev, tn = (TreeNode<K,V>)t.next;
    if (tb != null && tb.next != t)
        return false;
    if (tn != null && tn.prev != t)
        return false;
    if (tp != null && t != tp.left && t != tp.right)
        return false;
    if (tl != null && (tl.parent != t || tl.hash > t.hash))
        return false;
    if (tr != null && (tr.parent != t || tr.hash < t.hash))
        return false;
  	//如果当前节点为红色，则该节点的左右节点都不能为红色
    if (t.red && tl != null && tl.red && tr != null && tr.red)
        return false;
    if (tl != null && !checkInvariants(tl))
        return false;
    if (tr != null && !checkInvariants(tr))
        return false;
    return true;
}

将传入的节点作为根节点，遍历所有节点，检查节点的合法性，主要是保证树符合红黑树的规则。

split

扩容后，红黑树的hash分布，只可能存在于两个位置：原索引位置、原索引位置 + oldCap。

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
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
        TreeNode<K,V> b = this;//拿到调用此方法的节点
        // Relink into lo and hi lists, preserving order
        TreeNode<K,V> loHead = null, loTail = null;//存储索引位置为:“原索引位置”的节点
        TreeNode<K,V> hiHead = null, hiTail = null;//存储索引位置为:“原索引位置+oldCap”的节点
        int lc = 0, hc = 0;
			//以调用此方法的节点开始，遍历整个红黑树节点
        for (TreeNode<K,V> e = b, next; e != null; e = next) {//从b节点开始遍历
            next = (TreeNode<K,V>)e.next;//next赋值为e的下个节点
            e.next = null;//同时将老表的节点设置为空，以便垃圾收集器回收
          	//如果e的hash值与老表的容量进行与运算为0，则扩容后的索引位置跟老表的索引位置一样
            if ((e.hash & bit) == 0) {
                if ((e.prev = loTail) == null)//如果loTail为空，代表该该节点为第一个节点
                    loHead = e;//则将loHead赋值为第一个节点
                else
                    loTail.next = e;//否则将节点添加在loTail后面
                loTail = e;//并将loTail赋值为新增的节点
                ++lc; //统计原索引位置的节点个数
            }
          	//如果e的hash值与老表的容量进行与运算为1，则扩容后的索引位置为：老表的索引位置 + oldCap
            else {
                if ((e.prev = hiTail) == null)//如果hiHead为空，代表该节点为第一个节点
                    hiHead = e; //则将hiHead赋值为第一个节点
                else
                    hiTail.next = e; //否则将节点添加在hiTail后面
                hiTail = e; //并将hiTail赋值为新增的节点
                ++hc; //统计索引位置为原索引 + oldCap的节点个数
            }
        }
		//如果原索引位置的节点不为空
        if (loHead != null) {
            if (lc <= UNTREEIFY_THRESHOLD) //如果节点个数<=6个则将红黑树转为链表结构
                tab[index] = loHead.untreeify(map);
            else {
                tab[index] = loHead; //将原索引位置的节点设置为对应的头节点
              	//如果hiHead不为空，则代表原来的红黑树已经被改变，需要重新构建新的红黑树
              	//老表的红黑树由于节点被分到两个位置
                if (hiHead != null) // (else is already treeified)
                  	//以loHead为根节点，构建新的红黑树
                    loHead.treeify(tab);
            }
        }
			//如果索引位置为原索引+oldCap的节点不为空
        if (hiHead != null) {
          	//如果节点个数<=6个，则将红黑树转为链表结构
            if (hc <= UNTREEIFY_THRESHOLD)
                tab[index + bit] = hiHead.untreeify(map);
            else {
              	//将索引位置为原索引+oldCap的节点设置为对应的头节点
                tab[index + bit] = hiHead;
              	//loHead不为空则代表原来的红黑树已经被改变，需要重新构建新的红黑树
                if (loHead != null)
                  	//以hiHead为根节点，构建新的红黑树
                    hiHead.treeify(tab);
            }
        }
    }
  1. 以调用此方法的节点开始，遍历整个红黑树节点。
  2. 如果e的hash值与老表的容量进行与运算为0，则扩容后的索引位置跟老表的索引位置一样。
  3. 如果e的hash值与老表的容量进行与运算为1，则扩容后的索引位置为：老表的索引位置 + oldCap。
  4. 如果原索引位置的节点不为空，如果节点个数小于等于6则将红黑树转为链表结构，否则将原索引位置的节点设置为对应的头节点，如果hiHead不为空，则代表原来的红黑树已经被改变，需要重新构建新的红黑树。
  5. 如果索引位置为原索引+oldCap的节点不为空，如果节点个数小于等于6则将红黑树转为链表结构，否则将原索引位置+ oldCap的节点设置为对应的头节点，如果hiHead不为空，则代表原来的红黑树已经被改变，需要重新构建新的红黑树。

untreeify

将红黑树节点转为链表节点，当节点<=6时会被触发。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
final Node<K,V> untreeify(HashMap<K,V> map) {
    Node<K,V> hd = null, tl = null; //hd 头节点，t1 尾节点
  	//从调用该方法节点，即链表的头节点开始遍历，将所有节点转换为链表节点
    for (Node<K,V> q = this; q != null; q = q.next) { 
        Node<K,V> p = map.replacementNode(q, null);
      	//如果t1为null，代表是第一个节点，将hd赋值为该节点
        if (tl == null)
            hd = p;
        else //否则将尾节点赋值给p
            tl.next = p;
        tl = p; //每次将尾节点指向当前节点，即为节点
    }
  	//返回转换后的链表的头节点 
    return hd;
}
  1. 从调用该方法节点，即链表的头节点开始遍历，将所有节点转换为链表节点。
  2. 调用replacementNode方法构建链表节点。
  3. 如果t1为null，代表是第一个节点，将hd赋值为该节点，否则否则将尾节点赋值给p。
  4. 每次将尾节点指向当前节点，即为节点。
  5. 返回转换后的链表的头节点 。

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
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
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
  final void removeTreeNode(HashMap<K,V> map, Node<K,V>[] tab,
                            boolean movable) {
    	//------链表的处理start-------
      int n;
    	//table为空或长度为0直接返回
      if (tab == null || (n = tab.length) == 0)
          return;
    	//根据hash计算出索引的位置
      int index = (n - 1) & hash;
    	//将索引位置的头节点赋值给first和root
      TreeNode<K,V> first = (TreeNode<K,V>)tab[index], root = first, rl;
    	//该方法将要被移除的node(TreeNode)调用，因此此方法的this为要被移除node节点
    	//将node的next节点赋值给succ节点，prev节点赋值给pred节点
      TreeNode<K,V> succ = (TreeNode<K,V>)next, pred = prev;
    	//如果pred节点为空，则代表要被移除的node节点为头节点，将table索引位置的值和first节点的值赋值为succ节点（node的next节点）即可
      if (pred == null)
          tab[index] = first = succ;
      else
        	//否则将pred节点的next属性设置为succ节点（node的next节点）
          pred.next = succ;
    	//如果succ节点不为空，则将succ的prev节点设置为pred，与前面对应
      if (succ != null)
          succ.prev = pred;
    	//如果进行到此first节点为空，则代表该索引位置已经没有节点则直接返回
      if (first == null)
          return;
    	//如果root的父节点不为空，则将root赋值为根节点
      if (root.parent != null)
          root = root.root();
    	//通过root节点来判断此红黑树是否太小，如果是则调用untreeify方法转为链表节点并返回
    	//转链表后就无需再进行下面的红黑树处理
      if (root == null
          || (movable
              && (root.right == null
                  || (rl = root.left) == null
                  || rl.left == null))) {
          tab[index] = first.untreeify(map);  // too small
          return;
      }
    	//-----链表的处理end-------
    	//-----以下代码为红黑树处理--------
    	//将p赋值为要被移除的node节点，p1赋值为p的左节点，pr赋值为p的右节点
      TreeNode<K,V> p = this, pl = left, pr = right, replacement;
    	//如果p的左节点和右节点都不为空时
      if (pl != null && pr != null) {
        	//将s节点赋值为p的右节点
          TreeNode<K,V> s = pr, sl;
        	//向左一直查找，跳出循环时，s为没有左节点的节点
          while ((sl = s.left) != null) // find successor
              s = sl;
        	//交换p节点和s节点的颜色
          boolean c = s.red; s.red = p.red; p.red = c; // swap colors
          TreeNode<K,V> sr = s.right; //s的右节点
          TreeNode<K,V> pp = p.parent; //p的父节点
        	//---第一次调整和第二次调整：将p节点和s节点进行为位置调换---
        	//第一次调整
        	//如果p节点的右节点即为s节点，则将p的父节点赋值为s，将s的右节点赋值为p
          if (s == pr) { // p was s's direct parent
              p.parent = s;
              s.right = p;
          }
          else {
            	//将sp赋值为s的父节点
              TreeNode<K,V> sp = s.parent;
            	//将p的父节点赋值为sp
              if ((p.parent = sp) != null) {
                	//如果s节点为sp的左节点，则将sp的左节点赋值为p节点
                  if (s == sp.left)
                      sp.left = p;
                	//否则s节点为sp的右节点，则将sp的右节点赋值为p节点
                  else
                      sp.right = p;
              }
            	//s的右节点赋值为p节点的右节点
              if ((s.right = pr) != null)
                	//如果pr不为空，则将pr的父节点赋值为s
                  pr.parent = s;
          }
        	//第二次调整
        	//将p的左节点赋值为空，pl已经保存了该节点
          p.left = null;
        	//将p节点的右节点赋值为sr，如果sr不为空，则将sr的父节点赋值为p节点
          if ((p.right = sr) != null)
              sr.parent = p;
        	//将s节点的左节点赋值为pl，如果pl不为空，则将pl的父节点赋值为s节点
          if ((s.left = pl) != null)
              pl.parent = s;
        	//将s的父节点赋值为p的父节点pp
        	//如果pp为空，则p节点为root节点，交换后称为新的root节点
          if ((s.parent = pp) == null)
              root = s;
        	//如果p不为root节点，并且p是pp得右节点，则将pp的左节点赋值为s节点
          else if (p == pp.left)
              pp.left = s;
        	//如果p不为root节点，并且p是pp的右节点，则将pp的右节点赋值为s节点
          else
              pp.right = s;
        	//寻找replacement节点，用来替换掉p节点
        	//如果sr不为空，则replacement节点为sr，因为s没有左节点，所以使用s的右节点来替换p的位置
          if (sr != null)
              replacement = sr;
          else
              replacement = p;
      }
    	//如果p的右节点不为空，有节点为空，replacement节点为p的左节点
      else if (pl != null)
          replacement = pl;
    	//如果p的右节点不为空，左节点为空，replacement节点为p的右节点
      else if (pr != null)
          replacement = pr;
    	//如果p的左右节点都为空，即p为叶子节点，replacement节点为p节点本身
      else
          replacement = p;
    	//使用replacement节点替换掉p节点的位置，将p节点移除
      if (replacement != p) { //如果p节点不是叶子节点
        	//将p节点的父节点赋值给replacement节点的父节点，同时赋值给pp节点
          TreeNode<K,V> pp = replacement.parent = p.parent;
        	//如果p没有父节点，即p为root节点，则将root节点赋值为replacement节点即可
          if (pp == null)
              root = replacement;
        	//如果p不是root节点，即p为root节点，则将pp的左节点赋值为替换节点replacement
          else if (p == pp.left)
              pp.left = replacement;
        	//如果p不是root节点，并且p为pp的右节点，则将pp的右节点赋值为替换节点replacement
          else
              pp.right = replacement;
        	//p节点的位置已经被完整的替换为replacement，将P节点清空，以便垃圾收集器回收
          p.left = p.right = p.parent = null;
      }
//如果p节点不为红色则进行红黑树删除平衡调整
    	//如果删除的节点是红色则不会破坏红黑树的平衡无需调整
      TreeNode<K,V> r = p.red ? root : balanceDeletion(root, replacement);
//如果p节点为叶子节点，则简单的将p节点去除即可
      if (replacement == p) {  // detach
          TreeNode<K,V> pp = p.parent;
        	//将p的parent属性设置为空
          p.parent = null;
          if (pp != null) {
            	//如果p节点为父节点的左节点，则将父节点的左节点赋值为空
              if (p == pp.left)
                  pp.left = null;
            	//如果p节点为父节点的右节点，则将父节点的右节点赋值为空
              else if (p == pp.right)
                  pp.right = null;
          }
      }
      if (movable)
        	//将root节点移到索引位置的头节点
          moveRootToFront(tab, r);
  }

原文作者：leisurexi

原文链接：https://github.com/leisurexi/category/2019/08/15/集合/HashMap.html

发表日期：August 15th 2019, 10:06:00 am

更新日期：January 18th 2020, 4:37:01 pm

版权声明：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
  1. 1. 基本属性
  2. 2. 字段
  3. 3. 静态工具方法
    1. 3.1. hash
    2. 3.2. compareComparables
    3. 3.3. compareComparables
    4. 3.4. tableSizeFor
  4. 4. 构造函数
  5. 5. 常用方法
    1. 5.1. get
    2. 5.2. getNode
    3. 5.3. put
    4. 5.4. putVal
    5. 5.5. putAll
    6. 5.6. putMapEntries
    7. 5.7. remove
    8. 5.8. removeNode
    9. 5.9. 红黑树（TreeNode）相关方法
    10. 5.10. getTreeNode
    11. 5.11. find
    12. 5.12. putTreeVal
    13. 5.13. tieBreakOrder
    14. 5.14. treeifyBin
    15. 5.15. treeify
    16. 5.16. moveRootToFront
    17. 5.17. checkInvariants
    18. 5.18. split
    19. 5.19. untreeify
    20. 5.20. remove
Total : 26
2020
2019
CentOS 7 JVM 设计模式 Zookeeper Kafka MySQL RabbitMQ 并发 Nacos Spring IoC 集合 ELK Redis
CentOS-7 JVM 设计模式 CentOS-7/Zookeeper MySQL RabbitMQ 并发 CentOS-7/Zookeeper/Kafka CentOS-7/MySQL Spring-IoC CentOS-7/MySQL/Nacos 集合 ELK Redis