一步一步往前走

0%

数据结构与算法之开山篇：hashmap数据结构及源码分析

发表于 更新于 分类于 ，

​ 本篇是数据结构与算法系列博客的开山之篇，想写这个系列博客很久了，一直没想好该用什么方式来展开讲，最近也看了一些相关类的书，如：《算法图解》，《我的第一本算法书》，《大话数据结构》(还未看完)，感触挺多的，老师们都有一套自己的理解，讲的通俗易懂。但是怎么才能灵活应用这些数据结构，单独看某一类数据结构都懂，一到实际应用或者自己写一个综合的数据结构的时候就蒙圈。怎么才能摆脱这种尴尬，思考了很多，唯有深入专研,探究其奥秘，方能得心应手。

​ 这一篇将从数据结构的角度来分析hashmap,文中涉及的源码较多，所以会一起将源码一起梳理。

HashMap数据结构分析

HashMap中使用的数据结构

在hashmap中，抛开一些方法的类外，使用到了一下数据结构

1.Node.class ：

单项链表结构，存放hashmap中的数据。

1
2
3
4
5
6
static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
 }

2.TreeNode.class：

红黑树结构，存放hashmap中的数据，其实时Node的一个子类。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
   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;
   }
// LinkedHashMap.Entry<K,V> 结构
   static class Entry<K,V> extends HashMap.Node<K,V> {
       Entry<K,V> before, after;
       Entry(int hash, K key, V value, Node<K,V> next) {
           super(hash, key, value, next);
       }
   }

3.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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
/* ---------------- 字段中的默认值 -------------- */
/**
    * The default initial capacity - MUST be a power of two.
    * hashmap默认的初始化大小： 2的4次方，即16，
    */
   static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 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.
    * hashmap最大容量：2的4次方
    */
   static final int MAXIMUM_CAPACITY = 1 << 30;

   /**
    * The load factor used when none specified in constructor.
    * hashmap默认的负载因子，默认0.75，即达到总容量的75%时，需要扩容
    */
   static final float DEFAULT_LOAD_FACTOR = 0.75f;

   /**
    * 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.
    * 转化树形结构的阈值，默认8，即当某个链表上的节点长度大于8时，将这
    * 个链表转化为红黑树
    */
   static final int TREEIFY_THRESHOLD = 8;

   /**
    * 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.
    * 从树形结构转化为单链表结构的阈值，默认6
    */
   static final int UNTREEIFY_THRESHOLD = 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.
    * 对字段TREEIFY_THRESHOLD的一个补充，转化为红黑树的最小hashmap容量，
    * 如果某个链表的节点长度>8,但是总容量没达到64，hashmap会扩容，而不是
    * 直接转化为红黑树。（自定义该值时，至少应为4 * TREEIFY_THRESHOLD以
    * 避免在扩容还是转化为红黑树时产生冲突）
    */
   static final int MIN_TREEIFY_CAPACITY = 64;
  /* ---------------- Fields -------------- */

   /**
    * 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;

   /**
    * Holds cached entrySet(). Note that AbstractMap fields are used
    * for keySet() and values().
    * 具体的几点数据集合，
    */
   transient Set<Map.Entry<K,V>> entrySet;

   /**
    * The number of key-value mappings contained in this map.
    * hashmap总节点的个数，即容量
    */
   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).
    * 记录hashmap被修改的次数，包括rehash,添加数据等，在遍历数据时可以起到快速
    * 失败的作用
    */
   transient int modCount;

   /**
    * The next size value at which to resize (capacity * load factor).
    * 下一次扩容的阈值，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;

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

4.继承 AbstractMap<K,V>的字段

1
2
3
4
5
6
7
8
/**
 * key的集合缓冲
 */
transient Set<K>  keySet;
/**
 * value的集合缓冲
 */
transient Collection<V> values;

可能有人会问，为什么要在字段前加 transient， 这个其实只是想在对象序列化的时候不包含这个字段。

从上面的分析可以知道hashmap中使用了数组，单链表，二叉树的结构。其他字段都是为了统计或者处理不同结构转换的阈值。如图：

1

HashMap怎么运用这些数据结构

HashMap是怎么应用这些结构呢，让我们从源码的角度来分析。

1.构造方法

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
//无参构造，只设置默认负载因子 
public HashMap() {
   this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
//有参构造，自定义初始化容量，使用默认的负载因子
public HashMap(int initialCapacity) {
   this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//有参构造：设置初始化容量，负载因子，计算下一次扩容的大小
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);
}
//使用默认的负载因子，初始化hashmap
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

从上面构造函数上看不出来是如何使用这些数据结构的，我们再来看看添加方法

