前言： 本文基于 JDK1.8，不会过多的扩展其它知识，重点关注 HashMap 的实现。

首先简单介绍一下和 HashMap 有亲戚关系的三个类，分别为 LinkedHashMap、TreeMap 和 Hashtable。
类的继承关系如下图所示：

image
HashMap： (1)非线程安全 (2) 遍历顺序不确定 (3) 允许有一条记录的 key 为 null

LinkedHashMap： (1) LinkedHashMap 是 HashMap 的一个子类 (2) 保存了记录的插入顺序，在用 Iterator 遍历时，先得到的记录肯定是先插入的。

TreeMap： (1) 实现了 SortedMap 接口，当用 Iterator 遍历时，得到的记录是默认按键值升序排序的。(2) 底层是红黑树

Hashtable： (1) 除了面试可能会问到，否则没什么用。 (2) 线程安全

为什么现在几乎不使用 Hashtable 了？
因为有更好的类替代了它，如果是不需要线程安全的情况，则 HashMap 比它的效率更高，我们会使用 HashMap。如果是需要线程安全的情况，Hashtable 的并发性又不如 ConcurrentHashMap。

HashMap 的重点内容

一、存储实现

HashMap 是数组 + 链表 + 红黑树实现的。其解决冲突的方法是链地址法（拉链法），所以会有链表存在。由于产生 hash 冲突后，需要沿链表顺序查找，比较费时间，所以当链表长度大于 8 时，将链表转换为红黑树（JDK1.8新加入的功能），这就是为什么会有红黑树存在的原因。
如果对数据结构 hash 表不熟悉，不知道什么是 hash 冲突的同学，可以参考这篇博客https://blog.csdn.net/u011109881/article/details/80379505。
HashMap 的存储实现如下图所示：

image

二、功能实现（结合源代码）

2.1 依然从存储开始，存储键值对的结点类

源代码如下（扫一遍即可，注意，里面的英文注释都是源码自带的）：

/**
 * 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;
/**
 * 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> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;

    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }

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

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

    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}

这里的transient Node<K,V>[] table;中的 table 就是我们上面提到的存储实现里的数组，是一个 Node 型的数组，而这个 Node 为 HashMap 的内部类，是用来存储键值对的结点。
Node 类的简化代码如下，可以更清晰的看到其类结构：

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;    //用来定位数组索引位置
        final K key;
        V value;
        Node<K,V> next;   //链表的下一个node

        Node(int hash, K key, V value, Node<K,V> next) { ... }
        public final K getKey(){ ... }
        public final V getValue() { ... }
        public final String toString() { ... }
        public final int hashCode() { ... }
        public final V setValue(V newValue) { ... }
        public final boolean equals(Object o) { ... }
}

2.2 HashMap里的重要参数

下面是 HashMap 里定义的部分重要常量及字段，其中部分常量的值就是部分重要字段初始化的默认值，例如第一个常量 DEFAULT_INITIAL_CAPACITY=16 就是Node<K,V>[] table数组初始化的空间大小（即默认的数组长度为 16），源代码如下：

/**
 * The default initial capacity - MUST be a power of two.
 */
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.
 */
static final int MAXIMUM_CAPACITY = 1 << 30;

/**
 * The load factor used when none specified in constructor.
 */
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.
 */
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.
 */
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.
 */
static final int MIN_TREEIFY_CAPACITY = 64;

/**
 * The number of key-value mappings contained in this map.
 */
transient int size;

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

/**
 * The next size value at which to resize (capacity * load factor).
 */
// (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.
 */
final float loadFactor;

除了前面的常量（不那么重要），重要的字段总共就 4 个，分别为 size，modCount，threshold，loadFactor。

size（不需要初始化）： 就是 HashMap 中实际存储的键值对数目。

loadFactor： 为负载因子 (默认值是0.75)。

