【精讲】深入剖析HashMap的底层原理

前言

HashMap 是 Java 中一个很常用的容器，不过也是面试的重灾区，问题的办法多种多样。

本文着重叙述 HashMap 在JDK 1.7 和 Jdk 1.8 下的原理以及一些面试或许会被问到的问题。

现在先来看看自己能否答复得上这些问题，答案能得满分吗？

1.为什么要用 HashMap，你知道其底层原理吗？

2.HashMap 中的 hash 值有什么用？

3.为什么 HashMap 中的数组长度有必要是 2 的幂次方？

4.为什么建议用 String Integer 这样的包装类作为 HashMap 的键？

5.JDK 1.7中为什么会构成死循环？

6.红黑树的概念，它的原理是什么，为什么要用它？

...

假如对于上面这些问题还不清楚，别急，和我一同往下看。

✔️ 本文阅览时长约为: 20min

为什么要用到 HashMap

在 Java 中咱们经常用 ArrayList 作为容器来贮存一些数据，它的底层是由次序表完结的，自然查询快而且是随机拜访，可是在其中间增删功率就很慢了。那它的兄弟 LinkedList 怎样样呢？LinkedList 底层是由链表完结的，链表咱们知道 增删功率高，可是查找功率慢，每次查询都要从头节点开端向后查找 。难道没有一种容器能归纳它们的长处吗？诶有，这时分该咱们的 HashMap 登场了。

⭐⭐ HashMap 经过键值对进行存储，经过键进行查询，在 JDK 1.7及曾经 底层完结是一个 数组 + 链表 的形式，而在 JDK 1.7今后 底层是 数组 + 链表 + 红黑树 。

JDK 1.7及曾经的 HashMap

// 数组结构
transient Entry<K,V>[] table;
// 这是链表结构中的节点，用于处理 hash磕碰，加入一个 next 记录下一个节点
Entry(int h, K k, V v, Entry<K,V> n) {
    value = v;
    next = n;
    key = k ;
    hash = h;
}

JDK 1.7及曾经 -> 数组 + 链表

HashaMap HashMap 除了 map 总和 hash 有关 ，那么这个 hash 到底是什么？咱们知道 Object 类有一个 native 办法叫做 hashCode，回来的是一个 int 类型的值，那它又有什么用呢？没错，它在咱们的 HashMap 中体现出来了。咱们来看看 HashMap 中的 hash 办法。

final int hash(Object k) {
    // k 是作为当时键的方针
    int h = 0;
    if (useAltHashing) {
        if (k instanceof String) {
            return sun.misc.Hashing.stringHash32 ((string) k);
        }
    h = hashSeed;
    }
    // 每个方针都有一个 hashCode 值
    h ^= k.hashCode() ;
    h ^= (h >>> 20) ~ (h >>> 12);
    // 经过这些位运算来得到 HashMap 中的 hash
    return h ^ (h >>> 7) ^ (h >>> 4);
}

在 HashMap 中经过 hash() 能够得到一个值，而这个值与后续存放数据的下标有关。

// 确定当时键值对存放在数组中的下标
static int indexFor(int h, int length) {
    // 用核算出的 hash 按位与 上(length - 1)，算出对应数组的下标
    return h & (length - 1);
}

这儿的 length 是有一个隐藏的机制，它最开端默认是 16，后面遇到扩容都会 << 1，也便是说 length 永远是 2的幂次方 。那这 … 是为什么呢？

⛅ 咱们再来看看这个办法回来的是什么。h & (length - 1) ，这句代码目的是求出数组中的下标，用来存放当时这对键值对，那求出的值有必要在 0 - (lenght - 1) 之内，因而咱们能够斗胆猜想，这便是一个求模运算！可是 & 和 % 肯定是不同的操作，按位与怎样就相当于求模运算了呢？ 这正是因与 length 特别的限制有关。由于 length 是一个 2的幂次方的数 ，因而减去1后，低位每一位都是1。比方 length = 16，减去以1后便是 00001111，这时分再与 h 按位与就相当于 length 和 h 求模运算了。因而 length是2的幂次方 ，此外转化成二进制后，1 散布得很均匀，与 h 按位与时得出的成果在 length 上也是均匀的，然后在数组中也是均匀散布，所以有用削减了 hash磕碰 ，而且位运算的功率是高于求模运算的。