2.添加方法

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

/**
 * Implements Map.put and related methods
 *
 * @param hash hash for key
 * @param key the key
 * @param value the value to put
 * @param onlyIfAbsent if true, don't change existing value
 * @param evict if false, the table is in creation mode.
 * @return previous value, or null if none
 */
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; 
    int n, i;
    // 1.table如果是空数组，走扩容resize()逻辑
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 2.如果找到的链表头结点为null,直接新建一个next为null的节点，用(n - 1) & hash找到对应的链表头
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    /**
     * 3.走到这里，代表hashmap不为空，对应的链表也不为空，就涉及到在节点上添加数据，但是
     * 添加数据又不确认是链表结构还是红黑树结构，所以这里还有分化
     */
    else {
        Node<K,V> e; K k;
        // 3.1头结点就是要找的位置(hash值相等，key也相等)，将头结点赋值给临时变量e
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 3.2如果头结点不是要找的，判断节点的数据结构，是树结构，按红黑树的方式添加
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            // 是链表结构，遍历链表，找到链表尾部，即next为null
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    // 没找到与新增key相等的节点,在链表尾部新增一个节点
                    p.next = newNode(hash, key, value, null);
                    // 因为新增了节点，所以需要考虑是不是满足了转化为红黑树的条件
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                // 还没到链表尾部就找到了与key相等的节点，退出遍历
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                // 没找到将p的指针后移，继续遍历
                p = e;
            }
            // 遍历完后，p指向链表的倒数第二个节点，e指向添加新节点前的p.next或是
            // e=p(头结点时)
        }
        // 添加数据有两种情况，一种是key已经存在(此时e!=null),另一种是key(此时e=null)不存在
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            // oldValue为null或者指定要修改原值时，在找到的节点上用新的value替换oldValue
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            //这个在hashmap是个空方法，主要是留给LinkedHashMap去实现的
            afterNodeAccess(e);
            //返回老的值
            return oldValue;
        }
    }
    // hashmap被修改的次数加1
    ++modCount;
    // 容量加1，和阈值比较，看是否需要扩容
    if (++size > threshold)
        resize();
    // 同afterNodeAccess
    afterNodeInsertion(evict);
    return null;
}

从上面添加方法源码我们可以知道，添加主要干了这几件事：

1.hashmap为空，调用resize()初始化一个；

2.如果找到的链表的头结点null，第一次hash到这个位置，使用key，value新建一个都节点,然后修改统计字段modCount，size，如果size超过了扩容阈值，就扩容，然后返回null(在这一步是可以看出数组里面的元素是Node)；

3.如果头结点已经存放过值，分以下几种情况：

​ 3.1，头结点就是要找的节点，看是否需要修改oldValue，然后返回oldValue

​ 3.2，头结点不是要找的节点，又分节点是单链表结构(Node<K,V>)还是红黑树结构(TreeNode<K,V>)

​ 3.2.1，单链表：遍历节点，找到匹配的节点，如果遍历完都没找到就在链表尾部新增一个几点，此时需要考虑是否满足转化为红黑树的条件，后续还需要修改modCount，size，考虑是否满足扩容条件；如果在遍历的过程中就找到了匹配的节点(即以前用这个key存储过值)，看是否需要修改oldValue，然后返回oldValue;

​ 3.2.2，红黑树：按照红黑数的方式添加数据，源码抽取了一个方法，但是操作和单链表的方式大致相同，不同的事遍历方式，后面源码中会详细介绍。

1

分析完添加方法的逻辑后有没有发现，要是我们的数据结构是这样设计的，我们自己去实现添加方法时，整个逻辑也会是这样，并没有什么高深难懂的，当然其中用到的一些算法也很值得我们去学习。

tips：

1.通过hash值找对应的链表时，采用tab[i = (n - 1) & hash]方式，等价于tab[i = hash % n]，但是(n - 1) & hash方式更加高效。

2.源码中还有一个很好的函数式编码风格，采用临时变量去处理逻辑，如： K k; (k = p.key) == key。

3.单链表转化为红黑树是针对某一个链路的，扩容是针对table数组，即链表的数量。

通过上面分析，我们可以看出hashmap数据结构(主要是Node<K,V>[] table,Node<K,V>,TreeNode<K,V>)的应用，如下图：

1

某个单链表转化成红黑树的条件是：链表长度>=8 且总容量size>=64

hashmap数据结构小结

