关于redis:从零开始手写缓存框架-redis13HashMap-源码原理详解

为什么学习 HashMap 源码？

作为一名 java 开发，基本上最罕用的数据结构就是 HashMap 和 List，jdk 的 HashMap 设计还是十分值得深刻学习的。

无论是在面试还是工作中，晓得原理都对会咱们有很大的帮忙。

本篇的内容较长，倡议先珍藏，再细细品味。

不同于网上简略的源码剖析，更多的是实现背地的设计思维。

波及的内容比拟宽泛，从统计学中的泊松散布，到计算机根底的位运算，经典的红黑树、链表、数组等数据结构，也谈到了 Hash 函数的相干介绍，文末也引入了美团对于 HashMap 的源码剖析，所以整体深度和广度都比拟大。

思维导图如下：

本文是 两年前整顿的，文中未免有疏漏过期的中央，欢送大家提出贵重的意见。

之所以这里拿进去，有以下几个目标：

（1）让读者了解 HashMap 的设计思维，晓得 rehash 的过程。下一节咱们将本人实现一个 HashMap

（2）为什么要本人实现 HashMap?

最近在手写 redis 框架，都说 redis 是一个个性更加弱小的 Map，天然 HashMap 就是入门根底。Redis 高性能中一个过人之处的设计就是渐进式 rehash，和大家一起实现一个渐进式 rehash 的 map，更能领会和了解作者设计的奇妙。

想把常见的数据结构独立为一个开源工具，便于前期应用。比方这次手写 redis，循环链表，LRU map 等都是从零开始写的，不利于复用，还容易有 BUG。

好了，上面就让咱们一起开始 HashMap 的源码之旅吧~

HashMap 源码

HashMap 是平时应用到十分多的一个汇合类，感觉有必要深刻学习一下。

首先尝试本人浏览一遍源码。

java 版本

$ java -version
java version "1.8.0_91"
Java(TM) SE Runtime Environment (build 1.8.0_91-b14)
Java HotSpot(TM) 64-Bit Server VM (build 25.91-b14, mixed mode)

数据结构

从构造实现来讲，HashMap 是数组 + 链表 + 红黑树（JDK1.8 减少了红黑树局部）实现的。

对于以后类的官网阐明

基于哈希表实现的映射接口。这个实现提供了所有可选的映射操作，并容许空值和空键。(HashMap 类大抵相当于 Hashtable，但它是非同步的，并且容许为空。)

这个类不保障映射的程序; 特地地，它不能保障程序会随工夫放弃不变。

这个实现为基本操作 (get 和 put) 提供了恒定工夫的性能，假如哈希函数将元素适当地扩散在各个桶中。对汇合视图的迭代须要与 HashMap 实例的“容量”(桶数)及其大小 (键 - 值映射数) 成比例的工夫。因而，如果迭代性能很重要，那么不要将初始容量设置得太高(或者负载系数太低)，这是十分重要的。

HashMap 实例有两个影响其性能的参数: 初始容量和负载因子。

容量是哈希表中的桶数，初始容量只是创立哈希表时的容量。负载因子是在哈希表的容量主动减少之前，哈希表被容许达到的最大容量的度量。当哈希表中的条目数量超过负载因子和以后容量的乘积时，哈希表就会被从新哈希(也就是说，从新构建外部数据结构)，这样哈希表的桶数大概是原来的两倍。

一般来说，默认的负载因子 (0.75) 在工夫和空间老本之间提供了很好的衡量。

较高的值缩小了空间开销，但减少了查找老本(反映在 HashMap 类的大多数操作中，包含 get 和 put)。在设置映射的初始容量时，应该思考映射中的冀望条目数及其负载因子，以最小化重哈希操作的数量。如果初始容量大于条目标最大数量除以负载因子，就不会产生重哈希操作。

如果要将许多映射存储在 HashMap 实例中，那么应用足够大的容量创立映射将使映射存储的效率更高，而不是让它依据须要执行主动重哈希以增长表。