threshold： 是 HashMap 所能容纳的最大键值对数。threshold = length * loadFactor，其中 length 为 table 数组的长度，初始默认为16。所以 HashMap 所能容纳的最大键值对数就是数组长度按负载因子为比例计算的结果。

modCount（不需要初始化）： 用来记录 HashMap 内部结构发生变化的次数。

从负载因子我们可以知道 HashMap 大概有多少空闲空间，不用来存放数据。我原来一直在算法实现上总不想使用 hash 表的原因有如下两点：

1. hash 表需要占用很大的空间。而且肯定会有部分空闲空间没有存放数据。例如 HashMap 负载因子默认是0.75，所以至少有0.25的空闲空间（因为还有部分结点是链在链表中的）。
2. 理论上 hash 表的查找时间复杂度为O(1)，但是存在 hash 冲突的现象，所以最坏情况下可能也是O(n)。但是实际上，使用平摊分析，时间复杂度平摊下来就是O(1)。

可能有部分人现在也有这种想法，但我们一定要抛弃这种想法。因为在现在这个时间比空间更重要的年代里（存储空间越来越大越来越便宜，用户体验更重要，不能让用户有过长的等待时间） ，空间换时间是完全划算的。
言归正传，下面贴出 HashMap 的无参构造函数：

/**
 * Constructs an empty <tt>HashMap</tt> with the default initial capacity
 * (16) and the default load factor (0.75).
 */
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

我们可以很神奇的发现，无参构造函数竟然就只初始化了一个 loadFactor。那么如果我们调用无参的构造函数，table.length 和 threshold 又是在哪初始化的呢。其中我比较关心 table.length 即数组长度的初始化，这个 16 是在哪赋值的呢。看了一下源码，这个初始化真的是一波三折。
下面就讲一下这个初始化的过程：（下面一大段代码先扫一遍就行，能够知道三个函数之间的调用关系就可以了，后面我们还会具体讲解put、putVal 和 resize 方法）

/**
 * Associates the specified value with the specified key in this map.
 * If the map previously contained a mapping for the key, the old
 * value is replaced.
 */
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;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        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();
    afterNodeInsertion(evict);
    return null;
}

/**
 * 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() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    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;
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        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;
}

上面是 HashMap 的 put 函数（即向 HashMap 中添加和更新元素的函数）以及 resize 函数（Hash Map 的扩容函数）的实现源代码。
在调用 put 函数之前，table 数组是没有分配任何存储空间的。在执行到 putVal 函数时，首先要经过如下判断。

if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length;

发现数组没有分配空间后，就调用 resize() 函数。在此函数中会进行旧数组的容量判断，如果发现旧数组还未分配任何空间，就对数组进行初始化。

if (oldCap > 0) {
    if (oldCap >= MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return oldTab;
    }
    else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
             oldCap >= DEFAULT_INITIAL_CAPACITY)
        newThr = oldThr << 1; // double threshold
}
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);
}
...
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;

稍微想一下，源码这样设计是有它的好处的，其实初衷也很简单，就是在初始化 HashMap 对象时，并没有必要立马就分配数组内存。因为指不定最后根本就没有使用这个对象呢，这是完全有可能的。我们可以想象一下这样一个情境，一个程序员在编码过程中觉得，解决他面临的这个问题，肯定需要用到 HashMap，于是他定义并初始化了一个 HashMap 对象，但是写到后面他又发现不用 HashMap 也行，于是他后面就没有用到那个 HashMap 对象。所以源码把数组的初始化放在了调用 put 函数的时候，是合情合理的，只有当你真正使用 HashMap 的时候在给你分配数组空间。所以不仅无参的构造函数如此，其它所有的构造函数，都没有把数组的初始化放在其中。

2.3 如何由 key 确定键值对在数组中的索引

1. 调用 key 对象自身的 hashCode 函数，得到 key 的哈希值。
2. 进一步哈希，借助移位和异或运算，使得哈希值的高位也可以参与运算。
3. 对进一步得到的哈希值进行取模运算

/**
 * Computes key.hashCode() and spreads (XORs) higher bits of hash
 * to lower.  Because the table uses power-of-two masking, sets of
 * hashes that vary only in bits above the current mask will
 * always collide. (Among known examples are sets of Float keys
 * holding consecutive whole numbers in small tables.)  So we
 * apply a transform that spreads the impact of higher bits
 * downward. There is a tradeoff between speed, utility, and
 * quality of bit-spreading. Because many common sets of hashes
 * are already reasonably distributed (so don't benefit from
 * spreading), and because we use trees to handle large sets of
 * collisions in bins, we just XOR some shifted bits in the
 * cheapest possible way to reduce systematic lossage, as well as
 * to incorporate impact of the highest bits that would otherwise
 * never be used in index calculations because of table bounds.
 */