为什么要这么设计一个数据结构呢？我想这和hashmap的使用场景有关，hashmap就是维护着一个散列表，我们需要频繁在上面增删改查数据，数据一多，效率就成了问题。为了解决这个问题，单独使用某一种基本数据结构肯定不行，所以需要综合各个基本数据结构的有点来设计，比如数组的查询时间复杂度为O[1]，用它的作为桶固定大小；链表的插入、删除时间复杂度为O[1]，用它来添加删除节点；随着数据的增多，单个链表的长度会越长，在链表上查询数据的效率又成为问题，然后就会想到二叉树结构， 插入和查找 时间复杂度为 O(log(n)) 。这中间也用到我们经常听到的一种手法：空间换时间。

好了，hashmap数据结构的分析到这里就告一段了，下面我们接着来欣赏源码。

hashmap源码分析

1.添加方法相关的源码

上面我们已经介绍过添加方法的源码，里面涉及到的resize()，treeifyBin(),putTreeVal()我们接着分析。

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
/**
    * 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
    */
   final Node<K,V>[] resize() {
       // 将扩容前的table，cap,threshold分别赋值给临时变量oldTab，oldCap，oldThr
       // 刚创建的hashmap对象，table为null,cap为0，threshold为在没有指定容量时为0，否则也不为0
       Node<K,V>[] oldTab = table;
       int oldCap = (oldTab == null) ? 0 : oldTab.length;
       int oldThr = threshold;
       int newCap, newThr = 0;
       // 1.如果扩容前的容量大于0，不是第一次添加值
       if (oldCap > 0) {
           //1.1 判断扩容前容量是不是大于最大容量，如果是不扩容，把扩容阈值也设置为最大容量值
           if (oldCap >= MAXIMUM_CAPACITY) {
               threshold = Integer.MAX_VALUE;
               return oldTab;
           }
           // 1.2 对oldCap增大到2倍后，判断容量是不是小于最大容量并且>=默认容量
           else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                    oldCap >= DEFAULT_INITIAL_CAPACITY)
               //新阈值设置为原来的两倍
               newThr = oldThr << 1; // double threshold
       }
       // 2.如果扩容前的容量<=0，判断扩容前的阈值是否>0;如果>0,那扩容后的容量设置为oldThr
       // 创建hashmap对象时给定初始容量，第一次添加数据会出现cap<=0,oldThr>0
       else if (oldThr > 0) // initial capacity was placed in threshold
           newCap = oldThr;
       // 3. 扩容前的容量和阈值都<=0,使用无参构造创建对象，第一次添加值，初始化为默认值
       else {               // zero initial threshold signifies using defaults
           newCap = DEFAULT_INITIAL_CAPACITY;
           newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
       }
       //上面逻辑走的是2，重新计算下次扩容的阈值
       if (newThr == 0) {
           float ft = (float)newCap * loadFactor;
           newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                     (int)ft : Integer.MAX_VALUE);
       }
       //将阈值赋值给实例对象字段threshold
       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;
               //如果当前处的链表结构有数据，这里已经把链表头赋值给了临时变量e
               if ((e = oldTab[j]) != null) {
                   oldTab[j] = null;
                   //1.只有一个头结点，这个时候不用关心是单链表结构还是红黑树结构
                   if (e.next == null)
                       //重新计算key的hash在扩容后数组中新的位置
                       newTab[e.hash & (newCap - 1)] = e;
                   // 2.当前节点属于红黑树节点类型，按照红黑树的方式处理，这里先不展开
                   else if (e instanceof TreeNode)
                       ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                   //3.走到这，可以确定是单链表结构了，按照单链表的方式处理
                   else { // preserve order
                       //这里定义了两个高低位链表头结点和尾节点
                       Node<K,V> loHead = null, loTail = null;
                       Node<K,V> hiHead = null, hiTail = null;
                       Node<K,V> next;
                       //循环遍历链表oldTab[j]，知道节点的next=null
                       do {
                           next = e.next;
                           // 以第一次扩容为例，如果key的hash值落在0-15之间的，放在低位链表
                           if ((e.hash & oldCap) == 0) {
                               // 第一次走到这里，将e给头结点，
                               if (loTail == null)
                                   loHead = e;
                               //不是第一次落在低位链表，将新节点添加在尾部
                               else
                                   loTail.next = e;
                               // loTail指向最新的尾部
                               loTail = e;
                           }
                           //hash值落在16-31之间的，放在高位链表
                           else {
                               //逻辑同低位链表
                               if (hiTail == null)
                                   hiHead = e;
                               else
                                   hiTail.next = e;
                               hiTail = e;
                           }
                       } while ((e = next) != null);
                       //低位链表放在扩容后j的位置，并把尾部节点的next指向置为null
                       if (loTail != null) {
                           loTail.next = null;
                           newTab[j] = loHead;
                       }
                      //高位链表放在j+pldCap的位置，hiTail.next置为null
                       if (hiTail != null) {
                           hiTail.next = null;
                           newTab[j + oldCap] = hiHead;
                       }
                   }
               }
           }
       }
       return newTab;
   }