public v put(K key, V value) {
    if (key == null)
        return putForNullKey(value);
    // 经过 key 核算hash值
    int hash = hash(key);
    // 经过 key 找到数组中待存放的下标
    int i = indexFor(hash, table.length);
    // 链表
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        object k;
        // 假如这个数组下标中有元素，开端遍历链表
        if (e.hash == hash && ((k = e.key) == key || key .equals(k))) {
            // 假如两个 hash 值相同，或许键相同，则修正 value
            V oldValue = e.value;
            e.value = Value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    modCount++;
    // 或许两个 hash 值不同，但核算出的 index 相同，这就发生了 hash磕碰
    // 运用头插法，将其放在链表头部
    addEntry (hash, key, value, i)
    return null;
}

addEntry() 内部调用 createEntry()。

void createEntry (int hash, K key, v value, int bucketIndex) {
    Entry<K,V> e = table[bueketIndex];
    // 注意这儿将 e 传进去
    // 也便是说这儿运用的是 头插法
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}

⚡ JDK 1.7 用的是 头插法 ，这是构成 HashMap 构成死循环的原因之一。⚡

咱们刚刚看了 put() 的源码，做个总结，到这儿咱们知道 HashMap 底层是一个 数组 + 链表 的一个结构。它会经过核算 key 的 hash值 ，进而与 length - 1 进行按位与算出数组地点的下标。假如算出的 index 和其它元素重复，咱们称之为 哈希磕碰 ，这时会将新来的 键值对 放在其对应数组下标的链表的第一位(头插法) 。

现在咱们从微观上来看看 put() 的整个进程。

PS：做动画的时分想成尾插了，这儿咱们注意一下，不要被误导，JDK 1.7便是头插法

前两个节点算出来的 index 都是 4，发生了 hash磕碰，因而第二个节点经过 头插法 的办法，放到了链表的头部，第三个节点的 index 是 1，放在了数组下标为 1 的当地。

好了，put() 咱们讲完后，get() 就不在话下了，它的原理仍是和 put() 相同，先经过 hash 核算出对应数组的下标，然后就去链表中遍历，最终回来相应的成果。现在来讲讲几个重要的变量。

// 初始巨细
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 向左位移4位，也便是16
// 加载因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;

HashMap 默认巨细便是 16，这个加载因子与它的巨细乘积叫作 threshold 阈值，一旦超越了这个值，HashMap 就会进行一次扩容。不过请咱们考虑一下，HashMap中扩容会构成什么问题？

没错，一旦扩容 HashMap 中的数组长度就会增加，而咱们核算下标正是经过 hash 和 (length – 1)进行按位与 ，因而扩完容后下标肯定会变，那本来贮存的数据就会被打乱。在 JDK 1.7 中的处理办法是扩完容后(创立一个新的数组，巨细是本来的2倍)，会遍历每一个 entry ，进行 rehash ，再次核算 hash 和 数组下标，然后放到新的数组中去。

// 假如当时 size > 阈值，扩容之后就会调用这个办法，进行 rehash
void transfer(Entry[] newTable, boolean rehash) { 
    int newCapacity = newTable.length; 
    for (Entry<K,V> e : table) { 
        while(null != e) {
            // 得到当时节点的下一个节点 next
            // 留意一下这段代码，HashMap构成死循环时会讲到
            Entry<K,V> next = e.next; 
            if (rehash) { 
                // 从头核算hash
                e.hash = null == e.key ? 0 : hash(e.key); 
            } 
            // 每一个 entry 从头核算数组所对应的下标
            int i = indexFor(e.hash, newCapacity;
            e.next = newTable[i]; 
            // 放到新的数组中去
            newTable[i] = e;
            e = next; 
        } 
    } 
}

✈️ HashMap 的刺进， 查找， 删去 的中心原理都相同，这儿做个总结。

操作	原理
刺进	先核算 key 的 hash 值，依据 hash 值找到数组方位，再往链表中添加元素
查找	先核算 key 的 hash 值，依据 hash 值找到数组方位，再遍历链表，找到对应的节点
删去	先核算 key 的 hash 值，依据 hash 值找到数组方位，再从链表中找到对应节点，然后删去节点

为什么说 HashMap 会构成死循环？

在多线程下扩容 HashMap 会构成死循环，咱们从头回忆 transfer() 后再看看正常状况下的扩容。

成功扩容后，咱们发现链表被倒置了，现在再来看看 多线程 下对 HashMap 进行扩容构成环形数据结构的状况。

假设现在有两个线程在一同扩容 HashMap，当 线程A 履行到 Entry<K,V> next = e.next 时被挂起，待到 线程B 扩容完毕后，线程A 从头拿到 CPU时刻片 。

由于 线程A 在扩容前履行过 Entry<K,V> next = e.next，因而现在 线程A 的 e 和 next 分别指向 key("cofbro") 和 key("cc")。

现在 线程A 开端扩容，首先履行 newTab[i] = e，将 entry 刺进到数组中，随后依照次序履行 e = next，然后进入下一个循环 Entry<K,V> next = e.next，由于此刻HashMap现已被 线程B 扩容完结，所以此刻的 next = key("cofbro") 。

现在继续履行上个操作流程，不过由于 key("cofbro").next 没有节点了，因而 next 是 null。

咱们看到这个时分又会将 key("cofbro") 插到链表的头部，死循环就这样发生了。

JDK 1.7今后的 HashMap

咱们现在知道 HashMap 结合了 ArrayList 的查询功率高的特色以及 LinkedList 刺进功率高的特色，可是假如咱们要存储的数据过于巨大，肯定会构成很屡次的 哈希抵触，这样一来，链表上的节点会堆积得过多，在做查询的时分功率又变得很低，又失去了 HashMap 本来的特色。

那么 JDK 1.8 就做出了改变，运用 数组 + 链表 + 红黑树 的结构。当节点数不大于8时，仍是一个链表结构，只不过刺进节点时变成了 尾插法 ，当节点数大于8后，将从链表结构转化成红黑树结构，复杂度也从 O(n) 变成 O(logn)。

什么是红黑树

解说 HashMap 原理之前，先来说说 什么是红黑树。

红黑树 其实是一颗特别的 二叉排序树，它有以下限制：

1.每一个节点都有一个色彩，非黑即红

2.一切 null节点都是叶子节点，而且和根节点相同，都是黑色

3.一切赤色节点的子节点都是黑色

4.从任一节点到其叶子节点的一切途径上都包括相同数目的黑节点

上面这些限制的首要效果其实是保证 从根节点开端向下查找到叶子节点，其最长途径不多于最短途径的2倍，也便是说咱们去查询一个数据，最坏状况只比最好状况差一倍，这样提高了全体的查询速度。而 红黑树 本身便是一颗特别的 二叉排序树，因而它的查询复杂度从链表的 O(n) -> O(logn) 。

♻️ 为了坚持红黑树上述特性，咱们每次刺进、删去都需要对其进行一定的处理，才干使得这课红黑树一向坚持这它的特色，这儿我以刺进来举例。

红黑树的变色

由于有 性质4 的存在，因而每次刺进的节点都先是 赤色。

1️⃣ 状况1：刺进的新节点坐落树的根上、其父节点是黑色

2️⃣ 状况2：假如刺进节点的父节点和父兄节点都是赤色，父节点，父兄节点、祖父节点都要变色。

红黑树的平衡

为了坚持 红黑树 的相对平衡以及维护红黑树特性，每次刺进时会判别是否进行旋转。

1️⃣ 状况1：当刺进节点的父节点是赤色、父兄节点是黑色且刺进节点是左子树，这时进行一次右旋转。

进程：刺进节点7，将根节点的左子树改为新刺进节点的兄弟节点，再将根节点作为新刺进节点的兄弟节点，最终把新刺进节点的父节点改为根节点。

有点懵的话咱们再来看看动画:

2️⃣ 状况2：当刺进节点的父节点是赤色、父兄节点是黑色且刺进节点是右子树，这时进行一次左旋转。

进程：刺进节点30，将根节点的右子树改为新刺进节点的兄弟节点，再将根节点作为新刺进节点的兄弟节点，最终把新刺进节点的父节点改为根节点。

有些复杂的平衡往往需要经历两次旋转才干完结，比方 左右旋转（先左再右） 或许 右左旋转（先右再左），不过都是基于上述两种变换完结的，搞懂一次旋转后，二次旋转是没有问题的，这儿就不赘述了。

新版HashMap原理

新版的 HashMap 将本来的 Entry 改了个名字变成 Node 了，而且新增了 TreeNode 节点，专门为红黑树指定的。

// 便是本来的 Entry<K,V>
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;
    }   
}
// 红黑树节点
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red;
    // 这儿有 next 是由于转化成红黑树结构后，仍然维护着链表结构
    // 并不会由于转化成红黑树后而将链表结构删去掉
    TreeNode(int hash, K key, V val, Node<K,V> next) {
        super(hash, key, val, next);
    }
    final TreeNode<K,V> root() {
        for (TreeNode<K,V> r = this, p;;) {
            if ((p = r.parent) == null)
                return r;
            r = p;
        }
    }
}

