前言

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

本文着重叙述 HashMapJDK 1.7Jdk 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及曾经 -> 数组 + 链表

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

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 按位与就相当于 lengthh 求模运算了。因而 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 底层是一个 数组 + 链表 的一个结构。它会经过核算 keyhash值 ,进而与 length - 1 进行按位与算出数组地点的下标。假如算出的 index 和其它元素重复,咱们称之为 哈希磕碰 ,这时会将新来的 键值对 放在其对应数组下标的链表的第一位(头插法) 。

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

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

前两个节点算出来的 index 都是 4,发生了 hash磕碰,因而第二个节点经过 头插法 的办法,放到了链表的头部,第三个节点的 index1,放在了数组下标为 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刺进查找删去 的中心原理都相同,这儿做个总结

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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:刺进的新节点坐落树的根上、其父节点是黑色

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

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

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

红黑树的平衡

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

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

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

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

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

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

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

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

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

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

新版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.7HashMap ,由于原理仍是差的不多,因而仍是能容易看懂的。在新版的 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),这就类似二分查找。(红黑树原理便是上面讲的,总结一下)


写在最终

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

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

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

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