扩展：

1.有很多同学会对hash & n 与hash & (n-1)产生疑惑？

这个地方设计的相当 巧妙，我们以n=16为例来讲解：

16 - 1 = 15, 二进制表示为 0000 0000 0000 0000 0000 0000 0000 1111
可见除了低4位, 其他位置都是0,简写为1111， 则 (16-1) & hash 自然就是取hash值的低4位（假设abcd）,所以我们用hash & (n-1)来确定hash在table数组中的位置.

以此类推, 当我们将oldCap扩大两倍后, 新的index的位置就变成了 (32-1) & hash, 其实就是取 hash值的低5位. 那么对于同一个Node, 低5位的值无外乎下面两种情况:0abcd或 1abcd；16的二进制简写表示为10000,如果以16为界来区分高低位的话，我们刚好可以用它来确认hash是处在高位还是低位

2.上面的do{}while以及后面的两个if判断做的是什么逻辑？

如果 (e.hash & oldCap) == 0 则该节点在新表的下标位置与旧表一致都为 j
如果 (e.hash & oldCap) == 1 则该节点在新表的下标位置 j + oldCap

大概是这个意思：扩容前的数组范围是0-15，这个时候hash值为1,17的都会落在table[1]，当数组范围扩大到0-31时，这个时候就需要把原来的17落在table[17]才算合理

1

putTreeVal() ：树添加节点

这个其实是TreeNode内部的一个方法，

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
/**
     * Tree version of putVal.
     * 指定key所匹配到的节点对象，putVal针对这个对象去修改V（返回空说明创建了一个新节点）
     */
    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;;) {
            // 声明方向dir
            int dir, ph; K pk;
            //1.hash决定左右方向，如果当前节点的hash大于k的h，添加的key应该在当前节点的左边，如果小于h，在右边
            if ((ph = p.hash) > h)
                dir = -1;
            else if (ph < h)
                dir = 1;
            // 如果当前节点的键对象 和 指定key对象相同,返回当前节点，在外层方法会对v进行写入
            else if ((pk = p.key) == k || (k != null && k.equals(pk)))
                return p;
            // 走到这里说明hash相等，但是key不等
           // 2.由key决定左右
            else if ((kc == null &&
                      (kc = comparableClassFor(k)) == null) ||
                     (dir = compareComparables(kc, k, pk)) == 0) {
                //第一次循环时，key没有实现comparable接口||实现了但是两个key的类型不同||类型相同，key也相同 会走到这里
                /*
                 * searched 标识是否已经对比过当前节点的左右子节点了
                 * 如果还没有，那么就递归遍历对比，看是否能够得到key相等的的节点
                 * 如果得到了key相等的的节点就返回
                 * 如果还是没有键的equals相等的节点，那说明应该创建一个新节点了
                 */
                if (!searched) {
                    TreeNode<K,V> q, ch;
                    //标记遍历过
                    searched = true;
                    //先在左子树上找key相等的节点，找不到再到右子树上找，有找到就返回找到的节点
                    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相等的节点，再比较一下当前节点键和指定key键的大小,来决定是在左还是在右添加节点
                dir = tieBreakOrder(k, pk);
            }
//
            TreeNode<K,V> xp = p;
           /*
            * 如果dir小于等于0，那么看当前节点的左节点是否为空，如果为空，就可以把要添加的元素作为当前节点的左节点，如果不为空，还需要下一轮继续比较
            * 如果dir大于等于0，那么看当前节点的右节点是否为空，如果为空，就可以把要添加的元素作为当前节点的右节点，如果不为空，还需要下一轮继续比较
            */
            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;
                //当前节点的next指向新增的节点
                xp.next = x;
                //新增节点的父节点、前节点指向当前节点
                x.parent = x.prev = xp;
                // 如果原来的next节点不为空，那么原来的next节点的前节点指向到新的树节点，因为新节点是用xpn作为next创建的
                if (xpn != null)
                    ((TreeNode<K,V>)xpn).prev = x;
                // 重新平衡，以及新的根节点置顶
                moveRootToFront(tab, balanceInsertion(root, x));
                // 返回空，意味着产生了一个新节点
                return null;
            }
        }
    }

上面步骤可以为概括如下：树添加节点

1.找到root节点，自旋遍历；

2.确定新节点的位置，如果添加之前已经存在直接返回，没有就创建一个新节点

