[数据结构与算法]HashMap源码分析，Java中的符号表

前言

本篇文章主要围绕JDK8的符号表实现HashMap的源码来讲的，但是如果要读懂HashMap实现的原理和思想，必不可少要对符号表这种数据结构有所了解。所以在文章的开头，先是给读者介绍了什么是符号表之后，才开始分析源码，这样理解起来比较通透。如果读者时间有限或者对符号表已经有过了解，可以直接跳转到二、HashMap源码分析即可。

一、什么是符号表？

符号表是一种能够将一个键和值关联起来的key-value型数据结构，并且至少支持两种操作，一是插入put。二是查找get，即根据key找到对应的value。符号表的应用场景很广泛，(表1.1列出了符号表的几种应用场景)所以能高效的插入和查找是衡量一个符号表实现的重要指标。可以说在量子计算机或图灵机没有实现之前，如果没有高效的符号表实现，很多应用都将不可能。下面将给大家讲解几种符号表。

1. 链表符号表

基于单向链表实现的链表符号表，它的每个结点都有三个指针：key、value、next。put操作会将next指向新插入的结点。get操作需要顺序查找，因为put操作也需要查找key是否存在，所以它效率极差，get和put操作在最坏情况下都可能需要N¹ （注意：N右边的不是次方而是注脚）次比较。图1.1展示了一个简单的链表。

2. 有序符号表

有序符号表使用两个平行的数组来实现符号表。一个是key[]，一个是value[]。在put操作时要保证key的有序性，所以在有序性的基础上可以使用二分查找法来提高get操作的效率，能保证在lgN²次比较内完成。它的缺点是put操作需要维护数组的有序性，开销很大，最坏情况可能需要操作N²次。它们的示意如图1.2所示

3. 二叉查找树

二叉查找树又名2-树，是计算机科学中最重要的算法之一。它每个结点拥有两个指针：left、right。其中left指针指向的结点都小于当前结点，right下的结点都大于当前结点。每个结点都是一个二叉查找树，而且必须要有一个根结点root。简单的结构如图1.3所示。

• get：用get操作查找一个key时，先从root结点开始，如果key大于root的key则从右子树开始找，小于则从左子树开始找，如果碰到了指向NULL结点的指针就说明需要查找的key不在树中。
• put：在插入一个结点时先要执行一遍和get操作，以找到一个NULL结点，然后将原本指向NULL结点的指针指向插入的结点。
• removeMin：删除最小结点很简单，从root结点开始不断的向左找，如果有一个结点的left指针为空就将本来指向这个结点的指针指向这个结点的右子树³。
• remove：remove操作对于上面所讲的符号表实现比较简单，但是二叉查找树是相对比较复杂的。如果被删除结点只有一个子结点时，操作和removeMin或removeMax⁴差不多。当被删除结点有两个子结点时，就因为需要保证二叉查找树的性质而需要更多的操作。假设被删除结点的指针名为d，它的操作过程如下：临时保存结点指针d为temp，将d指向temp的右子树下最小的结点(代表继承者)，将d的right指针指向temp右子树中第二小的结点，最后将d的left指向temp的左子树。

二叉查找树在平均情况下能保证树高为lgN，但是最坏情况下可能会变成线性表。例如每次插入的结点都大于上一次插入的结点(如图1.3.1)。根据算法第四版⁴中的测试数据，随机构造的二叉查找树的高度都小于3lgN。

4. 2-3树

2-3树是基于二叉查找树思想的平衡查找树，它的出现是为了防止二叉查找树的最坏情况发生，能保证树的高度接近lgN。在2-3树中有两种结点：2-结点和3-结点，2-结点的意思和二叉查找树一样，包含一个key和两个链接。3-结点则包含两个键三个链接，从左到右的链接分别表示小于两个key、在两个key中间、大于两个key。简单的2-3树示例如图1.4所示。一颗完美平衡的2-3查找树中所有的空链接到根结点的距离都应该是相同的。(关于如何保证这个原则涉及的操作很多，而且HashMap中的红黑树没有基于2-3树来实现，笔者在这里不再赘述了)

5. 左偏红黑二叉查找树

左偏红黑二叉查找树⁵也是一种平衡查找树。基于2-3树和二叉查找树的思想，左偏红黑树中也有3-结点和2-结点，只不过3-结点表现形式不一样。它的结点分成红结点和黑结点，红结点将两个2-结点链接起来和它的父结点一起组成一个3-结点(如图1.5，为了便于理解，将NULL结点也画了出来)。如果将红结点和它的父结点画平，它和2-3树的3-结点看起来就很像了(把图1.5.1 和图1.4中的3-结点对比着来看)。黑结点则是2-3树中的普通结点。一颗正确的左偏红黑树需要满足以下几点