留神，应用具备雷同 hashCode()的多个键的确能够升高任何散列表的性能。为了改善影响，当键具备可比性时，这个类能够应用键之间的比拟程序来帮忙断开连接。

留神，这个实现不是同步的。如果多个线程并发地拜访散列映射，并且至多有一个线程在结构上批改了映射，那么它必须在内部同步。(构造批改是增加或删除一个或多个映射的任何操作; 仅更改与实例曾经蕴含的键关联的值并不是构造批改。这通常是通过对天然封装映射的对象进行同步来实现的。

如果不存在这样的对象，则应该应用汇合“包装”Collections.synchronizedMap 办法。这最好在创立时实现，以避免意外的对映射的非同步拜访:

Map m = Collections.synchronizedMap(new HashMap(...));

这个类的所有“汇合视图办法”返回的迭代器都是疾速失败的: 如果在创立迭代器之后的任何时候对映射进行构造上的批改，除了通过迭代器本人的 remove 办法，迭代器将抛出 ConcurrentModificationException。因而，在并发批改的状况下，迭代器会疾速而洁净地失败，而不是在将来的不确定工夫内冒着任意的、不确定的行为的危险。

留神，迭代器的疾速故障行为不能失去保障，因为一般来说，在存在非同步并发批改的状况下，不可能做出任何硬性保障。疾速失败迭代器以最佳的形式抛出 ConcurrentModificationException。因而，编写依赖于此异样的程序来保障其正确性是谬误的: 迭代器的疾速故障行为应该仅用于检测谬误。

其余根底信息

1. 这个类是 Java 汇合框架的成员。
2. @since 1.2
3. java.util 包下

源码初探

接口

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {}

以后类实现了三个接口，咱们次要关怀 Map 接口即可。

继承了一个抽象类 AbstractMap，这个临时放在本节前面学习。

常量定义

默认初始化容量

/**
 * The default initial capacity - MUST be a power of two.
 */
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

• 为什么不间接应用 16？

看了下 statckoverflow，感觉比拟靠谱的解释是：

1. 为了防止应用魔法数字，使得常量定义自身就具备自我解释的含意。
2. 强调这个数必须是 2 的幂。

• 为什么要是 2 的幂？

它是这样设计的，因为它容许应用疾速位和操作将每个键的哈希代码包装到表的容量范畴内，正如您在拜访表的办法中看到的:

final Node<K,V> getNode(int hash, Object key) {Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    if ((tab = table) != null && (n = tab.length) > 0 &&
        (first = tab[(n - 1) & hash]) != null) { /// <-- bitwise 'AND' here
        ...

最大容量

隐式指定较高值时应用的最大容量。

由任何带有参数的构造函数。

必须是 2 的幂且小于 1<<30。

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

• 为什么是 1 << 30？

当然了 interger 的最大容量为 2^31-1

除此之外，2**31 是 20 亿，每个哈希条目须要一个对象作为条目自身，一个对象作为键，一个对象作为值。

在为应用程序中的其余内容调配空间之前，最小对象大小通常为 24 字节左右，因而这将是 1440 亿字节。

能够必定地说，最大容量限度只是实践上的。

感觉理论内存也没这么大！

负载因子

当负载因子较大时，去给 table 数组扩容的可能性就会少，所以绝对占用内存较少（空间上较少），然而每条 entry 链上的元素会绝对较多，查问的工夫也会增长（工夫上较多）。

反之就是，负载因子较少的时候，给 table 数组扩容的可能性就高，那么内存空间占用就多，然而 entry 链上的元素就会绝对较少，查出的工夫也会缩小。

所以才有了负载因子是工夫和空间上的一种折中的说法。

所以设置负载因子的时候要思考本人谋求的是工夫还是空间上的少。

/**
 * The load factor used when none specified in constructor.
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

• 为什么是 0.75，不是 0.8 或者 0.6

其实 hashmap 源码中有解释。

Because TreeNodes are about twice the size of regular nodes, we
use them only when bins contain enough nodes to warrant use
(see TREEIFY_THRESHOLD). And when they become too small (due to
removal or resizing) they are converted back to plain bins.  In
usages with well-distributed user hashCodes, tree bins are
rarely used.  Ideally, under random hashCodes, the frequency of
nodes in bins follows a Poisson distribution
(http://en.wikipedia.org/wiki/Poisson_distribution) with a
parameter of about 0.5 on average for the default resizing
threshold of 0.75, although with a large variance because of
resizing granularity. Ignoring variance, the expected
occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
factorial(k)). The first values are:

0:    0.60653066
1:    0.30326533
2:    0.07581633
3:    0.01263606
4:    0.00157952
5:    0.00015795
6:    0.00001316
7:    0.00000094
8:    0.00000006
more: less than 1 in ten million

简略翻译一下就是在现实状况下, 应用随机哈希码, 节点呈现的频率在 hash 桶中遵循泊松散布，同时给出了桶中元素个数和概率的对照表。

从下面的表中能够看到当桶中元素达到 8 个的时候，概率曾经变得十分小，也就是说用 0.75 作为加载因子，每个碰撞地位的链表长度超过8个是简直不可能的。

Poisson distribution —— 泊松散布

阈值

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

TREEIFY_THRESHOLD

应用红黑树而不是列表的 bin count 阈值。

当向具备至多这么多节点的 bin 中增加元素时，bin 被转换为树。这个值必须大于 2，并且应该至多为 8，以便与树删除中对于膨胀后转换回一般容器的假如相匹配。

UNTREEIFY_THRESHOLD

在调整大小操作期间勾销 (宰割) 存储库的存储计数阈值。

应小于 TREEIFY_THRESHOLD，并最多 6 个网格与膨胀检测上来除。

MIN_TREEIFY_CAPACITY

最小的表容量，可为容器进行树状排列。(否则，如果在一个 bin 中有太多节点，表将被调整大小。)

至多为 4 * TREEIFY_THRESHOLD，以防止调整大小和树化阈值之间的抵触。

Node

源码

• Node.java

根底 hash 结点定义。

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

集体了解

四个外围元素：

final int hash; // hash 值
final K key;    // key
V value;    // value 值
Node<K,V> next; // 下一个元素结点

hash 值的算法

hash 算法如下。

间接 key/value 的异或(^)。

Objects.hashCode(key) ^ Objects.hashCode(value);

其中 hashCode() 办法如下：

public static int hashCode(Object o) {return o != null ? o.hashCode() : 0;
}

最初还是会调用对象自身的 hashCode() 算法。个别咱们本人会定义。

动态工具类

hash

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

为什么这么设计？

• jdk8 自带解释

计算 key.hashCode()，并将 (XORs) 的高比特位扩散到低比特位。

因为表应用的是 power-of-two 掩蔽，所以只在以后掩码上方以位为单位变动的哈希总是会发生冲突。

(已知的例子中有一组浮点键，它们在小表中保留间断的整数。)

因而，咱们利用了一种转换，将高比特的影响向下流传。

比特流传的速度、效用和品质之间存在衡量。

因为许多常见的散列集曾经正当散布(所以不要受害于流传), 因为咱们用树来解决大型的碰撞在垃圾箱, 咱们只是 XOR 一些扭转以最便宜的形式来缩小零碎 lossage, 以及将最高位的影响, 否则永远不会因为指数计算中应用的表。

• 知乎的解释

这段代码叫 扰动函数。

HashMap 扩容之前的数组初始大小才 16。所以这个散列值是不能间接拿来用的。

用之前还要先做对数组的长度取模运算，失去的余数能力用来拜访数组下标。

putVal 函数源码

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);
        //...    
}

其中这一句 tab[i = (n - 1) & hash])

这一步就是在寻找桶的过程，就是上图总数组，依据容量取如果容量是 16 对 hash 值取低 16 位，那么下标范畴就在容量大小范畴内了。

这里也就解释了为什么 hashmap 的大小须要为 2 的正整数幂，因为这样（数组长度 -1）正好相当于一个“低位掩码”。

比方大小 16，则 (16-1) = 15 = 00000000 00000000 00001111(二进制);

    10100101 11000100 00100101
&    00000000 00000000 00001111
-------------------------------
    00000000 00000000 00000101    // 高位全副归零，只保留末四位

然而问题是，散列值散布再涣散，要是只取最初几位的话，碰撞也会很重大。

扰动函数的价值如下：

右位移 16 位，正好是 32bit 的一半，本人的高半区和低半区做异或，就是为了混合原始哈希码的高位和低位，以此来加大低位的随机性。

而且混合后的低位掺杂了高位的局部特色，这样高位的信息也被变相保留下来。

优化哈希的原理介绍

comparable class

• comparableClassFor()

获取对象 x 的类，如果这个类实现了 class C implements Comparable<C> 接口。

ps: 这个办法很有借鉴意义，能够做简略的拓展。咱们能够获取任意接口泛型中的类型。

static Class<?> comparableClassFor(Object x) {if (x instanceof Comparable) {Class<?> c; Type[] ts, as; Type t; ParameterizedType p;
        if ((c = x.getClass()) == String.class) // bypass checks
            return c;
        if ((ts = c.getGenericInterfaces()) != null) {for (int i = 0; i < ts.length; ++i) {if (((t = ts[i]) instanceof ParameterizedType) &&
                    ((p = (ParameterizedType)t).getRawType() ==
                     Comparable.class) &&
                    (as = p.getActualTypeArguments()) != null &&
                    as.length == 1 && as[0] == c) // type arg is c
                    return c;
            }
        }
    }
    return null;
}

compareComparables()

获取两个可比拟对象的比拟后果。

@SuppressWarnings({"rawtypes","unchecked"}) // for cast to Comparable
static int compareComparables(Class<?> kc, Object k, Object x) {return (x == null || x.getClass() != kc ? 0 :
            ((Comparable)k).compareTo(x));
}

tableSizeFor

获取 2 的幂

static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

• 被调用处

public HashMap(int initialCapacity, float loadFactor) {
    // check...
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}

• 感想

emmm…. 为什么要这么写？性能吗？

简略剖析

当在实例化 HashMap 实例时，如果给定了 initialCapacity，因为 HashMap 的 capacity 都是 2 的幂，因而这个办法用于找到大于等于 initialCapacity 的最小的 2 的幂（initialCapacity 如果就是 2 的幂，则返回的还是这个数）。

• 为什么要 -1

int n = cap - 1;

首先，为什么要对 cap 做减 1 操作。int n = cap – 1;
这是为了避免，cap 曾经是 2 的幂。如果 cap 曾经是 2 的幂，又没有执行这个减 1 操作，则执行完前面的几条无符号右移操作之后，返回的 capacity 将是这个 cap 的 2 倍。如果不懂，要看完前面的几个无符号右移之后再回来看看。

上面看看这几个无符号右移操作：

如果 n 这时为 0 了（通过了 cap- 1 之后），则通过前面的几次无符号右移仍然是 0，最初返回的 capacity 是 1（最初有个 n + 1 的操作）。

这里只探讨 n 不等于 0 的状况。

• 第一次位运算

n |= n >>> 1;

因为 n 不等于 0，则 n 的二进制示意中总会有一 bit 为 1，这时思考最高位的 1。

通过无符号右移 1 位，则将最高位的 1 右移了 1 位，再做或操作，使得 n 的二进制示意中与最高位的 1 紧邻的左边一位也为 1，如 000011xxxxxx。

其余顺次类推

实例

比方 initialCapacity = 10;

表达式                       二进制
------------------------------------------------------    

initialCapacity = 10;
int n = 9;                  0000 1001
------------------------------------------------------    


n |= n >>> 1;               0000 1001
                            0000 0100   (右移 1 位) 或运算
                          = 0000 1101
------------------------------------------------------    

n |= n >>> 2;               0000 1101
                            0000 0011   (右移 2 位) 或运算
                          = 0000 1111
------------------------------------------------------    

n |= n >>> 4;               0000 1111
                            0000 0000   (右移 4 位) 或运算
                          = 0000 1111
------------------------------------------------------  

n |= n >>> 8;               0000 1111
                            0000 0000   (右移 8 位) 或运算
                          = 0000 1111
------------------------------------------------------  

n |= n >>> 16;              0000 1111
                            0000 0000   (右移 16 位) 或运算
                          = 0000 1111
------------------------------------------------------  

n = n+1;                    0001 0000    后果：2^4 = 16;      

put() 解释

上面的内容出自美团博客 Java 8 系列之重新认识 HashMap

因为写的十分好，此处就间接复制过去了。

流程图解

HashMap 的 put 办法执行过程能够通过下图来了解，本人有趣味能够去比照源码更分明地钻研学习。

①. 判断键值对数组 table[i]是否为空或为 null，否则执行 resize()进行扩容；

②. 依据键值 key 计算 hash 值得到插入的数组索引 i，如果 table[i]==null，间接新建节点增加，转向⑥，如果 table[i]不为空，转向③；

③. 判断 table[i]的首个元素是否和 key 一样，如果雷同间接笼罩 value，否则转向④，这里的雷同指的是 hashCode 以及 equals；

④. 判断 table[i] 是否为 treeNode，即 table[i] 是否是红黑树，如果是红黑树，则间接在树中插入键值对，否则转向⑤；

⑤. 遍历 table[i]，判断链表长度是否大于 8，大于 8 的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现 key 曾经存在间接笼罩 value 即可；

⑥. 插入胜利后，判断理论存在的键值对数量 size 是否超多了最大容量 threshold，如果超过，进行扩容。

办法源码

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;
}

扩容机制

简介

扩容 (resize) 就是从新计算容量，向 HashMap 对象里不停的增加元素，而 HashMap 对象外部的数组无奈装载更多的元素时，对象就须要扩充数组的长度，以便能装入更多的元素。

当然 Java 里的数组是无奈主动扩容的，办法是应用一个新的数组代替已有的容量小的数组，就像咱们用一个小桶装水，如果想装更多的水，就得换大水桶。

JDK7 源码

咱们剖析下 resize()的源码，鉴于 JDK1.8 融入了红黑树，较简单，为了便于了解咱们依然应用 JDK1.7 的代码，好了解一些，实质上区别不大，具体区别后文再说。

void resize(int newCapacity) {   // 传入新的容量
    Entry[] oldTable = table;    // 援用扩容前的 Entry 数组
    int oldCapacity = oldTable.length;         
    if (oldCapacity == MAXIMUM_CAPACITY) {// 扩容前的数组大小如果曾经达到最大 (2^30) 了
        threshold = Integer.MAX_VALUE; // 批改阈值为 int 的最大值(2^31-1)，这样当前就不会扩容了
        return;
    }

    Entry[] newTable = new Entry[newCapacity];  // 初始化一个新的 Entry 数组
    transfer(newTable);                         //！！将数据转移到新的 Entry 数组里
    table = newTable;                           //HashMap 的 table 属性援用新的 Entry 数组
    threshold = (int)(newCapacity * loadFactor);// 批改阈值
}

这里就是应用一个容量更大的数组来代替已有的容量小的数组，transfer() 办法将原有 Entry 数组的元素拷贝到新的 Entry 数组里。

void transfer(Entry[] newTable) {Entry[] src = table;                   //src 援用了旧的 Entry 数组
    int newCapacity = newTable.length;
    for (int j = 0; j < src.length; j++) { // 遍历旧的 Entry 数组
        Entry<K,V> e = src[j];             // 获得旧 Entry 数组的每个元素
        if (e != null) {src[j] = null;// 开释旧 Entry 数组的对象援用（for 循环后，旧的 Entry 数组不再援用任何对象）do {
                Entry<K,V> next = e.next;
                int i = indexFor(e.hash, newCapacity); //！！从新计算每个元素在数组中的地位
                e.next = newTable[i]; // 标记[1]
                newTable[i] = e;      // 将元素放在数组上
                e = next;             // 拜访下一个 Entry 链上的元素
            } while (e != null);
        }
    }
}

newTable[i]的援用赋给了 e.next，也就是应用了单链表的头插入方式，同一地位上新元素总会被放在链表的头部地位；

这样先放在一个索引上的元素终会被放到 Entry 链的尾部(如果产生了 hash 抵触的话），这一点和 Jdk1.8 有区别，下文详解。

在旧数组中同一条 Entry 链上的元素，通过从新计算索引地位后，有可能被放到了新数组的不同地位上。

案例

上面举个例子阐明下扩容过程。假如了咱们的 hash 算法就是简略的用 key mod 一下表的大小（也就是数组的长度）。

其中的哈希桶数组 table 的 size=2，所以 key = 3、7、5，put 程序顺次为 5、7、3。

在 mod 2 当前都抵触在 table[1]这里了。

这里假如负载因子 loadFactor=1，即当键值对的理论大小 size 大于 table 的理论大小时进行扩容。

接下来的三个步骤是哈希桶数组 resize 成 4，而后所有的 Node 从新 rehash 的过程。

Jdk8 优化

通过观测能够发现，咱们应用的是 2 次幂的扩大(指长度扩为原来 2 倍)，所以，元素的地位要么是在原地位，要么是在原地位再挪动 2 次幂的地位。

看下图能够明确这句话的意思，n 为 table 的长度，图（a）示意扩容前的 key1 和 key2 两种 key 确定索引地位的示例，

图（b）示意扩容后 key1 和 key2 两种 key 确定索引地位的示例，其中 hash1 是 key1 对应的哈希与高位运算后果。

元素在从新计算 hash 之后，因为 n 变为 2 倍，那么 n - 1 的 mask 范畴在高位多 1bit(红色)，因而新的 index 就会产生这样的变动：

因而，咱们在裁减 HashMap 的时候，不须要像 JDK1.7 的实现那样从新计算 hash，只须要看看原来的 hash 值新增的那个 bit 是 1 还是 0 就好了，是 0 的话索引没变，是 1 的话索引变成“原索引 +oldCap”，能够看看下图为 16 裁减为 32 的 resize 示意图：

这个设计的确十分的奇妙，既省去了从新计算 hash 值的工夫，而且同时，因为新增的 1bit 是 0 还是 1 能够认为是随机的，因而 resize 的过程，平均的把之前的抵触的节点扩散到新的 bucket 了。

这一块就是 JDK1.8 新增的优化点。

有一点留神区别，JDK1.7 中 rehash 的时候，旧链表迁徙新链表的时候，如果在新表的数组索引地位雷同，则链表元素会倒置，然而从上图能够看出，JDK1.8 不会倒置。

JDK8 源码

有趣味的同学能够钻研下 JDK1.8 的 resize 源码，写的很赞:

/**
 * 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 有一个 reHash 的过程就行，相似于 ArrayList 的 resize。

下一节咱们将一起学习下本人手写实现一个渐进式 rehash 的 HashMap，感兴趣的能够关注一下，便于实时接管最新内容。

感觉本文对你有帮忙的话，欢送点赞评论珍藏转发一波。你的激励，是我最大的能源~

不晓得你有哪些播种呢？或者有其余更多的想法，欢送留言区和我一起探讨，期待与你的思考相遇。