方法一：取 key 的哈希值，并进一步哈希，得到计算数组索引所用的哈希值
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

方法二：jdk1.7的源码，jdk1.8没有这个方法，jdk1.8把这段代码融到具体需要算数组下标的时候去了，原理不变
static int indexFor(int h, int length) {
     return h & (length-1);//由于length是2的幂，此时相当于取模运算
}

由于源码都是很优化的代码，所以能使用位运算的地方都尽量使用位运算。例如上面的代码使用位运算代替取模运算，大大提高了运算效率。而能够让位运算代替取模运算的条件是数组的长度为2的幂。因为数组的初始长度为 16，以后每次 reszie 的时候都是乘 2（左移一位），所以数组的长度总是2的幂。体现在源代码里面，就是：

if (oldCap > 0) {
    if (oldCap >= MAXIMUM_CAPACITY) {
        threshold = Integer.MAX_VALUE;
        return oldTab;
    }
    else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
             oldCap >= DEFAULT_INITIAL_CAPACITY)
        newThr = oldThr << 1; // double threshold
}

即第 6 行的这句newCap = oldCap << 1，使得新数组长度永远是旧数组长度的 2 倍。

看到这里相信有很多人会有两个疑问，
(1) 为什么数组长度为 2 的幂时，取模运算可以使用代码里的位运算代替？
(2) 为什么通过 key 对象的 hashCode 方法得到的哈希值，需要进一步哈希，使得原始哈希值的高位也参与运算？
请带着这两个问题看下面这幅图，这幅图表示的就是从原始哈希值计算得到数组索引的整个过程，n 为数组的长度：

image

解答问题(1)：因为当 n 为 2 的幂时，n-1 的二进制表示就是若干个连续的二进制 1 组成的，此时做与运算就相当于取模运算。
解答问题(2)：正因为取模运算，取的仅仅是二进制数据的低位部分，如果不对高位数据进行处理，那么高位数据将完全没用上，换句话说就是哈希的效果不好。

2.4 HashMap 的 put 方法（get 方法类似）

put 方法的作用是添加新的键值对或根据键去更新值，其大致流程如下：

1. 判断数组 table 是否为 null 或长度为 0，如果是则执行 resize() 进行扩容。
2. 计算键值 key 对应的数组下标 i，如果 table[i]==null，则直接新建节点添加，转向步骤 6。
3. 如果table[i] 不为空，判断 key 是否就在 table[i] 的首个元素，如果是则直接对 value 进行赋值，并返回旧的 value，算法结束。
4. 如果不是，判断 table[i] 是否为红黑树，如果是红黑树，则转入对红黑树的操作（这一块不展开讲解）。
5. 如果不是红黑树，遍历 table[i]，如果遍历过程中发现 key 已存在，则直接对 value 赋值，并返回旧的 value，算法结束。否则，将键值对插入链表尾部，然后判断插入后链表长度是否大于 8，如果是，就把链表转换为红黑树。
6. 插入成功后，判断实际存在的键值对数量 size 是否超多了最大容量 threshold，如果超过，进行扩容。

put 方法实际上就是直接调用 putVal 函数，下面我们主要看 putVal 方法即可：