1. 红结点均为左链接；
2. 没有任何一个结点同时和两条红结点相连；
3. 不能有两个连续的红结点
4. 该树是完美黑色平衡的，即任意空结点到根结点的路径上的黑结点数量相同

满足这样定义的左偏红黑树和相应的2-3树是一 一对应的。除了结点多了Color这个属性以外，它的结点都可以看作是二叉查找树的结点，所以可以支持二叉查找树的所有操作。只用在原来的基础上要改动插入方法和删除方法，其他的例如查找、排名、查找小于指定键的最大值等都和二叉查找树相同。具体的细节我们放到讲解HashMap源码的时候再讲，大家理解起来会更加方便。由于左偏红黑树自身的性质，它平均的树高在lgN左右，最坏情况是2lgN。

6. 散列表

散列表很好理解，它就是一个数组。假设人类哪天实现了图灵机，并且键又是整数，那么我们可以直接将键作为索引插入数组中。下次要查找这个键对应的值时，直接通过数组下标就可以获取到结点。当然现实世界里物理存储是有限的，必然就会碰到N-1个键要放入N个空间里的抽屉原理问题。然后符号表在应用的时候谁也不能保证键是什么类型，所以在计算索引时我们会使用Hash算法。咱先不管Hash算法内容是什么，知道它会返回一个整型值就行了。假设数组大小是M，我们要将某个键放入数组中，先是计算出键的Hash值，然后用取余数法得到数组下标。在Java中取余操作符是%，例如Hash % M。计算出下标后直接插入数组即可。查找一个键也很简单，同样使用Hash % M计算出下标然后array[index]拿到结点或元素。一个好的Hash算法需要满足以下几点

• 一致性： 等价的键必然产生相等的Hash值
• 高效性：计算简便，快速
• 均匀性：均匀的散列所有值

在Java的API中大多数都实现了Object类的hashCode方法，我们用String类的hashCode方法来举例

public int hashCode() {
    //缓存了hash的计算结果,防止重复计算
    int h = hash;
    if (h == 0 && value.length > 0) {
        char val[] = value;

        //使用horner方法 将每个char当成一个31进制数的一位 
        //这样的hashCode的结果就是一个31进制值
        for (int i = 0; i < value.length; i++) {
            h = 31 * h + val[i];
        }
        hash = h;
    }
    return h;
}

horner方法链接
因为抽屉原理，总会出现多个不同的hash值计算到同一个下标里。比如有两个hash值1000和100，数组长度是10，它们%10的结果都是0，都会放入0下标中。由此就引出了散列表的碰撞问题，为了解决这个问题有两种方法

1. 拉链法
   该方法把数组的元素类型设为链表，碰撞到同一个下标的结点都放入对应下标的链表中(结构如图1.6所示)。get操作先根据hash计算index，然后获取到index的链表，如果key不相等则在next结点中继续找，找到了返回没找到返回NULL。数组中结点数量N(注意：这里不单指数组中链表的数量，而是非空结点的总数量)和数组大小M的比N/M达到某个值时可以对数组进行动态扩容，以提升散列表的性能。
   

2. 线性探测法
   线性探测法的原理是：如果发生碰撞则将下标往后移(如果到了底部就回到0下标继续)直到找到空结点为止，然后将结点插入该空结点。这种方法有个问题就是，如果数组中没有空结点了会发生死循环，而且空结点原来越少时查找或插入都会很慢(因为键簇的增长)。根据概率论，线性探测表中N/M的比值最好在1/8到1/2之间性能是最好的⁶，所以在put或remove操作时进行相应的数组扩容或缩小即可。由于线性探测表本身的性质，它会造成很多空间碎片存在，但是对于它的性能来说这点很值得。

二、HashMap源码分析

首先说结论，JDK8中的HashMap使用的是散列表中的拉链法外加红黑树。与HashMap不同的是HashTable没有使用红黑树，并且是线程安全的(使用synchronized管程)，HashTable还是使用的是取余运算计算下标，HashMap使用的是掩码运算。请注意，源码分析中的常量、变量和方法等，并不是按照文章的先后顺序关联的，而是平行的，并且需要结合代码块中的注释一起看，所以如果在开头看不明白一些方法，也许在看完下文后就能看明白了。Let’s get started！

1.常量及成员变量分析

列出了经常需要使用的字段和两个简单的方法

/**
 * 数组默认大小是16 数组容量必须是2的次幂数
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

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

/**
 * 默认加载因子，即结点数量N与数组大小M的比值 HashMap设的是75%
 * 达到这个阈值时可能会发生数组扩容
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

/**
 * 当单个链表的数量大于2小于TREEIFY_THRESHOLD时
 * 可能会将链表转为红黑树
 */
static final int TREEIFY_THRESHOLD = 8;