2.1 .用hash来找节点，找不到hash相等的，比较当前节点与指定hash的大小来决定在左还是在右添加新节点；

2.2 .找到hash相等，再与key作比较，找到与key相等的节点，找到直接返回；

2.3 .找不到就比较当前节点与指定key的大小来决定在左还是在右添加新节点；

3.平衡的添加节点，并将root节点设置为头结点

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
34
35
36
37
38
39
/**
   * 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;
      /*
       * 如果元素数组为空 或者 数组长度小于 树结构化的最小限制,走扩容逻辑
       * MIN_TREEIFY_CAPACITY 默认值64，对于这个值可以理解为：如果元素数组长度小于这个值，没有必要去进行结构转换
       * 当一个数组位置上集中了多个键值对，那是因为这些key的hash值和数组长度取模之后结果相同。（并不是因为这些key的hash值相同）
       * 因为hash值相同的概率不高，所以可以通过扩容的方式，来使得最终这些key的hash值在和新的数组长度取模之后，拆分到多个数组位置上。
       */
      if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
          resize();
  	// 大于MIN_TREEIFY_CAPACITY，根据hash值计算得到需要转换数据结构的链表
      else if ((e = tab[index = (n - 1) & hash]) != null) {
          //定义树节点的头、尾
          TreeNode<K,V> hd = null, tl = null;
          //遍历链表，将所有节点转换为树结构
          do {
              //将当前节点转化为红黑数节点，replacementTreeNode内部其实只是new TreeNode()
              TreeNode<K,V> p = replacementTreeNode(e, null);
              //转化链表的头结点时，tl为null,此时将树的头结点指向p
              if (tl == null)
                  hd = p;
              // 尾节点不为空，以下两行是一个双向链表结构
              else {
                  p.prev = tl;
                  tl.next = p;
              }
              //树尾节点指向新创建的节点
              tl = p;
          } while ((e = e.next) != null);
          //注意上面的步骤只是把每个节点转化为TreeNode类型的节点，并用双向链表的方式链接，节点的左右子节点以及root节点并没有处理
          // 树的头结点不为null,将前面转换的所有树节点连起来，
          if ((tab[index] = hd) != null)
              hd.treeify(tab);
      }
  }

逻辑如下：

1.判断table容量是否小于MIN_TREEIFY_CAPACITY，确定是走扩容逻辑还是转化为树；

2.找到需要转化为树的链表位置，循环遍历，将每个节点转化为树节点，在连起来

treeify()：连接树形节点

treeify方法是TreeNode类的一个实例方法，通过TreeNode对象调用，实现该对象打头的链表转换为树结构。

在treeifyBin()方法中是头结点在调用该方法： hd.treeify(tab)。

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
/**
      * 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;
         //在treeifyBin()中this指向双向链表头结点，此处是在遍历链表
         for (TreeNode<K,V> x = this, next; x != null; x = next) {
             next = (TreeNode<K,V>)x.next;
             x.left = x.right = null;
             //1.如果根节点为null,将当前节点设置当前节点为根节点，同时把根节点的父节点设置为null,标记为黑色
             if (root == null) {
                 x.parent = null;
                 x.red = false;
                 root = x;
             }
             //2.如果根节点不为null
             else {
                 //获取当前链表节点的 key 、hash、key的class类型
                 K k = x.key;
                 int h = x.hash;
                 Class<?> kc = null;
                 // 自旋遍历红黑树，此遍历没有设置边界，只能从内部跳出
                 //因为要确认链表中当前节点再红黑树中的位置，所以需要遍历插入
                 for (TreeNode<K,V> p = root;;) {
                     //dir 标识方向（左右）、ph标识当前树节点的hash值,pk前树节点的key
                     int dir, ph;
                     K pk = p.key;
                     //如果当前树节点hash值 大于 当前链表节点的hash值,标识当前链表节点会放到当前树节点的左侧,否则标识右侧，如果hash相等,再用key的作比较
                     if ((ph = p.hash) > h)
                         dir = -1;
                     else if (ph < h)
                         dir = 1;
                     /*
                      * 如果两个节点的key的hash值相等，那么还要通过其他方式再进行比较。
                      * 如果当前链表节点的key实现了comparable接口，并且当前树节点和链表
                      * 节点是相同Class的实例，那么通过comparable的方式再比较两者。
                      * 如果还是相等，最后再通过tieBreakOrder比较一次
                      */
                     else if ((kc == null &&
                               (kc = comparableClassFor(k)) == null) ||
                              (dir = compareComparables(kc, k, pk)) == 0)
                         dir = tieBreakOrder(k, pk);

                     TreeNode<K,V> xp = p;
                     /*
                      * 如果dir 小于等于0 ：当前链表节点一定放置在当前树节点的左侧，但
                      * 不一定是该树节点的左孩子，也可能是左孩子的右孩子或者更深层次的节点。
                      * 如果dir 大于0 ：当前链表节点一定放置在当前树节点的右侧，但不一
                      * 定是该树节点的右孩子，也可能是右孩子的左孩子或者更深层次的节点。
                      * 如果当前树节点不是叶子节点，那么最终会以当前树节点的左孩子或者右孩
                      * 子为起始节点  再从树节点遍历处开始 重新寻找自己（当前链表节点）的位置
                      * 如果当前树节点就是叶子节点，那么根据dir的值，就可以把当前链表节点挂
                      * 载到当前树节点的左或者右侧了。
                      * 挂载之后，还需要重新把树进行平衡。平衡之后，就可以针对下一个链表节点
                      * 进行处理了。
                      */
                     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;
                     }
                 }
             }
         }
         //将root设为头结点
         moveRootToFront(tab, root);
     }

