前言
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)，这就类似二分查找。(红黑树原理便是上面讲的，总结一下)
写在最终
篇幅很长，能看到最终很不容易，给自己一个 大大的赞 吧！
假如觉得写的不错，就给个赞再走吧~
创造实属不易，你的肯定是我创造的动力，下次见！
假如本篇博客有任何错误的当地，请咱们批评指正，不胜感激。