/**
 * 红黑树的大小达到这个阈值时会再转回链表
 */
static final int UNTREEIFY_THRESHOLD = 6;

/**
 * 除了判断单个链表的大小外还会判断数组中的结点数量
 * 见下文resize方法
 */
static final int MIN_TREEIFY_CAPACITY = 64;

/**
 * 用来存储结点的数组，也就是散列表
 */
transient Node<K,V>[] table;

/**
 * 数组中所有的结点数（不是元素数)
 */
transient int size;

/**
 * 防止在遍历HashMap时修改内容导致的编码错误
 * 或多线程一个在读一个在写
 * 这个modCount在很多集合或列表的API中都能看到
 */
transient int modCount;

/**
 * 需要进行数组扩容的阈值 (capacity * load factor)
 */
int threshold;

/**
 * 加载因子 size/table.size()的比
 */
final float loadFactor;

//返回结点数量
public int size() {
    return size;
}

//HashMap结点数是不是0
public boolean isEmpty() {
    return size == 0;
}

2. 方法分析

在下面的讲解中，为了文章的结构清晰，我会先把关于红黑树的部分抽出来，在把HashMap一些方法的主体讲清楚之后，再讲红黑树的部分。建议读者在看完主体方法和红黑树部分后，反过来再看主体的方法，以加深理解。

2.1 构造方法

	/**
     * 该方法接受一个initialCapacity(容量)和loadFactor(加载因子)
     * 进行初始化HashMap对象
     */
    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;
        //tableSizefor Method is so funcy
        this.threshold = tableSizeFor(initialCapacity);
    }

    /**
     * 接受一个initialCapacity，并使用默认加载因子
     */
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }

    /**
     * 默认容量，默认加载因子
     */
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

在代码块1.0的第一个构造方法中有一个非常有趣的方法，tableSizeFor。它的作用是获取给定容量大小最近的2的次幂数(HashMap的容量必须是2的次幂数)，按照正常的逻辑应该直接取对数就行了，但是写这个方法的人却用了一种非常聪明的方法，感兴趣的读者可以点击链接了解下tableSizeFor方法图解。

2.2 get方法

按照本篇文章的惯例，我们先从查找这个经典操作入手，逐步分析出HashMap的庐山真面目

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

get方法接受一个Object类型的key，目的是通过key来查找表中的值。
代码块1.1的第2行出现了一个Node型变量，他是HashMap中的链表结点，结构如代码块1.2所示(为了节省篇幅代码块1.2中只列出了Node的成员变量)。get方法实际上调用了getNode方法(第一个参数调用了hash方法，具体内容这里先略过，在下文中会讲)，它的内容如代码块1.3所示。