上面的源码小结一下：

1.遍历链表，确定每个链表节点在树中的位;

2.循环遍历当前树，然后找到该链表节点可以插入的位置，依次和遍历的树节点比较，比它大则跟其右孩子比较，小则与其左孩子比较，依次遍历，直到找到左孩子或者右孩子为null的位置进行插入

moveRootToFront()：将root设为头结点

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

     /**
      * Ensures that the given root is the first node of its bin.
      * 把红黑树的根节点设为  其所在的数组槽 的第一个元素
* 首先明确：TreeNode既是一个红黑树结构，也是一个双链表结构
* 这个方法里做的事情，就是保证树的根节点一定也要成为链表的首节点
      */
     static <K,V> void moveRootToFront(Node<K,V>[] tab, TreeNode<K,V> root) {
         int n;
         if (root != null && tab != null && (n = tab.length) > 0) {
             //计算桶的位置，first指向链表第一个节点
             int index = (n - 1) & root.hash;
             TreeNode<K,V> first = (TreeNode<K,V>)tab[index];
             //如果root不是第一个节点，则将root放到第一个首节点位置
             if (root != first) {
                 //定义一个节点，后续存放root.next
                 Node<K,V> rn;
                 //将根节点设置为链表的头结点
                 tab[index] = root;
                 //root前驱节点
                 TreeNode<K,V> rp = root.prev;
                 //如果root节点的next不为null,那么next的前驱设置为原root的前驱节点
                 //相当于把root从链表中摘除
                 if ((rn = root.next) != null)
                     ((TreeNode<K,V>)rn).prev = rp;
                 // 如果root的前驱不为null,那么将前驱的next设置为root的后驱
                 //这一步root彻底从双向链表中摘除
                 if (rp != null)
                     rp.next = rn;
                 //如果原链表第一个节点不为null,将first的前驱设置为root
                 if (first != null)
                     first.prev = root;
                 //root后驱指向first
                 root.next = first;
                 //root没有前驱
                 root.prev = null;
             }
             //这里是防御性编程，校验更改后的结构是否满足红黑树和双链表的特性
             //因为HashMap并没有做并发安全处理，可能在并发场景中意外破坏了结构
             assert checkInvariants(root);
         }
     }

这个方法是将root节点移动到桶中的第一个元素，也就是链表的头节点，这样做是因为在判断桶中元素类型的时候会对链表进行遍历，将根节点移动到链表前端可以确保类型判断时不会出现错误。

1.将root节点从原位置抽出，原root的前后驱互相连接

2.将root设置为原first节点的后驱设置为first，并将root的前驱设置为null

3.重新检查树的结构

balanceInsertion():平衡插入

这个很核心的一个方法，目的是让红黑树添加新数据后继续保持平衡，putTreeVal() 、treeify()都有调用。

