共计 4779 个字符，预计需要花费 12 分钟才能阅读完成。
1. HashMap 概述：
HashMap 是基于哈希表的 Map 接口的非同步实现(他与 Hashtable 相似，但 Hashtable 是线程平安的，所以是同步的实现)，此实现提供可选的映射操作，容许应用 null 值和 null 键，但他并非有序。
2. HashMap 数据结构与实现原理：
在 jdk1.7 和 jdk1.8 中，HashMap 的数据结构是有所差异的，进行一些优化来解决抵触问题，上面咱们就别离从两个版本的角度来剖析一下他的改变与区别
（一）jdk1.7 版本
在 jdk1.7 版本的时候采纳的是数组 + 链表的模式，也就是采纳了拉链法。
将哈希抵触值退出到每个数组的链表中，他的插入采纳的是头插法的模式 (这种办法最大的弊病就是会使插入值产生环，从而有限循环，前面咱们将具体解说这种办法的弊病操作)，在进行 hash 值计算的时候，jdk1.7 则采纳的是 9 次扰动(4 次位运算 + 5 次异或运算) 的形式进行解决（因为自己目前临时用的 jdk1.8 所以无奈利用源码进行解说，望见谅），除此之外在扩容上也有所不同，在 jdk1.7 中采纳的全副依照原来的形式进行计算（即 hashCode ->> 扰动函数 ->> (h&length-1)），而在 jdk1.8 中则采纳依照扩容后的法则计算（即扩容后的地位 = 原地位 or 原地位 + 旧容量），上面让咱们来具体解说一下 jdk1.8。
（二）jdk1.8 版本
而 jdk1.8 的版本则采纳数组 + 链表 + 红黑树的形式，如下图：
这种办法能够大大优化了哈希抵触的问题，缩小了搜寻工夫，当增加的数目达到阈值的时候能够将链表转换为红黑树的模式，而当红黑树的节点小于 6 的时候就会从红黑树转化为链表的模式（如果不了解红黑树的话，能够参考我的上一篇文章），而在进行插入值的时候则采纳的是尾插法的模式，这种办法解决了成环的状况产生
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;
}下面代码便是对数组进行 put 操作时，节点的判断以及增加，外面有几个外围的办法让咱们一个一个来剖析：
resize()：
这个办法顾名思义 —— 扩容，他在 jdk1.8 的时候进行两次调用，第一次是在数组进行初始化的时候对其进行扩容，而第二次则是在数组满的工夫进行的扩容，一次是开始，一次则是快完结的时候，让咱们点进去来具体查看一下他在外部所作的操作及含意：
final Node<K,V>[] resize() {Node<K,V>[] oldTab = table; // 定义老数组
int oldCap = (oldTab == null) ? 0 : oldTab.length; // 判断老数组是否为空，来实现初始化扩容操作
int oldThr = threshold; // 使初始容量临时为创立数组时产生的容量，默认为 16
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; // 双重容量，也能够了解为进行扩容
}
else if (oldThr > 0) // 初始容量处于阈值
newCap = oldThr;
else { // 零初始阈值示意应用默认值
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {float ft = (float)newCap * loadFactor; // 进行与加载因子的乘积，此时示意在主动扩容之前，数组达到多满的一种度量，当超过这个乘积值的时候才进行扩容，加载因子的默认值为 0.75
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;
}从中咱们能够看出，扩容办法对数组初始化以及为空都进行了具体的判断，许多人看到这里都会问为什么加载因子的默认值为 0.75 呢？那么这个问题咱们会在接下来的面试典型题中进行简略的解释。让咱们回到下面的 put 办法中持续剖析。
hash(key)
这个办法也是咱们的重点，他是为了保障充分利用数组的每个地位 (下标) 并大大解决哈希抵触问题而诞生的，在 jdk1.7 中咱们提到了计算 hash 的时候进行了 9 次扰动，而在 jdk1.8 中咱们仅仅应用了 2 次扰动就进行了 hash 值的计算，
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
从下面代码能够看出他是通过 key.hashCode()进行高 16 位和低 16 位进行了一次异或运算失去的，缩小了 hash 的碰撞问题。
两个次要的办法剖析完了，让咱们来整体形容一下 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，如果超过，进行扩容。
至此咱们的解说结束，上面来讲述一下面试过程中所遇到的一些面试题。
面试过程中的典型问题
1. 为什么采纳 hashcode 的高 16 位和低 16 位异或能升高 hash 碰撞？hash 函数能不能间接用 key 的 hashcode？
因为 key.hashCode 调用的是 key 键值类型自带的哈希函数，他返回的是一个 int 类型的散列值，咱们都晓得 int 类型的 -2147483648~2147483647** 大概有 40 亿的空间，而在咱们的数组中容量仅仅为 16 个，所以就会造成数组无奈承载值的状况，因为必须是均匀分布能力无效地防止哈希碰撞的问题，所以就要对其进行取模运算。
2.HashMap 默认加载因子为什么抉择 0.75？
因为进步空间利用率和 缩小查问老本的折中，次要是泊松散布，0.75 的话碰撞最小，因为在 hashmap 中影响性能的因为有俩个，一个是初始容量，一个便是加载因子，如果加载因子小的话就会造成空间利用率低，并进步了 rehash 的次数，为了保障最大水平上缩小 rehash 的次数，0.75 是最合适的规范数也是折中的一种思考。
3.jdk1.7 插入数据形式有什么弊病？
下面我提到了造成环，那么到底是为什么呢，因为在应用的过程中，如果一个线程在插入一个节点的时候，另一个线程也在插入节点，而且两个线程插入的都是对方线程上的几点，这样当进行头插的时候会使链表产生反转，便造成了环状，造成了死循环，如下图：
最初
感激你看到这里，看完有什么的不懂的能够在评论区问我，感觉文章对你有帮忙的话记得给我点个赞，每天都会分享 java 相干技术文章或行业资讯，欢送大家关注和转发文章！