/**
 * 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> {
	//key生成的hash值
    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;
    }
}

getNode接受一个key和key对应的hash值，在代码块1.3的第9行的if语句中first = tab[(n - 1) & hash]就是计算hash值下标的代码，首先n是数组的容量，它必须是2的次幂数，以默认容量16为例，它转为二进制是0001 0000，16-1后的二进制是0000 1111也就是15，n-1有两个作用，一个是保证了数组下标不会越界，二是n-1代表了一个二进制掩码，把(n-1) & hash就是提取hash码二进制的低N位，比如15对应的掩码是低4位，这样计算出来的效果和使用%运算是差不多的。

final Node<K,V> getNode(int hash, Object key) {
	//数组
    Node<K,V>[] tab; 
	//first：根据hash值计算的下标下的头结点
    Node<K,V> first, e; 
    //n：数组大小
    int n; K k;
    //判断table是否为Null
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) {
		//如果链表头结点就是该key，则说明没有发生过碰撞，直接返回
        if (first.hash == hash && // always check first node
            ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
        	//如果结点时红黑树，则调用红黑树查找结点的方法
            if (first instanceof TreeNode)
                return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            //如果是链表则根据next指针顺序查找
            do {
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

而这里引申出一个问题就是，参与计算的hash码不管多大，只有低N位能参与计算，其二进制高位都是无效的。这样会导致散列碰撞的几率很高，所以HashMap会对对象返回的hashCode再进行一次hash计算。其内容如代码块1.4所示，它就是调用getNode方法时使用的hash方法，该方法实际上是一个扰动函数。hashCode是一个int型的值，在Java中int占32位，于是hash方法把32位数的高16与低16位进行一次^(异或)运算，让高16位也参与计算，这样的hashCode分布更均匀。笔者在研究这里时看过一个测试报告，在掩码为9位时，使用扰动函数后的碰撞几率减少了10%左右(如图1.7)。

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

接着回到代码块1.3第9行的if判断，内容是：用hash计算出来的数组的index的第一个结点与key进行对比，看是否相等，不是则判断还没有下一个结点，有就继续判断结点类型是红黑树结点还是普通链表结点，对其进行对应的查找操作。如果上述的操作都没有找到该结点，则返回NULL。注意：不管Node的类型是TreeNode还是它自己，在HashMap中它们之间都是可以互相转换的，只不过TreeNode多了些指针，组成了红黑树(getTreeNode是红黑树查找结点的方法，放在后面讲)。

在讲完了get方法的的内容后，如果读者有哪里不明白或者有更好的理解，欢迎在评论区留言，笔者也希望收到更多宝贵的建议。

接下来我们要讲解的便是第二个符号表最重要的操作之一：put操作

2.3 put方法

如代码块1.5所示，put方法实际上调用的putVal方法(代码块1.6)，该方法接受一个（key、key的hash值、key对应的value）(其他两个参数可以忽略)。然后将key-value插入table中，在插入之前首先会进行查找，找到了就替换value，并返回oldvalue，没有找到才可以插入。

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

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为空 则进行resize 初始化一个默认容量的数组
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        /**
         * 下标i = (n - 1) & hash是如何得到的？
         * hash = obj.hashCode() ^ obj.hashCode() >>> 16
         * hash是一个扰动函数 可以增加原hashCode的随机性，减少碰撞的几率
         * n - 1 是 table容量的最大值 转换成二进制 也就是二进制掩码 binary mask
         * n - 1 & hash 能计算到 0 到 n - 1 中的 任意n
         */  
        //根据key进行hash 看是否对应的数组下标已经有元素 没有直接插入
        if ((p = tab[i = (n - 1) & hash]) == null)
        	//newNode就是创建了个结点
            tab[i] = newNode(hash, key, value, null);
        else {
        	//e代表需要插入的结点已存在 e=这个已存在的结点
            Node<K,V> e; 
            K k;
            //如果计算到的下标已经有元素 并且key也是相等的
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            //key不相等则判断该元素是否是一个红黑树,是就往里面增加树节点
            //这个的p就是红黑树的root结点
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            //key不相等 也不是红黑树 则是链表
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        //jdk8采用的是尾插法
                        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 = e;
                }
            }
            //HashMap中已存在key相等的元素 替换 并且返回老值
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                //这里判是否需要替换还是忽略 默认是替换
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                //忽略这个方法    
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        //结点插入后是否需要扩容
        if (++size > threshold)
            resize();
		//LinkedHashMap使用了这个方法,HashMap没有使用
        afterNodeInsertion(evict);
        return null;
    }

2.4 resize数组扩容方法

在代码块1.6中我们看到有一个叫resize的扩容方法，它会被其他很多地方触发到，其具体内容如代码块1.7所示。扩容时一般将容量扩容原来的两倍⁷，而且在扩容后要将原来数组的结点rehash并放入扩容后对应下标的链表或红黑树中。

	 /**
	 * 在进行数组扩容的同时 要保证通过 (table.length - 1) & hash 还能计算出正确的下标
     * @return the table
     */
    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) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            //将newCap 扩容为oldCap的两倍 newThr同
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
        //当使用代码块1.0中的第一个构造方法初始化HashMap时
		//oldThr = threshold = tableSizeFor(initialCapacity)
        else if (oldThr > 0) // initial capacity was placed in 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) {
            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) {
                    oldTab[j] = null;
                    //该元素非链表 非树 直接插入进新数组
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    //如果是树 则调用split方法
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        //是链表
                        //loHead - loTail 是不会因数组变化而变化下标的元素
                        Node<K,V> loHead = null, loTail = null;
                        //hiHead - hiTail 是会因为数组变大 而变化下标的元素
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
                            /*
                                以原数组容量作为掩码进行与操作 数组容量表现为2的次幂数 所以 二进制是 100000...的形式
                                扩容是把二进制左移了一位 比如 16 -> 32 当hash对原数组容量为1的位为1时
                                就会受到扩容后的数组容量影响从而产生偏移，偏移量刚好是原数组下标+原数组容量
                             */
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            //不是0代表该hash计算的下标会因为容量变大而产生偏移 偏移量刚好是 原容量的大小
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        //把扩容后还在该下标下的元素 继续放在新数组对应的下标下
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            //偏移原容量大小 就可得到该元素在新数组中的下标
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

对于数组中存放链表，并对链表进行get或者put、remove操作来说，代码实现都很简单。但是对于在put过程中将结点转为红黑树的treeifyBin、和直接往TreeNode类结点(红黑树结点)中插入结点的putTreeVal、在get操作中的getTreeNode、在remove操作removeTreeNode方法来说操作都很复杂。特别是removeTreeNode方法，实际上比红黑树的删除更复杂⁸。

2.5 remove方法

remove方法和put、get都一样，实际上调用的是内部的方法。remove之前也应该要查找key对应的结点是否存在，存在才会去删除，不存在则返回NULL。

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

final Node<K,V> removeNode(int hash, Object key, Object value,
                               boolean matchValue, boolean movable) {
        Node<K,V>[] tab; Node<K,V> p; int n, index;
        //对应hash的下标应该存在元素，否则直接返回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;
            //拿到的第一个元素就hash值相同 key相等 匹配成功
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                node = p;
            //没有匹配成功就继续找
            else if ((e = p.next) != null) {
                //是树节点就在树中找
                if (p instanceof TreeNode)
                    node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
                else {
                    //在链表中找
                    do {
                        if (e.hash == hash &&
                            ((k = e.key) == key ||
                             (key != null && key.equals(k)))) {
                            node = e;
                            break;
                        }
                        p = e;
                    } while ((e = e.next) != null);
                }
            }
            //找到了该结点
            if (node != null && (!matchValue || (v = node.value) == value ||
                                 (value != null && value.equals(v)))) {
                //如果是红黑树 则调用红黑树删除
                if (node instanceof TreeNode)
                    ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
                //链表删除
                else if (node == p)
                //如果被删除结点就是头结点，直接指向node.next即可
                    tab[index] = node.next;
                else
                //因为p总是node的上一个结点，于是只要将p.next指向node.next即可
                    p.next = node.next;
                ++modCount;
                //结点数-1
                --size;
                //请无视调用
                afterNodeRemoval(node);
                return node;
            }
        }
        return null;
    }