相同的，咱们看原理仍是从 put() 入手，跟着我来一同看一遍 put() 工作原理。

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为空或许length等于0，就调用resize办法进行初始化（第一次放元素就会第一次调用resize）
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 经过hash值核算下标，将下标方位的头节点赋值给p，假如p为空则在数组对应方位添加一个节点
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        // 假如数组的当时下标方位不为 null，则进行遍历
        // 假如当时节点的key和hash值和之前贮存的相同，代表找到了方针节点，将其赋值给 e
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 假如 p 节点类型是 TreeNode，则调用红黑树的putTreeVal办法查找方针节点
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                // 这儿便是调用链表结构的查找办法
                // 假如p的next节点为空时，则新增一个节点并刺进链表尾部，注意这儿从头插法改为尾插法
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 假如节点数查过8，调用treeifyBin()转为红黑树结构
                    if (binCount >= TREEIFY_THRESHOLD - 1)
                        treeifyBin(tab, hash);
                    break;
                }
                // 假如e节点的hash值和key值都与传入的相同，代表找到了方针节点
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                // 将p指向下一个节点
                p = e;  
            }
        }
        // 找到方针节点后，用新值替换旧值并回来旧值
        if (e != null) {
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    // 假如刺进节点后节点数超越阈值，则调用resize办法进行扩容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

现在再来看看是怎么构建红黑树的：

final void treeify(Node<K,V>[] tab) {
    TreeNode<K,V> root = null;
    for (TreeNode<K,V> x = this, next; x != null; x = next) {
        next = (TreeNode<K,V>)x.next;   // 获得下一个节点 next
        x.left = x.right = null;    // 初始化红黑树
        if (root == null) {  // 初始化根节点
            x.parent = null;
            x.red = false;
            root = x;
        }
        else {
            K k = x.key; // 得到每一个 key
            int h = x.hash; // 得到每一个 hash值
            Class<?> kc = null;
            // 从根节点遍历，寻找刺进方位
            // 依据红黑树的特性，向左越小，向右越大
            for (TreeNode<K,V> p = root;;) {
                int dir, ph;
                K pk = p.key;
                if ((ph = p.hash) > h)
                    // 向左查找
                    dir = -1;
                else if (ph < h)
                    // 向右查找 
                    dir = 1;
                // 假如两个hash值相同，就比较key
                else if ((kc == null && 
                          (kc = comparableClassFor(k)) == null) ||
                         (dir = compareComparables(kc, k, pk)) == 0)
                    // 比较当时这个节点和遍历到的节点的巨细
                    dir = tieBreakOrder(k, pk);
                TreeNode<K,V> xp = p;
                // dir <= 0 则向p左面查找,否则向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);
}

在前面咱们看过 JDK 1.7 的 HashMap ,由于原理仍是差的不多，因而仍是能容易看懂的。在新版的 HashMap 中增加了 TREEIFY_THRESHOLD 变量，目的便是用来标识是否将链表转化成红黑树。此外还有变化便是 resize(扩容时) 不再像 JDK 1.7 那样从头核算hash了。

✔️ JDK 1.8是这么优化的：将扩容后的长度 – 1 按位与 上本来核算出的key的hash值，这样的长处是：

1.HashMap中核算出的 hash 转化成二级制后 0 1能够看成是均匀散布的，这样与 (length - 1) 按位与核算出来的值在数组中也仍是均匀散布的

2.因而进行按位与会有两种成果。某个 node 的hash对应的 (length - 1) 最高位的数假如是1，新数组下标便是 oldIndex + 旧数组的巨细，假如是0，新数组下标便是 oldIndex，便是原索引方位

3.相比上个版本的 HashMap 少了一次从头核算hash的进程，提高了一定的功率

// JDK 1.8 的 扩容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) {
        // 假如旧表的巨细比 Integer.MAX_VALUE 还大这就没办法扩容了，直接回来旧表
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        // 扩容，将newCap变成oldCap的2倍
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            // 新的阈值改为本来的两倍
            newThr = oldThr << 1;
    }
    else if (oldThr > 0)
        newCap = oldThr;
    else {
        // 这时将阈值和容量设置成初始值，由于初次创立 HashMap 就会调用一次 resize
        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;
                // 假如e.next为空, 说明旧表中该方位只需1个节点，依据新的索引，放进新表中
                if (e.next == null)
                    // 这便是刚刚讲到的新版 HashMap 中核算下标的办法，很精妙
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    // 有哈希抵触，红黑树中进行重hash
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else {
                    // 有哈希抵触，链表中进行重hash
                    // 下标仍然是 本来方位的 节点 
                    Node<K,V> loHead = null, loTail = null;
                    // 下标是 原方位下标 + oldCap 的节点
                    Node<K,V> hiHead = null, hiTail = null; 
                    Node<K,V> next;
                    do {
                        next = e.next;
                        // 假如e的hash值相对旧表的容量的最高位不是1，则扩容后的索引和本来相同
                        if ((e.hash & oldCap) == 0) {
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        // 假如e的hash值相对旧表的容量的最高位不是1，则扩容后的索引是原索引 + oldCap
                        else {
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    // 旧表的数据从头填充到新表上 原索引 的节点
                    // 将最终一个节点的next设为空
                    // 并将新表上索引方位为 原索引 的节点设置为头节点
                    if (loTail != null) {
                        loTail.next = null;
                        newTab[j] = loHead;
                    }
                    // 旧表的数据从头填充到新表上 原索引+oldCap 的节点
                    // 将最终一个节点的next设为空
                    // 并将新表上索引方位为 原索引+oldCap 的节点设置为头节点
                    if (hiTail != null) {
                        hiTail.next = null;
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    // 回来扩容后的新表
    return newTab;
}

新版的HashMap的 put()原理到这儿就讲完了，查询和删去仍是之前说的，只需懂了 put()，再去看它们源码的时分也是很轻松了，到这儿我现已写了太多了，就不再拿出来讲了。

接下来咱们答复一下开头提出的问题。

问题总结

为什么要用HashMap，你知道底层原理吗？

答：HashMap结合了查询功率快以及增删功率快的长处，作为一个容器对错常可贵的。HashMap存的都是一个个键值对，咱们经过键值对对其进行修正和拜访，在 JDK 1.7及曾经底层是一个数组+链表的结构，当发生哈希抵触时，就将节点采用头插法的办法放在链表头部。在JDK1.7今后底层是一个数组+链表+红黑树的结构，相同的，发生哈希抵触时，依旧是插到链表里去，只不过现在是尾插法，这样做便是为了防止呈现循环数据，别的当链表节点大于8时，会转成红黑树进行存储，但这并不代表删去了链表结构，链表结构依然存在，当节点数量从头小于8后，红黑树又会从头变成链表结构。(再说说get(),put()办法原理就差不多了)。

2.HashMap 中的 hash 值有什么用？

HashMap中的hash值是由hash函数发生的，它是保证HashMap能正常工作的基石，一切键值对进行存储时的方位都是靠它和 (length – 1) 进行位运算得出的，咱们进行刺进、拜访、删去都有必要先得到对应的hash值，再经过它算出对应的索引值，最终才干操作对应的键值对。

3.为什么 HashMap 中的数组长度有必要是 2 的幂次方？

由于数组长度减一按位与上hash()，从成果上来看等同于 h % length ，恰好在咱们的数组范围内。此外，数组长度是2的幂次方保证了在与 hash() 进行按位与时，低位的每一位都是1。又由于咱们经过 hash()核算出的值能够认为是均匀散布的，因而二者进行按位与后发生的值，也便是索引值，在数组当中便是散布均匀的。别的，在JDK1.8后，由于有上述的特色，当扩容时咱们不必再从头核算hash值，只需要判别当时节点对应的最高位上是否是1，假如是1，就代表新索引方位为oldIndex + oldCap，假如是0，则新索引方位仍是oldIndex。然后削减一次hash核算，提高功率

4.为什么建议用 String Integer 这样的包装类作为 HashMap 的键？

首先，这些类内部重写了hashCode()，equal()办法，本身就遵循HashMap中的规范，能够有用减小hash磕碰的概率。其次，这些类都是final类型，也便是说key是不可变的，防止同一个方针的核算出的hash值不相同。除了上面所说的，很多容器都不能用根本类型而且也不能存null值也是一个原因。

5.JDK 1.7中为什么会构成死循环？

JDK1.7中在链表中添加节点采用的是头插法，这就导致两个线程一同去扩容HashMap的时分会呈现一个线程履行到一少半，比方履行得到 e 和 next，这时另一个线程抢占了CPU时刻片而且将HashMap扩容完结，此刻HashMap中链表是一个倒序。这个时分第一个线程再去扩容时，第一次得到的e就会去拜访两次，在链表中刺进两次，这就会导致循环数据的发生，然后拜访时构成死循环。虽然说JDK1.8处理了这个问题，但它依然是线程不安全的，并发场景下仍是要运用ConcurrentHashMap。

6.红黑树的概念，它的原理是什么，为什么要用它？

红黑树是一颗特别的二叉查找树，它有每一个节点都有一个色彩，非黑即红、一切 null节点都是叶子节点，而且和根节点相同，都是黑色等特色。引进它的含义便是为了处理hash磕碰次数过多，导致链表长度太大，查询耗时的问题。有了红黑树，咱们查询功率就提升至O(logn)，这就类似二分查找。(红黑树原理便是上面讲的，总结一下)

---

写在最终

篇幅很长，能看到最终很不容易，给自己一个 大大的赞 吧！

假如觉得写的不错，就给个赞再走吧~

创造实属不易，你的肯定是我创造的动力，下次见！

假如本篇博客有任何错误的当地，请咱们批评指正，不胜感激。