全网!最全！最详细！ HashMap 源码解析

系统管理员 2024-04-18 12:02 12阅读 0赞

## 要思考的问题 ##

*  HashMap的底层数据结构(节点结构,这种结构有什么优点)
 *  如何处理hash冲突
 *  怎么扩容?扩展机制是什么?
 *  增删改查过程
 *  链表到红黑树的转换过程,反之?
 *  红黑树相关(见另一篇数据结构之红黑树)
 *  hash计算

## 达到的目标 ##

*  掌握底层数据结构
 *  掌握扩容原理
 *  掌握hash冲突的处理过程
 *  掌握增删改查过程

## 看之前要掌握的知识点 ##

### 红黑树 ###

## 看之前大体了解的知识点 ##

### hash算法 ###

### Poisson分布 ###

[poisson分布][poisson]

## 开始 ##

### HashMap的继承体系 ###

\[外链图片转存失败(img-z4jA6cu0-1567747065188)(./images/HashMap01-继承体系.png)\]

*  AbstractMap: map的抽象类,以最大限度的减少实现Map接口的类的工作量。

### hashMap结构 ###

### 字段解释 ###

#### 常量字段(默认值字段) ####

*  DEFAULT\_INITIAL\_CAPACITY=1<<4: 默认的初始容量,默认是为16,必须是2的n次方.为什么呢? 见扩容的方法。
 *  DEFAULT\_LOAD\_FACTOR=0.75f: 默认的负载因子。它和哈希表的容量的乘积是决定是否重新hash的阈值。
 *  TREEIFY\_THRESHOLD=8: 使用树而不是链表的计数阈值。当桶的元素添加到具有至少这么多节点时，桶被转换为树。
 *  UNTREEIFY\_THRESHOLD=6: 用于在调整大小操作期间解除（拆分）桶的桶计数阈值。(untreeifying不是一个英语单词,这里的以是非树化,即转换成普通列表的过程).也就是说从树转换成普通的桶(链表)的阈值。
 *  MAXIMUM\_CAPACITY=1<<30: 最大的容量: `1<<30`，如果具有参数的任一构造函数隐式指定更高的值，则使用此参数。必须是2的n次方,小于等于`1<<30`
 *  MIN\_TREEIFY\_CAPACITY=64: 容器可以树化的最小容量(否则，如果bin中的节点太多，则会调整表的大小.)应该至少为 4 \* TREEIFY\_THRESHOLD，以避免调整大小和树化阈值之间的冲突.

#### 类属性 ####

*  table: `transient HashMap.Node<K,V>[] table`; table在首次使用时初始化，并根据需要调整大小。分配时，长度始终是2的幂。(我们还在一些操作中容忍长度为零，以允许当前不需要的自举机制)
 *  entrySet: `transient Set<Map.Entry<K,V>> entrySet`; 保存缓存的entrySet.
 *  size: `transient int size`; map中元素的数量。结构修改是那些改变HashMap中映射数量或以其他方式修改其内部结构（例如，rehash）的修改。此字段用于在HashMap的Collection-views上快速生成迭代器(见ConcurrentModificationException)

--------------------

注意: 这些字段都是 `transient` 的? 为什么呢?

*  loadFactor: `final float loadFactor;`hash表的负载因子，在实例化hashTable的时候指定,该对象内不能变更(final);
 *  threshold: `int threshold;`, 下一次调整容器大小的阈值. threshold=capacity \* load factor

#### HashMap的两种节点 ####

*  基本的哈希桶的节点(链表的结点) Node

`static class Node<K,V> implements Map.Entry<K,V>`它继承了Map的Entry,是对子类的行为规范。要求提供了getKey(),getValue()等常用方法。

链表节点的结构如下:

static class Node<K,V> implements Map.Entry<K,V> { 
        final int hash; // 避免重复计算key的hash值
        final K key;
        V value;
        // 指向下一个节点的指针
        HashMap.Node<K,V> next;
    
        Node(int hash, K key, V value, HashMap.Node<K,V> next) { 
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }
    
        @Override
        public final K getKey()        {  return key; }
        @Override
        public final V getValue()      {  return value; }
        @Override
        public final String toString() {  return key + "=" + value; }
    
        // todo 没有找到在哪里使用了这个方法
        @Override
        public final int hashCode() { 
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }
    
        @Override
        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;
        }
    }

*  Tree的节点 TreeNode

`static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V>`继承了其子类的Entry, 子类的Entry继承了父类的Node.注意了，这里乍一看还挺乱。来张图吧。  
\[外链图片转存失败(img-ZPV5rtwT-1567747065189)(./images/hashMap的节点的继承图.png)\]

这里呢,TreeNode其实是Node的孙子, 也就是说HashMap的树节点是链表节点的孙子辈儿的。  
为什么要使两种节点有继承关系呢? 为什么TreeNode不直接继承Node节点呢？

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { 
        HashMap.TreeNode<K,V> parent;  // red-black tree links
        HashMap.TreeNode<K,V> left;
        HashMap.TreeNode<K,V> right;
        HashMap.TreeNode<K,V> prev;    // needed to unlink next upon deletion
        boolean red;
        TreeNode(int hash, K key, V val, HashMap.Node<K,V> next) { 
            super(hash, key, val, next);
        }
        // 省略其他代码
    }

### HashMap增加方法 HashMap\#put() ###