3. HashMap中的TreeNode

Java中的红黑树是根据算法导论⁹的红黑树改编而来的，而不是文章的第一部分中根据算法第四版³而写的左偏红黑树。算法导论中对红黑树的定义是这样的

1. 每个结点或是红色，或是黑色的
2. 根节点是黑色的
3. 每个叶结点(NIL)都是黑色的(叶结点就是NULL结点)
4. 如果一个结点是红色的，则它的两个子结点都是黑色的
5. 对每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点。(以下简称黑色平衡性)

这两种红黑树的区别是：算法第四版的红黑树的红结点只能是左结点，而算法导论中的红结点可以是左右结点，但是这种存在也是临时的，后面读者就会看到，很多操作中会将left、right都是红结点的结点进行消除。本质上都是黑色平衡性。

接下来我们按照第2部分中关于TreeNode操作出现的顺序来讲解，依次是：get方法中的getTreeNode、

3.1 getTreeNode方法

该方法实际调用的是find，请注意：在HashMap中键的比较主要依据以下优先级从上往下的规则：

• 比较元素的依据主要以 hashCode为主
• 如果在hashCode相等 就判断元素是否有实现Comparable接口
• 如果实现了就调用compareTo对比
• 如果还是相等，就调用Class.getName().compareTo对比
• 如果Class.getName().compareTo还是相等 会调用System.identityHashCode 再对比

final TreeNode<K,V> getTreeNode(int h, Object k) {
    //如果调用这个方法的结点不是root，则找到root后继续
    return ((parent != null) ? root() : this).find(h, k, null);
}

final TreeNode<K,V> find(int h, Object k, Class<?> kc) {
            /**
             * 从getTreeNode方法进来的时候是p是root结点
             * 但是并未规定调用find一定是要是root结点
             * 可以认为只要是树结点就可调用此方法
             */
            TreeNode<K,V> p = this;
            do {
                int ph, dir; K pk;
                //拿到p的左树和右树
                TreeNode<K,V> pl = p.left, pr = p.right, q;
                //需要找的k的hash是否小于p的hash
                if ((ph = p.hash) > h)
                    //是就将p改为p的左树
                    p = pl;
                else if (ph < h)
                    //大于p的hash时将p改为其右树
                    p = pr;
                //到这里时说明hash已经相等了，再判断key是否也相等，相等则找到了
                else if ((pk = p.key) == k || (k != null && k.equals(pk)))
                    return p;
                //左树为空从右树继续找
                else if (pl == null)
                    p = pr;
                //右树为空从左树继续找
                else if (pr == null)
                    p = pl;
                /**
                 * 比较元素的依据主要以 hashCode为主
                 * 如果在hashCode相等 就判断元素是否有实现Comparable接口
                 * 如果实现了就调用compareTo对比
                 * 如果还是相等，就调用Class.getName().compareTo对比
                 * 如果Class.getName().compareTo还是相等 会调用System.identityHashCode 再对比
                 */
                else if ((kc != null ||
                          (kc = comparableClassFor(k)) != null) &&
                         (dir = compareComparables(kc, k, pk)) != 0)
                    p = (dir < 0) ? pl : pr;
                //比较没法得到结果 则总是先从右子树开始找 找到了返回
                else if ((q = pr.find(h, k, kc)) != null)
                    return q;
                //右子树没找到 继续从左子树开始
                else
                    p = pl;
            //只要p不等于null就继续循环
            } while (p != null);
            return null;
        }