public V put(K key, V value) {
    //put 方法在调用 putVal 方法之前，先计算好了 key 的哈希值。
    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;
//步骤1，判断数组是否未初始化
if ((tab = table) == null || (n = tab.length) == 0)
 n = (tab = resize()).length;
//步骤2，根据 key 的哈希值，计算数组下标
if ((p = tab[i = (n - 1) & hash]) == null)
 tab[i] = newNode(hash, key, value, null);
else {
 Node<K,V> e; K k;
//步骤3，首先判断 key 是否就在首个元素
 if (p.hash == hash &&
     ((k = p.key) == key || (key != null && key.equals(k))))
     e = p;
//步骤4，判断是否为红黑树
 else if (p instanceof TreeNode)
     e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//步骤5，为链表的情况
 else {
     for (int binCount = 0; ; ++binCount) {
         if ((e = p.next) == null) {
             p.next = newNode(hash, key, value, null);
             //链表长度大于 8，转换为红黑树
             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;
     }
 }
//如果 key 存在，则直接覆盖 value，并返回旧的 value
 if (e != null) { // existing mapping for key
     V oldValue = e.value;
     if (!onlyIfAbsent || oldValue == null)
         e.value = value;
     afterNodeAccess(e);
     return oldValue;
 }
}
++modCount;//进行了一次插入操作，HashMap 的结构变化了一次，所以自加 1
//步骤6，超过了容量限定，就扩容
if (++size > threshold)
 resize();
afterNodeInsertion(evict);
return null;
}

2.5 resize 方法（数组扩容）

扩容并不是简单的 new 一个容量更大的数组，然后把原来数组里的键值对拷贝到新数组里就行了的。还要对所有元素进行重哈希的操作，因为数组的 length 变为原来的 2 倍，原来 key 对应的 哈希值，经过取模运算后，得到的数组索引可能已经发生了变化。
看了下图就可以明白上面这段话的意思，n 为 table 的长度，图 (a) 表示扩容前的 key1 和 key2 两个 key 确定索引位置的示例，图 (b) 表示扩容后 key1 和 key2 两个 key 确定索引位置的示例。

image

元素在重哈希之后，因为 n 变为了原来的 2 倍，那么 n-1 的 mask 范围在高位会比原来多出 1 个比特。如果多出来的这个比特是 1，那么数组索引会发生如下图所示的变化：

image

因此，我们在扩容的时候，只需要对着原本的 hash 值，看新增的那个 bit 是 1 还是 0 就好了，如果是 0 的话索引不变，是 1 的话索引变为 “原索引 + oldCap”，可以参考下面 16 扩充为 32 的 resize 示意图：

image
resize 方法源代码，加上注释如下：

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) {
        //  超过最大值就不再扩充
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 没超过最大值，就扩充为原来的2倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    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);
    }
    // 计算新的resize上限
    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) {
        // 把每个bucket都移动到新的buckets中
        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;
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                // 重新计算数组索引的代码块
                else { // preserve order
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
                        // 原索引
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        // 原索引 + oldCap
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 原索引放到 bucket 里
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    // 原索引 + oldCap 放到 bucket 里
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

2.6 性能测试和对比

Hash较均匀的情况（使用1、10、100、......10000000作为 key，屏蔽了扩容的情况）

JDK1.7 和 JDK1.8 get 方法的性能对比：

image

我们可以看到，JDK1.8 get 方法的性能明显优于 JDK1.7。而且由于 key 比较均匀，这还是没有展现出红黑树优势的情况。

Hash极不均匀的情况（总令 key 为 1，屏蔽了扩容的情况）

JDK1.7 和 JDK1.8 get 方法的性能对比：

image

测试环境：处理器为2.2 GHz Intel Core i7，内存为16 GB 1600 MHz DDR3，SSD硬盘，使用默认的JVM参数，运行在64位的OS X 10.10.1上。

参考：

1. JDK1.8 源码
2. 知乎文章，https://zhuanlan.zhihu.com/p/21673805