红黑树的每个节点遵循以下规则：

  • 所有节点只能是红色或者黑丝
  • 根节点是黑色
  • 只存在相邻的红色节点（即红色节点不能有红色的父节点或者红色的孩子）
  • 任意从root到Nil节点，经过的路径中黑色节点的数目是一样的。
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
static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
                                            TreeNode<K,V> x) {
    // 新插入的节点标为红色
    x.red = true;
    /*
     * 这一步即定义了变量，又开起了循环，循环没有控制条件，只能从内部跳出
     * xp：当前节点的父节点、xpp：爷爷节点、xppl：左叔叔节点、xppr：右叔叔节点
     */
    for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
        // L1  如果父节点为空
        //说明当前节点就是根节点，那么把当前节点标为黑色，返回当前节点
        if ((xp = x.parent) == null) {
            x.red = false;
            return x;
        }
        /**
         * 插入的节点的父节点是黑色节点，则不需要调整，因为插入的节点会初始化为
         * 红色节点，红色节点是不会影响树的平衡的。
         * 插入的节点的祖父节点为null，即插入的节点的父节点是根节点，直接插入即
         * 可(因为根节点肯定是黑色).
         * 这两种都不需要调整，直接返回原root节点
         */
        //L2
        else if (!xp.red || (xpp = xp.parent) == null)
            return root;
        //这后面的都是插入节点的父节点是红色
        // L3 插入的节点父节点和爷爷节点都存在，并且其父节点是爷爷节点的左节点
        if (xp == (xppl = xpp.left)) {
            //L3_1 插入节点的右叔叔节点存在并且是红色
            if ((xppr = xpp.right) != null && xppr.red) {
                //将右叔叔、父节点设置为黑色，爷爷节点设置为红色
                xppr.red = false;
                xp.red = false;
                xpp.red = true;
                //运行到这里，就又会进行下一轮的循环了,将爷爷节点当做处理的起始节点,相当于沿着子节点向根节点遍历检查是否平衡
                x = xpp;
            }
            //L3_2 插入节点的叔叔节点是黑色或不存在
            else {
                //L3_2_1 插入节点是其父节点的右孩子
                if (x == xp.right) {
                    //父节点左旋
                    root = rotateLeft(root, x = xp);
                    xpp = (xp = x.parent) == null ? null : xp.parent;
                }
                //L3_2_2 插入节点是其父节点的左孩子
                //此时有父节点将其设置为黑色，有爷爷节点将其设置为红色
                if (xp != null) {
                    xp.red = false;
                    if (xpp != null) {
                        xpp.red = true;
                        //爷爷节点右旋
                        root = rotateRight(root, xpp);
                    }
                }
            }
        }
        // L4 插入的节点父节点和祖父节点都存在，并且其父节点是爷爷节点的右节点
        else {
            //L4_1 插入节点的叔叔节点是红色
            if (xppl != null && xppl.red) {
                xppl.red = false;
                xp.red = false;
                xpp.red = true;
                //从爷爷节点开始继续向根节点遍历检查平衡
                x = xpp;
            }
            //L4_2 如果左叔叔为空或者是黑色
            else {
                //L4_2_1 插入节点是其父节点的左孩子
                if (x == xp.left) {
                    //父节点右旋
                    root = rotateRight(root, x = xp);
                    xpp = (xp = x.parent) == null ? null : xp.parent;
                }
                //L4_2_2 插入节点是其父节点的右孩子
                if (xp != null) {
                    xp.red = false;
                    if (xpp != null) {
                        xpp.red = true;
                        //爷爷节点左旋
                        root = rotateLeft(root, xpp);
                    }
                }
            }
        }
    }
}

上面的逻辑直接看源码不太好理解，可以参考下面的图来看源码：

变色不旋转

左旋

右旋

rotateLeft() : 左旋

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
static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
                                             TreeNode<K,V> p) {
           //r:p右节点，pp:p的父节点，rl:p的右节点的左孩子节点
    		TreeNode<K,V> r, pp, rl;
    		//左旋的节点以及左旋的节点的右孩子不为空
           if (p != null && (r = p.right) != null) {
                // 左旋的节点的右孩子的左节点赋给左旋的节点的右孩子 节点为：rl
               //1.左旋节点的右节点存在左节点，设置rl的父节点为当前节点
               if ((rl = p.right = r.left) != null)   
                   rl.parent = p;
               //将r的父节点指向p的父节点，相当于右孩子提升了一层
       		//此时如果父节点为空，说明r 已经是顶层节点了，应该作为root 并且标为黑色
               if ((pp = r.parent = p.parent) == null)
                   (root = r).red = false;
               // 如果父节点不为空并且要左旋的节点是左孩子,将r设置为父节点的左孩子，即r取代p
               else if (pp.left == p)
                   pp.left = r;
               //如果父节点不为空并且要左旋的节点是右孩子，将r设置为父节点的右孩子，即r取代p
               else
                   pp.right = r;
               //将p这是为r的左孩子及父节点，r彻底取代p
               r.left = p;
               p.parent = r;
           }
           return root;
       }

左旋小结：

1.需要左旋节点 p 的右孩子 r 必须存在，并且将r取代p的位置；

2.如果 r 存在左孩子，将r的左孩子设置为p的右孩子；

3.r成为p的父节点，p成为r的左孩子节点

左旋图

左旋动图