3.2 treeifyBin方法

treeifyBin是把数组中某个下标指向的链表的所有结点转为红黑树，将操作效率从N提升到lgN，具体内容请见代码块1.8。因为在树化之后还要保证能untreeifyBin，也就是从红黑树转回链表，所以在HahsMap的TreeNode中多维护了跟链表有关的两个指针:prev、next(TreeNode的属性如代码块2.0所示)。在代码块1.8中可以看到，真正开始树化的方法是treeify。

	/**
     * 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;
        //当前table的长度是否达到了MIN_TREEIFY_CAPACITY的界限 如果没有 还是进行数组扩容
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize();
        //拿到链表表头元素
        else if ((e = tab[index = (n - 1) & hash]) != null) {
            //按链表的顺序将元素依次变为TreeNode结点(实际上还是链表)
            TreeNode<K,V> hd = null, tl = null;
            do {
                TreeNode<K,V> p = replacementTreeNode(e, null);
                if (tl == null)
                    hd = p;
                else {
                    p.prev = tl;
                    tl.next = p;
                }
                tl = p;
            } while ((e = e.next) != null);
            //以hd作为root正式开始红黑树化
            if ((tab[index] = hd) != null)
                hd.treeify(tab);
        }
    }

treeify方法的执行过程实际上就是把链表中每个结点插入红黑树的过程，红黑树中插入一个结点的方法和二叉查找树基本相同(见代码块1.9)，但是为了维护红黑树性质的balanceInsertion方法则很复杂。

final void treeify(Node<K,V>[] tab) {
            TreeNode<K,V> root = null;
            for (TreeNode<K,V> x = this, next; x != null; x = next) {
                //next变量指向x.next
                next = (TreeNode<K,V>)x.next;
                //红黑树的左右两个指针初始化
                x.left = x.right = null;
                //如果root为null
                //直接将循环开始的第一个结点作为红黑树的root结点
                if (root == null) {
                    //root结点是没有父亲的
                    x.parent = null;
                    //满足性质2
                    x.red = false;
                    root = x;
                }
                else {
                    K k = x.key;
                    int h = x.hash;
                    Class<?> kc = null;
                    for (TreeNode<K,V> p = root;;) {
                        int dir, ph;
                        K pk = p.key;
                        /**
                         * 比较元素的依据主要以 hashCode为主
						 * 如果在hashCode相等 就判断元素是否有实现Comparable接口
						 * 如果实现了就调用compareTo对比
						 * 如果还是相等，就调用Class.getName().compareTo对比
						 * 如果Class.getName().compareTo还是相等 会调用System.identityHashCode 再对比
                         */
                        if ((ph = p.hash) > h)
                            dir = -1;
                        else if (ph < h)
                            dir = 1;
                        else if ((kc == null &&
                                  (kc = comparableClassFor(k)) == null) ||
                                 (dir = compareComparables(kc, k, pk)) == 0)
                            dir = tieBreakOrder(k, pk);

                        TreeNode<K,V> xp = p;
                        /**
                         * 以上面比较的结果决定插入的位置
                         * 如果对应的子树不为空则继续循环，直到找到null结点为止
                         */
                        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);
        }

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
        TreeNode<K,V> parent;  // 父亲节点链接
        TreeNode<K,V> left;    // 左子树链接
        TreeNode<K,V> right;   // 右子树链接
        TreeNode<K,V> prev;    // 链表的上一个结点
        boolean red;		   // 当前结点是否是红色的
        TreeNode(int hash, K key, V val, Node<K,V> next) {
            super(hash, key, val, next);
        }
}        

balanceInsertion总体上是为了保证红黑树的几条基本性质不被破坏，如果被破坏了就要进行修复。为了方便书写，我们把x定为被插入结点的名称。在方法中使用循环修复树结构，循环的保持条件是，x的父亲是红结点。因为x的父亲是红结点时破坏了性质4，相反则什么性质也没破坏。在破坏了性质4的基础上，可能会有三种情况发生(其实有6种情况，其他3种跟将要介绍的3种刚好相反，笔者就不再赘述了)：

1. x的祖父的右节点也是红色
   发生这种情况时，我们使用颜色转换来将问题的解自底向上传递，直到其父结点不是红色为止。颜色转换是把两个子结点变为黑色，然后把两个子结点的父亲变为红色，具体操作请看图1.8。虽然有些结点的颜色发生了转变，但是并未破坏性质5，即黑色平衡性。唯一可能破坏的就是当图中56这个结点的父亲也是红色时(性质4)。在代码实现上右旋转和左旋转的差别不大，主要是left OR right的区别。