/** * 将指定的value和key关联在map中。 * 如果map中已经存在了key,那么将会替换掉老的value。 * @param key key 指定的key * @param value value 和指定key关联的value * @return 如果返回了value，就说明map中原来和key关联是有值的。如果返回null就说明没有value。 */
    public V put(K key, V value) { 
        return putVal(hash(key), key, value, false, true);
    }

这里就比较有看点了, 1.这里是hashMap的增加方法，增加方法里必然会遇到hash冲突的问题，我们等会看下hash冲突是如何处理的，还会涉及到扩容的问题, 我们也要来看看他是怎么扩容的, 扩容的过程中还会遇到普通的桶转换成树的过程.我们先来看下hash值是怎么计算出来的。

*  hash值的计算 \{TODO 和jdk1.7中的比较\}

/** * 计算key的hashCode并且和hashCode值高16位进行异或运算。(异或: 相同为0，不同为1) * 混和低位和高位，就是为了加大低位的随机性,而且混合后的低位掺杂了高位的部分特征, * 这样高位的信息也被变相的保留了下来。 */
    static final int hash(Object key) { 
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

为什么这么做呢? 见HashMap的Hash函数到底有什么意义

*  那我们接下接着看putVal()方法。

/** * 实现Map.put相关的方法。 * @param hash hash for key * @param key the key * @param value the value to put * @param onlyIfAbsent if true, don't change existing value * 如果是true的,不会修改存在的值。返回老的值。 * @param evict if false, the table is in creation mode. * 如果为false的时候,表属于创建模式,第一次新增元素的时候。 * @return previous value, or null if none */
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                    boolean evict) { 
    
        HashMap.Node<K,V>[] tab;
        HashMap.Node<K,V> p;
        int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            // 如果数组为null,或者数组长度为0的时候，数组需要调整大小。
            n = (tab = resize()).length;
        if ((p = tab[i = (n - 1) & hash]) == null)
            // 定位到数组的桶为null的时候,创建桶内的第一个元素。next=null;
            tab[i] = newNode(hash, key, value, null);
        else { 
            // 如果桶不为null，则创建链表
            HashMap.Node<K,V> e; K k;
            // p表示当前桶的第一个元素。
            // 如果新增的元素和第一个元素相等的话(出现hash冲突),暂存已经存在的元素到变量e中。
            if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof HashMap.TreeNode)
                // 如果是树节点。
                e = ((HashMap.TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else { 
                // 链表元素新增的过程了。
                for (int binCount = 0; ; ++binCount) { 
                    if ((e = p.next) == null) { 
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1)
                            // 如果桶内的元素数量达到树化的阈值,将链表转换成树。
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                        // 如果第一个元素和要新增的元素hash,key都相等的话,直接进行新增操作。
                        break;
                    p = e;
                }
            }
    
            if (e != null) {  // existing mapping for key
                // 如果原来的元素不为空,保留原来的值。
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    // 覆盖掉原来的value;
                    e.value = value;
                // 留一个无方法体的方法，供子类扩展
                afterNodeAccess(e);
                return oldValue;
            }
        }
        // failFast计数
        ++modCount;
        if (++size > threshold)
            // 如果table中的桶的数量超过了阈值。扩容。
            resize();
        // 供子类扩展的方法。
        afterNodeInsertion(evict);
        return null;
    }

这段代码里中有三处重要的地方,resize(),treeifyBin(),putTreeNode(),接下来我们依次看下这三个方法。

#### resize ####

/** * 初始化，或者加倍表格的大小 * 如果为null时候，根据字段threshold的初始容量进行分配 * 否则，因为我们正在使用二次幂扩展，所以每个bin中的元素必须保持相同的索引，或者在新表中以两个偏移的幂移动 * * @return the table 新的表 */
    final HashMap.Node<K, V>[] resize() { 
        HashMap.Node<K, V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        if (oldCap > 0) { 
            // 如果旧表的大小大于0
            if (oldCap >= MAXIMUM_CAPACITY) { 
                // hash表达到最大容量
                threshold = Integer.MAX_VALUE;
                return oldTab;
            } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                    oldCap >= DEFAULT_INITIAL_CAPACITY) { 
                // 如果翻倍后旧表大小<最大表长度，并且旧表长度>默认初始化长度。
                // 扩容的阈值也翻倍。 还是等级 table.length*loadFactor
                newThr = oldThr << 1; // double threshold
            }
        } else if (oldThr > 0) {  // initial capacity was placed in threshold
            // 旧表长度<=0,旧的threshold>0,
            // 就把threshold设置为表长度。
            newCap = oldThr;
        } else {                // zero initial threshold signifies using defaults
            // 设置为默认值。
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
    
        if (newThr == 0) { 
            // 如果新的扩缩容阈值等于0,设置新的扩缩容阈值为新的容量*负载因子.
            float ft = (float) newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ?
                    (int) ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
    
        // 重新创建新的hash表
        @SuppressWarnings({ "rawtypes", "unchecked"})
        HashMap.Node<K, V>[] newTab = (HashMap.Node<K, V>[]) new HashMap.Node[newCap];
        table = newTab;
        // 如果旧表不为空,进行扩容.
        // 否则(旧表为空)就进行初始化过程.
        if (oldTab != null) { 
            for (int j = 0; j < oldCap; ++j) { 
                HashMap.Node<K, V> e;
                if ((e = oldTab[j]) != null) { 
                    oldTab[j] = null;
                    if (e.next == null) { 
                        // 如果当前桶只有一个节点。
                        newTab[e.hash & (newCap - 1)] = e;
                    } else if (e instanceof HashMap.TreeNode) { 
                        // 如果当前桶是棵红黑树
                        ((HashMap.TreeNode<K, V>) e).split(this, newTab, j, oldCap);
                    } else {  // preserve order
                        // 桶是链表,将该桶内的元素重新分配到表中。
    
                        HashMap.Node<K, V> loHead = null, loTail = null;
                        HashMap.Node<K, V> hiHead = null, hiTail = null;
                        HashMap.Node<K, V> next;
    
                        // 遍历桶内的元素，将元素重新分配到hash表内的各个桶中。
                        // 具体的实现过程是: 将当前的元素的hash值和容量取&,如果>0,那就说明该元素应该分配到新的桶内。
                        // 桶的位置就是: oldCap+j.即桶原来容器+该元素所在的桶的下标。(hiHead所标识的位置)
                        // 反之如果hash值是==0的,那么该元素就应该还在当前桶内。(loHead所标识的位置)
                        // 这里所说的位置都是指桶的下标,整个表都是新的了,位置肯定都变了。
                        // 为什么可以这么实现呢？
                        // 因为扩容的时候，使用的是原来容量的2倍进行扩容的。所以就可以使用(oldCap+j)的方式来确定元素的新位置了。
                        do { 
                            next = e.next;
                            if ((e.hash & oldCap) == 0) { 
                                // 还在原桶中
                                if (loTail == null)
                                    loHead = e;
                                else { 
                                    // 位置最后一个节点为空,使用e=next的时候，next为null的情况。
                                    // 在桶内元素遍历完成后,会把桶的最后一个元素的next置为null。
                                    loTail.next = e;
                                }
                                loTail = e;
                            } else { 
                                // 放置到新的桶内。
                                if (hiTail == null)
                                    hiHead = e;
                                else { 
                                    // 位置最后一个节点为空,使用e=next的时候，next为null的情况。
                                    // 在桶内元素遍历完成后,会把桶的最后一个元素的next置为null。
                                    hiTail.next = e;
                                }
                                hiTail = e;
                            }
                        } while ((e = next) != null);
    
                        if (loTail != null) { 
                            loTail.next = null;
                            // 原来桶的位置。
                            newTab[j] = loHead;
                        }
    
                        if (hiTail != null) { 
                            hiTail.next = null;
                            // 确定新桶的位置
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

看一个散列还算非常均匀的例子来看扩容过程。

\[外链图片转存失败(img-4b59ZB73-1567747065195)(./images/hashMap04-Put方法过程01.png)\]

那么进行扩容的过程是怎么样的呢？

\[外链图片转存失败(img-uOO7peRH-1567747065197)(./images/hashMap05-resize方法01.png)\]

以元素1和12为例,看扩容过程:  
元素1的hash值为49.(以hashMap计算hash值的方式得出。)， 与15取&计算桶的下标为1, 扩容后，与31取&,计算桶的下标为17.所以扩容前位置是0，扩容后元素1的存放位置是17。  
代码中是怎么完成这个过程的呢？  
和扩容前hash表的容量取&,得 `49 & 16 = 16 > 0`(代码第86-96行), 新的桶的头节点(对应代码里的hiHead)就是当前节点1，尾节点(hiTail)赋为当前节点。然后进行下一次`do...while`循环，处理节点12, 计算出节点12的hash值为`1569`,进行计算`1569 & 16 = 0 == 0`原来桶的头结点是节点12,尾节点也是节点12(对应着代码第76-86行),这样hitail和loTail均不为null, 所以然后直接使用`newTab[j] = loHead;`和 `newTab[j + oldCap] = hiHead;`的方式确定桶的位置。这个案例里，处理完节点12才会确定桶的位置。因为原来的表中下标为1的桶中有两个元素1和12.那桶里只有一个元素的怎么处理的呢？`newTab[e.hash & (newCap - 1)] = e;` e是当前节点，newCap是新表的容量。

> 如果你想问为什么能使用 `hash & olcCap==0?`来决定是`newTab[j]` 还是 `newTab[j+oldCap]`这种方式来确定新的桶的下标的话。 那么原因就是扩容使用的是2次幂的方式，容量是原来容量的2倍.所以就可以使用 `hash & olcCap==0?`来判断了。

这个例子呢，演示了扩容过程中的链表的新增和扩容过程。再回头看resize方法,还有一种情况我们没有分析过.那就是

...
    else if (e instanceof HashMap.TreeNode) { 
        // 如果当前桶是棵红黑树
        ((HashMap.TreeNode<K, V>) e).split(this, newTab, j, oldCap);
    }
    ...

/** * 将原来树桶中的节点拆分为更低或更高的树桶,如果太小的话就转化成链表 * 只被resize方法调用 * * @param map hash表 * @param tab 表中的指定的桶的头结点(桶是一个棵树) * @param index 要拆分的hash表的节点 * @param bit the bit of hash to split on 要分裂的hash位 */
    final void split(HashMap<K, V> map, HashMap.Node<K, V>[] tab, int index, int bit) { 
        HashMap.TreeNode<K, V> b = this;
        // Relink into lo and hi lists, preserving order
        HashMap.TreeNode<K, V> loHead = null, loTail = null;
        HashMap.TreeNode<K, V> hiHead = null, hiTail = null;
        // lc代表的是原来的桶的元素的数量
        // hc代表新的桶中的元素的数量, 用来和UNTREEIFY_THRESHOLD比较决定是否要转换结构.
        int lc = 0, hc = 0;
        // 这里还是当做链表去处理，把桶内的元素重新散列。
        for (HashMap.TreeNode<K, V> e = b, next; e != null; e = next) { 
            next = (HashMap.TreeNode<K, V>) e.next;
            e.next = null;
            if ((e.hash & bit) == 0) { 
                if ((e.prev = loTail) == null)
                    loHead = e;
                else
                    loTail.next = e;
                loTail = e;
                ++lc;
            } else { 
                if ((e.prev = hiTail) == null)
                    hiHead = e;
                else
                    hiTail.next = e;
                hiTail = e;
                ++hc;
            }
        }
        // 散列完后，判断原来的桶(lo)和新的桶中的元素个数
        // 然后决定转换为树还是链表
        if (loHead != null) { 
            if (lc <= UNTREEIFY_THRESHOLD)
                tab[index] = loHead.untreeify(map);
            else { 
                tab[index] = loHead;
                if (hiHead != null) // (else is already treeified)
                    loHead.treeify(tab);
            }
        }
        if (hiHead != null) { 
            if (hc <= UNTREEIFY_THRESHOLD)
                tab[index + bit] = hiHead.untreeify(map);
            else { 
                tab[index + bit] = hiHead;
                if (loHead != null)
                    hiHead.treeify(tab);
            }
        }
    }

将树重新穿换成链表的过程就比较简单了：

/** * Returns a list of non-TreeNodes replacing those linked from * this node. */
    final HashMap.Node<K, V> untreeify(HashMap<K, V> map) { 
        HashMap.Node<K, V> hd = null, tl = null;
        for (HashMap.Node<K, V> q = this; q != null; q = q.next) { 
            // replacementNode:将TreeNode转成Node
            HashMap.Node<K, V> p = map.replacementNode(q, null);
            if (tl == null)
                hd = p;
            else
                tl.next = p;
            tl = p;
        }
        return hd;
    }

这里就是和红黑树相关的内容了,这里关键的是split调用了一个treeify的方法。这个方法同时也被treeifyBin调用了.所以treeify方法就和treeifyBin方法一块分享。  
顺便提一嘴,他们有如下的关系:

\[外链图片转存失败(img-YyYNbt4W-1567747065200)(./images/hashMap06-红黑树相关方法调用关系.png)\]  
其中蓝色的是红黑树的方法,黄色的是HashMap调用的方法。

#### treeifyBin ####

/** * 将链表转换成树。 * 替换给定hash值的索引处的桶的所有节点，如果表太小(table.length小于64),就调整大小.这里其实是对hash表的一种优化,防止因为表长度太小而转换成树,造成性能浪费 * @param hash 用于确定桶的位置。 */
    final void treeifyBin(HashMap.Node<K, V>[] tab, int hash) { 
        int n, index;
        // 链表的节点
        HashMap.Node<K, V> e;
        // 如果hash表为空或者hash表的长度小于最小化的树化容量(64)，这时会重调整大小。
        // 将容量扩大为原来的两倍。
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) { 
            resize();
        } else if ((e = tab[index = (n - 1) & hash]) != null) { 
            `HashMap.TreeNode<K, V> hd = null, tl = null;
            do { 
                // 构建一个树的节点。
                HashMap.TreeNode<K, V> p = replacementTreeNode(e, null);
                // 如果尾为null,说明这个节点是该桶中的第一个元素，
                // 所以要将其赋于头节点。
                if (tl == null) { 
                    hd = p;
                } else { 
                    // 将该节点放在尾节点后。
                    p.prev = tl;
                    tl.next = p;
                }
                // 当前节点作为尾节点。
                tl = p;
            } while ((e = e.next) != null);
    
            // 如果该桶中有元素，则进行树化。
            if ((tab[index] = hd) != null){ 
                hd.treeify(tab);
            }`
        }
    }

其实呢,这个`treeifyBin`方法还是做了一些将桶树化的前置操作,然后将装有`TreeNode`节点的桶交给了`treeify`方法去真正的转换为一棵红黑树。那我们接下来看下`treeify`方法。注意这个方法定义在`HashMap.TreeNode#treeify()`

##### treeify()方法 #####

/** * Forms tree of the nodes linked from this node. * 把该节点连接的所有节点组成一棵树。(树化的过程) */
    final void treeify(HashMap.Node<K, V>[] tab) { 
        // 该棵树的根节点。
        HashMap.TreeNode<K, V> root = null;
        // x是遍历的每个节点。
        for (HashMap.TreeNode<K, V> x = this, next; x != null; x = next) { 
            // 存下下一个节点。(指向下一个节点的指针)
            next = (HashMap.TreeNode<K, V>) x.next;
            x.left = x.right = null;
            // 对根节点就行赋值(无父节点,黑色)
            if (root == null) { 
                x.parent = null;
                x.red = false;
                root = x;
            } else { 
                K k = x.key;
                int h = x.hash;
                Class<?> kc = null;
    
                for (HashMap.TreeNode<K, V> p = root; ; ) { 
                    // dir,负值和0为左子树，正值为右子树。
                    int dir, ph;
                    K pk = p.key;
    
                    /*************判断节点在左子树还是右子树 -start***************/
                    // h为当前节点的hash值。
                    // p是父节点, ph是父节点的hash值。
                    if ((ph = p.hash) > h) { 
                        // 放在左子树
                        dir = -1;
                    } else if (ph < h) { 
                        // 放在又子树
                        dir = 1;
                    }
                    //如果当前节点和父节点的hash值相等:
                    //如果节点的key实现了Comparable, 或者 父节点和当前节点的key为一个。
                    else if ((kc == null && (kc = comparableClassFor(k)) == null) ||
                            (dir = compareComparables(kc, k, pk)) == 0) { 
                        // k是当前节点的key，pk是父节点的key
                        // 根据hashMap定义的规则,判断当前节点应该位于左子树还是右子树。
                        dir = tieBreakOrder(k, pk);
                    }
                    /*************判断节点在左子树还是右子树 -end***************/
    
                    HashMap.TreeNode<K, V> xp = p;
                    // p==null,代表着遍历到了叶子节点。
                    if ((p = (dir <= 0) ? p.left : p.right) == null) { 
                        // xp是当前节点的父节点。
                        x.parent = xp;
                        if (dir <= 0){ 
                            xp.left = x;
                        } else { 
                            xp.right = x;
                        }
                        // 平衡插入的红黑树(完成插入后，红黑树的性质可能被破坏,这里进行重新平衡)
                        root = balanceInsertion(root, x);
                        break;
                    }
                }
    
            }
        }
        //确保红黑树的根节点是桶的第一个节点。
        moveRootToFront(tab, root);
    }

在这里呢,有3个方法没有仔细去说明,分别是 tieBreakOrder(),balanceInsertion() 和 moveRootToFront(tab, root),注意，这三个方法在下面的PutTreeVal中也有调用.当然包括调整平衡的左旋(rotateLeft),右旋(rotateRight)方法.我们接着往下看吧。

##### balanceInsertion方法 #####

在说这个方法之前,先总结下红黑树变换的5条规则。

*  规则1: 红黑树为空树 ==> \{ 直接插入当前节点,节点涂为黑色。\}
 *  规则2: 插入节点的父节点是黑色 ==> \{ 直接插入当前节点.\}
 *  规则3: 当前节点的父节点是红色，并且叔叔节点是红色。==> \{ 父节点涂黑,叔叔节点涂黑,祖父节点涂红.\}
 *  规则4: 当前节点的父节点是红色,叔叔是黑色,当前节点是父节点的右子树. ==> \{ 当前节点的父节点作为新的当前节点,以新的当前节点左旋。\}
 *  规则5: 当前节点的父节点是红色,叔叔节点是黑色,当前节点是父节点的左子树. ==> \{ 父节点变为黑色，祖父节点变为红色，以祖父节点为支点右旋.\}  
    下面结合代码看HashMap是怎么实现上面这个5个规则的:

/** * 调整红黑树 * @param root 根节点 * @param x 当前节点 */
    static <K, V> HashMap.TreeNode<K, V> balanceInsertion(HashMap.TreeNode<K, V> root,
                                                            HashMap.TreeNode<K, V> x) { 
        x.red = true;
        // xp: 当前节点的父节点(父节点)
        // xpp: 当前节点的父节点的父节点(祖父节点)
        // xppl: 当前节点的父节点的父节点的左子树(叔叔节点)
        // xppr: 当前节点的父节点的父节点的右子树(叔叔节点)
        for (HashMap.TreeNode<K, V> xp, xpp, xppl, xppr; ; ) { 
            // 规则1
            if ((xp = x.parent) == null) { 
                x.red = false;
                return x;
            }
            // 父节点为黑色 或者祖父节点为空==>规则2
            else if (!xp.red || (xpp = xp.parent) == null) { 
                return root;
            }
    
            // 父节点是左子树
            if (xp == (xppl = xpp.left)) { 
                // 父节点是左子树,且祖父节点存在右子树(叔叔节点为右子树)，并且叔叔为红色。 ==> 父节点是右子树时的性质1.
                if ((xppr = xpp.right) != null && xppr.red) { 
                    // 叔叔节点涂黑
                    xppr.red = false;
                    // 父节点涂黑
                    xp.red = false;
                    // 祖父节点涂红
                    xpp.red = true;
                    // 以祖父节点为新的当前节点
                    x = xpp;
                }
                // 祖父节点没有右子树或者有右子树,颜色为黑色。
                else { 
                    // 当前节点是父节点的右子树==> 规则4
                    if (x == xp.right) { 
                        // 左旋
                        root = rotateLeft(root, x = xp);
                        // 设置祖父节点要么为空要么是父节点。
                        xpp = (xp = x.parent) == null ? null : xp.parent;
                    }
                    // 规则5
                    if (xp != null) { 
                        // 父节点涂成黑色
                        // 此时xp可能为root.
                        xp.red = false;
                        // 如果xp不是root的时候。
                        if (xpp != null) { 
                            // 祖父节点涂成红色,右旋。
                            xpp.red = true;
                            root = rotateRight(root, xpp);
                        }
                    }
                }
            }
    
            // 父节点不是左子树==> 父节点是右子树。
            else { 
                // 叔叔节点(祖父节点的左子树),叔叔为红色 ==> 规则3
                if (xppl != null && xppl.red) { 
                        // 叔叔涂黑
                    xppl.red = false;
                    // 父节点涂黑
                    xp.red = false;
                    // 祖父节点涂红
                    xpp.red = true;
                    // 以祖父节点为新的当前节点
                    x = xpp;
                }
                // 祖父节点没有右子树或者有右子树,颜色为黑色。 ==> 规则4
                else { 
                    // 当前节点是左子树
                    if (x == xp.left) { 
                        // 右旋
                        root = rotateRight(root, x = xp);
                        // 设置祖父节点要么为空要么是父节点。
                        xpp = (xp = x.parent) == null ? null : xp.parent;
                    }
                    // ==> 规则5
                    if (xp != null) { 
                        xp.red = false;
                        // 如果有祖父
                        if (xpp != null) { 
                            // 祖父节点涂成红色,右旋。
                            xpp.red = true;
                            root = rotateLeft(root, xpp);
                        }
                    }
                }
            }
        }
    }

##### rotateLeft 左旋 #####

这里的代码不能用语言描述,真的是只能意会不能言传啊。

static <K, V> HashMap.TreeNode<K, V> rotateLeft2(HashMap.TreeNode<K, V> root, HashMap.TreeNode<K, V> p) { 
                HashMap.TreeNode<K, V> r, pp, rl;
                // p是父节点
        if (p != null && p.right != null) { 
            // 右孩子
            r = p.right;
            // 右孩子有左孩子的话.
            if (r.left != null) { 
                // 右孩子变成右孩子的左孩子。即rl变成了p的右孩子。
                p.right = r.left;
                rl = r.left;
                rl.parent = p;
                // 注意此时r没有关联。
            }
            pp = p.parent;
            // 如果p没有有父节点的话。
            if (p.parent == null) { 
                // 将r的父节点置为null
                r.parent = p.parent;
                // 颜色涂成黑色，并且r就是根节点。
                (root = r).red = false;
            }
            // 如果p节点有父节点，并且p是左子树的话
            else if (pp.left == p) { 
                // 将祖父节点的左子树置为r,
                pp.left = r;
            } else { 
                // 将祖父节点的右子树置为r,
                pp.right = r;
            }
            // 将r和p连接起来。
            r.left = p;
            p.parent = r;
        }
        return root;
    }

注意下,这里的代码是我修改之后，JDK的源码看起来很精简，理解起来,啧啧啧。

MD,来张图:

\[外链图片转存失败(img-HtJlVEms-1567747065203)(./images/HashMap07-左旋的过程.png)\]

这里假设右孩子是有左孩子的。如果没有的话，那就直接去掉绿色的rl就好了。

##### rotateRight #####

右旋的过程同理:

static <K, V> HashMap.TreeNode<K, V> rotateRight(HashMap.TreeNode<K, V> root,
                                                             HashMap.TreeNode<K, V> p) { 
        HashMap.TreeNode<K, V> l, pp, lr;
        if (p != null && (l = p.left) != null) { 
            if ((lr = p.left = l.right) != null)
                lr.parent = p;
            if ((pp = l.parent = p.parent) == null)
                (root = l).red = false;
            else if (pp.right == p)
                pp.right = l;
            else
                pp.left = l;
            l.right = p;
            p.parent = l;
        }
        return root;
    }

这图啊，有空再做吧。今天太累了。

还有一个方法:

##### moveRootToFront #####

/** * Ensures that the given root is the first node of its bin. * // 确保红黑树的根节点是桶的第一个节点。 * 为什么不直接将tab[index]==root? 是为了树重新转换成链表的时候使用的。 */
    static <K, V> void moveRootToFront(HashMap.Node<K, V>[] tab, HashMap.TreeNode<K, V> root) { 
        int n;
        if (root != null && tab != null && (n = tab.length) > 0) { 
            int index = (n - 1) & root.hash;
            HashMap.TreeNode<K, V> first = (HashMap.TreeNode<K, V>) tab[index];
            // 判断第一个节点和root是不是相等的,判断的是地址。
            if (root != first) { 
                HashMap.Node<K, V> rn;
                tab[index] = root;
                HashMap.TreeNode<K, V> rp = root.prev;
    
                if ((rn = root.next) != null) { 
                    // root的后一个节点的指向前的指针指向root的前一个节点。
                    ((HashMap.TreeNode<K, V>) rn).prev = rp;
                }
    
                if (rp != null) { 
                    // root的前一个节点的指向后的指针指向root的后一个节点。
                    rp.next = rn;
                }
    
                if (first != null) { 
                    // 第一个元素的前指针指向root
                    first.prev = root;
                }
                // root的后向指针指向first
                root.next = first;
                // root的前向指针置为null
                root.prev = null;
            }
            // 递归不变检查
            assert checkInvariants(root);
        }
    }

#### putTreeNode ####

final HashMap.TreeNode<K, V> putTreeVal(HashMap<K, V> map, HashMap.Node<K, V>[] tab,
                                                    int h, K k, V v) { 
        Class<?> kc = null;
        boolean searched = false;
        HashMap.TreeNode<K, V> root = (parent != null) ? root() : this;
        for (HashMap.TreeNode<K, V> p = root; ; ) { 
            int dir, ph;
            K pk;
            /***************判断 左右子树 ******************/
            if ((ph = p.hash) > h) { 
                dir = -1;
            } else if (ph < h) { 
                dir = 1;
            } else if ((pk = p.key) == k || (k != null && k.equals(pk))) { 
                return p;
            } else if ((kc == null &&
                    (kc = comparableClassFor(k)) == null) ||
                    (dir = compareComparables(kc, k, pk)) == 0) { 
                if (!searched) { 
                    HashMap.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;
                }
                dir = tieBreakOrder(k, pk);
            }
    
            /***************判断 左右子树 end******************/
    
            HashMap.TreeNode<K, V> xp = p;
            if ((p = (dir <= 0) ? p.left : p.right) == null) { 
                HashMap.Node<K, V> xpn = xp.next;
                HashMap.TreeNode<K, V> x = map.newTreeNode(h, k, v, xpn);
                if (dir <= 0)
                    xp.left = x;
                else
                    xp.right = x;
                xp.next = x;
                x.parent = x.prev = xp;
                if (xpn != null)
                    ((HashMap.TreeNode<K, V>) xpn).prev = x;
                // 这里比较重要了，不过我们在treeify中已经说过了。
                moveRootToFront(tab, balanceInsertion(root, x));
                return null;
            }
        }
    }

这样，HashMap的新增过程我们就处理完了。

### HashMap删除方法 HashMap\#remove() ###

/** * 从map中删除指定的key,如果key存在的话 * @param key key whose mapping is to be removed from the map * @return value 如果key存在,返回key对应的Value,如果不存在返回null */
    public V remove(Object key) { 
        HashMap.Node<K, V> e;
        return (e = removeNode(hash(key), key, null, false, true)) == null ?
                null : e.value;
    }

其中计算hash值的方法还是和之前的一样。

#### removeNode ####

/** * Implements Map.remove and related methods. * 实现Map.remove相关的方法 * @param hash hashCode * @param key key * @param value value * @param matchValue 如果是true，仅在value相等的时候删除。 * @param movable 如果为false，则在删除节点的时候不移动其他节点。 * @return 返回删除的节点 */
    final HashMap.Node<K, V> removeNode(int hash, Object key, Object value,
                                        boolean matchValue, boolean movable) { 
        HashMap.Node<K, V>[] tab;
        HashMap.Node<K, V> p;
        int n, index;
        if ((tab = table) != null && (n = tab.length) > 0 &&
                (p = tab[index = (n - 1) & hash]) != null) { 
            HashMap.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;
            else if ((e = p.next) != null) { 
                if (p instanceof HashMap.TreeNode) { 
                    // 找到红黑树中的节点
                    node = ((HashMap.TreeNode<K, V>) p).getTreeNode(hash, key);
                } else { 
                    // 删除链表中的节点1: 查找到节点的位置。
                    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)))) { 
                if (node instanceof HashMap.TreeNode) { 
                    // 删除红黑树的节点
                    ((HashMap.TreeNode<K, V>) node).removeTreeNode(this, tab, movable);
                }else if (node == p) { 
                    // 桶中只有当前的节点。
                    tab[index] = node.next;
                }else { 
                    // 链表中节点的删除
                    p.next = node.next;
                }
                // 修改次数+1
                ++modCount;
                --size;
                afterNodeRemoval(node);
                return node;
            }
        }
        return null;
    }

还有一个最难理解的方法落在了红黑树的移除上了。

#### HashMap\#TreeNode\#removeTreeNode ####

还是先看下红黑树的删除是怎么回事。

在删除方法调用之前必须要有存在的给定节点。  
这比典型的红黑删除代码更混乱，因为我们不能将内部节点的内容与叶子后继交换，后者由遍历期间可独立访问的“下一个”指针固定。 所以我们交换树链接。 如果当前树似乎有太少的节点，则红黑树(bin)将转换回普通的链表(普通bin). （测试会在2到6个节点之间触发，具体取决于树结构）。  
上面是 removeTreeNode方法的解释.说实话，没理解…

HashMap的删除不同于普通的红黑树的删除, 因为它其中还维护了，一个链表的指向. HashMap采用的是将树中的两个节点进行换位, 颜色也要进行互换，来保证红黑树的平衡,并不改变二者在链表中的位置,互换后,删除节点此时的左子树是空的，将问题转换成了对左子树为空的节点的删除。

有一个简单的问题,千万不要弄混了,就是TreeNode中要删除的节点是谁??

删除的签名是这样的:`final void removeTreeNode(HashMap<K, V> map, HashMap.Node<K, V>[] tab,boolean movable)`,并没有传 TreeNode啊?是不是??

干吗呢！大兄嘚. 要删除的节点是：this啊。我们现在走到了TreeNode内部了!! 它本身就是要被删除的节点啊。

好了，那我现在要告诉你: 删除自己！

HashMap删除红黑树的节点，实际上就是 TreeNode自己删除自己。那么它是怎么删的呢?

它分成了三步:

*  1.将删除节点从双链向链表中删除.
 *  2.将删除节点与其右子树最小节点互换,之后平衡树
 *  3.将树根节点，移动到`tab[index]`指针处

final void removeTreeNode(HashMap<K, V> map, HashMap.Node<K, V>[] tab,
                                      boolean movable) { 
            // 注意了： 这个时候被删除的节点是谁??
            // 是this.
            int n;
            if (tab == null || (n = tab.length) == 0)
                return;
    
            // 找到对应的索引(确定对应桶的位置), n 是当前表的长度
            int index = (n - 1) & hash;
            // first: 第一个树节点(当前为父节点),root，父节点。rl:
            HashMap.TreeNode<K, V> first = (HashMap.TreeNode<K, V>) tab[index], root = first, rl;
            // succ:下一个节点(链表的指向)。pred, 前一个节点。
            HashMap.TreeNode<K, V> succ = (HashMap.TreeNode<K, V>) next, pred = prev;
    
            if (pred == null) { 
                // 前一个为空时，即当前接是父节点:(被删除的节点是根节点)
                tab[index] = first = succ;
            } else { 
                // 否测,前一个节点的下一个执行当前节点的下一个。(意会)
                pred.next = succ;
            }
    
            if (succ != null) { 
                // 当前节点的后节点不为null,后一个节点的前节点指向当前节点的前节点(意会)
                succ.prev = pred;
            }
    
            if (first == null) { 
                // 如果删除当前节点，该桶变成了null的。就直接返回
                return;
            }
    
            if (root.parent != null) { 
                // 重置table[index]处为树的根节点。
                root = root.root();
            }
    
            // PS: 说点没用， JDK除了部分ifelse不加括号之外，
            // 其实换行，还是用的挺多的，看起来也挺舒服的。
            // 值得借鉴
            if (root == null
                    || (movable && (root.right == null
                    || (rl = root.left) == null
                    || rl.left == null))) { 
                // 树太小了，将树转换成链表
                tab[index] = first.untreeify(map);  // too small
                return;
            }
            /*****注意！！！ 此时已经从双向链表中删除了, 第一步走完。******/
    
            // p是待删除的节点，pl当前节点的左孩子节点,pr当前节点的右孩子节点,replacement,用来交换的节点。
            HashMap.TreeNode<K, V> p = this, pl = left, pr = right, replacement;
            if (pl != null && pr != null) { 
    
                // s为右子树的最小的节点,sl为左子树(一下五行和源码略有不同)
                HashMap.TreeNode<K, V> s = pr, sl = s.left;
                while (sl != null) {  // find successor
                    s = sl;
                    sl = s.left;
                }
    
                // 交换颜色
                boolean c = s.red;
                s.red = p.red;
                p.red = c; // swap colors
    
                // 交换节点连接
                HashMap.TreeNode<K, V> sr = s.right;
                HashMap.TreeNode<K, V> pp = p.parent;
                // pr是当前节点的右孩子节点
                // s是当前节点的右子树的最小的节点
                // p的右子树,只有s这一个节点
                if (s == pr) {  // p was s's direct parent
                    p.parent = s;
                    s.right = p;
                } else {  //
                    // sp： 最小节点的父节点
                    HashMap.TreeNode<K, V> sp = s.parent;
                    if ((p.parent = sp) != null) { 
                        if (s == sp.left)
                            sp.left = p;
                        else
                            sp.right = p;
                    }
                    if ((s.right = pr) != null)
                        pr.parent = s;
                }
                // 置null孩子。
                p.left = null;
                if ((p.right = sr) != null) { 
                    sr.parent = p;
                }
                if ((s.left = pl) != null) { 
                    pl.parent = s;
                }
                if ((s.parent = pp) == null) { 
                    root = s;
                } else if (p == pp.left) { 
                    pp.left = s;
                } else { 
                    pp.right = s;
                }
    
                // 确定要交换的节点完毕，交换节点
                if (sr != null) { 
                    replacement = sr;
                } else { 
                    replacement = p;
                }
            } else if (pl != null) { 
                // 当前树只含有左子树
                replacement = pl;
            } else if (pr != null) { 
                // 当前树，只有又子树
                replacement = pr;
            } else { 
                // 无孩子
                replacement = p;
            }
    
            if (replacement != p) { 
                HashMap.TreeNode<K, V> pp = replacement.parent = p.parent;
                if (pp == null)
                    root = replacement;
                else if (p == pp.left)
                    pp.left = replacement;
                else
                    pp.right = replacement;
                p.left = p.right = p.parent = null;
            }
    
            // 是否要进行重平衡树?
            HashMap.TreeNode<K, V> r = p.red ? root : balanceDeletion(root, replacement);
    
            // 在平衡后删除该节点
            if (replacement == p) {   // detach
                HashMap.TreeNode<K, V> pp = p.parent;
                p.parent = null;
                if (pp != null) { 
                    if (p == pp.left)
                        pp.left = null;
                    else if (p == pp.right)
                        pp.right = null;
                }
            }
            // 参数moveable控制是否删除节点后确保树的根节点为链表的头节点
            if (movable) { 
                // 将树根节点，移动到tab[index]指针处
                moveRootToFront(tab, r);
            }
        }

这样呢，整个删除过程就完成了。  
用官方中的话，比较混乱。尤其是涉及到红黑树的删除，这部分内容。还是需要好好消化，消化的。

下面我们还剩下两个内容：修改和查找

### HashMap的修改方法 ###

留坑~

### HashMap的查找方法 ###

留坑~

## 问题解答 ##

*  如果我的HashMap的初始大小设置为`[3|9|12]`,第一次扩容的时候,容量变为了多少? 是如何进行扩容的?
 *  (有毒的问题)假设Hash表的长度是32,已知某一个bin中的链表长度为7,如果新增一个元素还是在该bin中的时，会进行什么操作？ `resize`还是`treeifyBin`? 假设完成这个操作后该bin中元素数量没变,又新增一个元素还是到该bin中，这时进行什么操作?

## 总结 ##

*  表中允许null的键和null值。
 *  线程不同步,
 *  不保证元素的顺序。

## 网上常见面试问题汇总以及参考解答 ##

## 冷门知识点 ##

*  failFast机制。

## JDK变更历史说明 ##

## 课后娱乐 ##

*  java实现红黑树
 *  自定义实现hashMap。

## 参考文档&答谢 ##

## 感受 ##

*  注释: 新字段要加注释标注此字段的作用,该字段是什么含义。

--------------------

阅读之前记录

1.图解。遇到问题，画图说明。  
2.一定要有自己的理解。  
3.对比其他版本JDK。

如果记得还行的话，就关注下 **公众号** 呀 ，看最新看详细的文章！  
![在这里插入图片描述][20190909222856113.jpg]

[poisson]: http://en.wikipedia.org/wiki/Poisson_distribution
[20190909222856113.jpg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/b1317d67dc72411891af3c5824a87f6f.jpg