rotateRight():右旋

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
static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
                                               TreeNode<K,V> p) {
             //l:p左节点，pp:p的父节点，lr:p的左节点的右孩子节点
    		TreeNode<K,V> l, pp, lr;
    		//右旋节点以及右旋节点的左孩子不为空
            if (p != null && (l = p.left) != null) {
                //将p的左节点的右孩子节点赋值给p的左节点，如果lr存在，将其父节点设置为p
                //1.这一步相当于在剔除p的左节点
                if ((lr = p.left = l.right) != null)
                    lr.parent = p;
                //2.将剔除的l节点替换p的位置
                //将l父节点指向p父节点，相当于左孩子提升了一层
        		//2.1 p没有父节点，说明l 已经是顶层节点了，应该作为root 并且标为黑色
                if ((pp = l.parent = p.parent) == null)
                    (root = l).red = false;
                //2.2 p有父节点，并且p是父节点的右节点，将父节点的右节点设置为l
                else if (pp.right == p)
                    pp.right = l;
                 //2.3 p有父节点，并且p是父节点的左节点，将父节点的左节点设置为l
                else
                    pp.left = l;
                //交换p,l自父节点的连接
                l.right = p;
                p.parent = l;
            }
            return root;
        }

右旋小结：

需要右旋节点 p 的左孩子 l 必须存在：

1.剔除 l 节点：将l的右节点设置为p的左节点；

  1. l、p节点交换位置

右旋图

右旋动图

小结

红黑树整体的构建过程可参考下图演变过程，以插入数字10，5，9，3，6，7，19，32，24，17 为例

1

2.删除方法

remove() -> 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
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
 /**
  * Removes the mapping for the specified key from this map if present.
  *
  * @param  key key whose mapping is to be removed from the map
  * @return the previous value associated with <tt>key</tt>, or
  *         <tt>null</tt> if there was no mapping for <tt>key</tt>.
  *         (A <tt>null</tt> return can also indicate that the map
  *         previously associated <tt>null</tt> with <tt>key</tt>.)
  */
 public V remove(Object key) {
     Node<K,V> e;
     return (e = removeNode(hash(key), key, null, false, true)) == null ?
         null : e.value;
 }

/**
  * Implements Map.remove and related methods
  *
  * @param hash hash for key
  * @param key the key
  * @param value the value to match if matchValue, else ignored
  * @param matchValue if true only remove if value is equal
  * @param movable if false do not move other nodes while removing
  * @return the node, or null if none
  */
 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里面有数据，并且找到的桶位的头结点不为null
     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;
         //1.找到要删除的节点
         //1.1 头结点就是
         if (p.hash == hash &&
             ((k = p.key) == key || (key != null && key.equals(k))))
             node = p;
         //1.2 头结点不是，获取下一个节点
         else if ((e = p.next) != null) {
             // 1.2.1 数据结构是红黑树，按红黑树的方式查找
             if (p instanceof TreeNode)
                 node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
             // 1.2.2 数据结构是链表，按链表的方式查找
             else {
                 do {
                     if (e.hash == hash &&
                         ((k = e.key) == key ||
                          (key != null && key.equals(k)))) {
                         node = e;
                         break;
                     }
                     p = e;
                 } while ((e = e.next) != null);
             }
         }
         // 2. 找到要删除的节点
         if (node != null && (!matchValue || (v = node.value) == value ||
                              (value != null && value.equals(v)))) {
             // 2.1 找到的节点是红黑数结构，按红黑树方式删除
             if (node instanceof TreeNode)
                 ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
             // 2.2 找到的节点是链表
             //2.2.1 是头结点
             else if (node == p)
                 tab[index] = node.next;
             // 2.2.2 不是头结点
             else
                 p.next = node.next;
             // 修改次数加1，size减1，返回删除的节点
             ++modCount;
             --size;
             afterNodeRemoval(node);
             return node;
         }
     }
     return null;
 }

删除涉及到removeTreeNode()方法不打算展开来讲，逻辑和添加要考虑的东西刚好相反，比如减少一个节点需要考虑是不是要把树结构转化为链表结构，在红黑树中删除还需要考虑树的平衡，里面也会涉及到左旋右旋，感兴趣的同学可以去看看源码。

总结：

hashmap里面综合运用了数组，单链表，双向链表，平衡二叉树（AVL）等数据结构，使得hashmap在添加、删除，查找上的时间复杂度尽可能最低，所以为什么要研究数据结构，一句话，数据结构的最终目的是提高数据的处理速度。

这篇博客花了很多时间在上面，感觉自己成长了不少，后面将继续分析数据结构。

资料：

数据结构动画演示：

​ https://www.cs.usfca.edu/~galles/visualization/Algorithms.html 

https://visualgo.net/zh/bst