2. x的祖父的右节点不是红色，且x是其父亲的右结点
3. x的祖父的右节点不是红色，且x是其父亲的左结点
   情况2发生的目的是为情况3服务的，无论是同时发生了情况2和情况3，还是只发生了情况3,。其最终目的都是要满足性质4。为了满足性质4有一种叫旋转的操作，情况2对应左旋转(请结合代码块2.1和图1.9看)，情况3对应右旋转(请结合代码块2.2和图2.0看)。

		/**
         * 左旋一个结点，p代表要左旋的结点
         * 温馨提示：搭配图解更直观
         */
        static <K,V> TreeNode<K,V> rotateLeft(TreeNode<K,V> root,
                                              TreeNode<K,V> p) {
            TreeNode<K,V> r, //p的右结点
                    pp,      //p的父结点
                    rl;      //p的右结点的左结点
            //p的右结点不为空时
            if (p != null && (r = p.right) != null) {
                /**
                 * 将r的左结点赋值给p的右结点
                 * 因为r既然是p的右结点，那么r下的结点必然都比p大
                 * 这里将r的左结点给p是因为它的右节点不用参与这次旋转，保留即可
                 */
                if ((rl = p.right = r.left) != null)
                    rl.parent = p;
                //如果p是root 那么r就要满足性质2
                if ((pp = r.parent = p.parent) == null)
                    (root = r).red = false;
                //不是则把p的父亲的左结点或者右结点指向r
                else if (pp.left == p)
                    pp.left = r;
                else
                    pp.right = r;
                //右结点的左结点指向p，最终右结点从儿子变成了父亲
                r.left = p;
                p.parent = r;
            }
            return root;
        }

/**
         * 右旋一个结点，p代表要右旋的结点
         */
        static <K,V> TreeNode<K,V> rotateRight(TreeNode<K,V> root,
                                               TreeNode<K,V> p) {
            TreeNode<K,V> l, //p的左结点
                    pp,      //p的父结点
                    lr;      //p的左结点的右结点
            //p的左结点不为空时
            if (p != null && (l = p.left) != null) {
                /**
                 * 将l的右结点赋值给p的左结点
                 * 因为l既然是p的左结点，那么l下的结点必然都比p小
                 * 这里将l的右结点给p是因为它的左节点不用参与这次旋转，保留即可
                 */
                if ((lr = p.left = l.right) != null)
                    lr.parent = p;
                //如果p是root 那么r就要满足性质2
                if ((pp = l.parent = p.parent) == null)
                    (root = l).red = false;
                //不是则把p的父亲的左结点或者右结点指向l
                else if (pp.right == p)
                    pp.right = l;
                else
                    pp.left = l;
                //左结点的右结点指向p，最终左结点从儿子变成了父亲
                l.right = p;
                p.parent = l;
            }
            return root;
        }

