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 相干技术文章或行业资讯,欢送大家关注和转发文章!