在理解了上面三种情况以及所做的处理之后，再来看代码块2.3中balanceInsertion的代码就会很容易理解了。

		/**
         * 这个方法判断红黑树的以下性质是否被破坏，被破坏就修复
         * 1. 每个结点或是红色，或是黑色的
         * 2. 根节点是黑色的
         * 3. 每个叶结点(NIL)都是黑色的(叶结点就是NULL结点)
         * 4. 如果一个结点是红色的，则它的两个子结点都是黑色的
         * 5. 对每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点。
         */
        static <K,V> TreeNode<K,V> balanceInsertion(TreeNode<K,V> root,
                                                    TreeNode<K,V> x) {
            //新插入的结点必须是红结点(保证性质5，防止破坏黑色平衡性)
            x.red = true;
            /**
             * xp是被插入节点的父结点
             * xpp是被插入结点的祖父结点
             * xppl是被插入结点的祖父结点的左结点
             * xppr是被插入结点的祖父结点的右结点
             */
            for (TreeNode<K,V> xp, xpp, xppl, xppr;;) {
                //如果父节点是NULL，说明它就是root结点
                if ((xp = x.parent) == null) {
                    //为了满足性质2
                    x.red = false;
                    return x;
                }
                //当父亲的颜色为黑色时循环结束(这里 || 右边的貌似没有必要，因为性质2)
                else if (!xp.red || (xpp = xp.parent) == null)
                    return root;
                /**
                 * 进入到这里的时候，说明它父亲也是红结点
                 * 这就说明破坏了性质4 即红结点下都是黑节点
                 */
                //如果它父亲是它祖父的左结点
                if (xp == (xppl = xpp.left)) {
                    /**
                     * 情况1：如果他祖父的右结点也是红结点
                     * 情况1的处理方法是颜色转变，自底向上传递
                     * 虽然改变了一些结点的颜色，但是性质5并没有被破坏
                     */
                    if ((xppr = xpp.right) != null && xppr.red) {
                        //将它祖父的子节点都变黑 再把它自身变红
                        xppr.red = false;
                        xp.red = false;
                        xpp.red = true;
                        //x指向了它祖父
                        x = xpp;
                        // (可以认为现在要处理的结点从插入结点变成了其祖父)
                    }
                    else {
                    /**
                     * 情况2：右节点不是红色，且它是它父亲的右结点
                     * 情况2的处理方法是：先把x指向其父亲，然后把它父亲左旋
                     * 左旋完成之后x必然就是其父亲的左结点，情况2的操作是为了配合情况3完成整个修复过程
                     */
                        if (x == xp.right) {
                            //将xp左旋
                            root = rotateLeft(root, x = xp);
                            //拿到x的祖父结点
                            xpp = (xp = x.parent) == null ? null : xp.parent;
                        }
                    /**
                     * 情况3：右节点不是红色，且它是它父亲的左结点
                     * 情况3的处理方法是：先把x指向其父亲，然后把它父亲左旋
                     * 左旋完成之后x必然就是其父亲的左结点，情况2的操作是为了配合情况3完成整个修复过程
                     */
                        //在经过了情况2的洗礼后 xp的意义则变成了x本身(因为左旋操作)
                        if (xp != null) {
                            //xp作为新的根节点，需满足性质2
                            xp.red = false;
                            if (xpp != null) {
                                //将祖父结点右旋
                                xpp.red = true;
                                root = rotateRight(root, xpp);
                            }
                        }
                    }
                }
                /**
                 * else中是它父亲是祖父的右结点时的操作 和上诉逻辑刚好相反(对称)
                 * 这里笔者就不赘述了
                 */
                else {
                    if (xppl != null && xppl.red) {
                        xppl.red = false;
                        xp.red = false;
                        xpp.red = true;
                        x = xpp;
                    }
                    else {
                        if (x == xp.left) {
                            root = rotateRight(root, x = xp);
                            xpp = (xp = x.parent) == null ? null : xp.parent;
                        }
                        if (xp != null) {
                            xp.red = false;
                            if (xpp != null) {
                                xpp.red = true;
                                root = rotateLeft(root, xpp);
                            }
                        }
                    }
                }
            }
        }

3.3 putTreeVal方法

如果理解了treeifyBin方法，putTreeVal就相对简单了。

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;
            //如果调用者不是root 就找到root
            TreeNode<K,V> root = (parent != null) ? root() : this;
            for (TreeNode<K,V> p = root;;) {
                int dir, ph; K pk;
                /**
                 * @see #treeify(Node[]) 的注释
                 */
                if ((ph = p.hash) > h)
                    dir = -1;
                else if (ph < h)
                    dir = 1;
                //如果key相等 直接返回当前结点
                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) {
                    /**
                     * 如果结点其实是实现了Comparable接口的类，并且对比结果是相等
                     * 则直接在该树的子树中找结点是否已存在
                     */
                    if (!searched) {
                        TreeNode<K,V> q, ch;
                        searched = true;
                        //左树不为NULL在左树找，右树不为NULL在右树找，找到了就返回该结点
                        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;
                    }
                    //没找到就继续使用Class.getName().compareTo、System.identityHashCode对比
                    dir = tieBreakOrder(k, pk);
                }

                TreeNode<K,V> xp = p;
                //依据对比的结果判断左树或者右树是否为NULL，不为NULL则继续查找
                if ((p = (dir <= 0) ? p.left : p.right) == null) {
                    /**
                     * 这里维护next和prev是为了将树链表化
                     * @see #untreeify(HashMap)
                     * 链表头插法
                     */
                    Node<K,V> xpn = xp.next;
                    //new一个树结点
                    TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn);
                    //插入到左子树后右子树 (xp是其父亲)
                    if (dir <= 0)
                        xp.left = x;
                    else
                        xp.right = x;
                    xp.next = x;
                    x.parent = x.prev = xp;
                    if (xpn != null)
                        ((TreeNode<K,V>)xpn).prev = x;
                    //插入完成后维护平衡，并将root放到头结点上
                    moveRootToFront(tab, balanceInsertion(root, x));
                    return null;
                }
            }
        }

3.4 removeTreeNode方法

在2.5节的remove方法中我们可以看到，调用removeTreeNode之前需要删除的结点已经被找到。
removeTreeNode操作除了删除结点之外，要做的便是和put操作的balanceInsertion差不多的维护红黑树性质的修复操作，这里因为文章篇幅和时间问题就不详细讲解了。

总结

文章中介绍的几种符号表的差异如下表所示

红黑树本来可以用作有序性的操作的，但是HashMap只是将它作为查找来使用了，所以在HashMap的红黑树中键的顺序并不重要，重要的是能在对数时间内找出要的键和值。