hashMap是程序员最常使用的一种数据结构,广泛用于各种需要键值对处理的场景:分组、缓存等等。hashMap的api使用非常简单,但是在使用的时候我们还是会有一些疑惑:
- 为什么阿里的编码规范建议在初始化hashMap时尽量传入预估需要存储的数据的数量(其实基本所有的容器初始化时都建议这么做)
- 为什么jdk1.8之前的hashMap在多线程环境下会死循环。当然有人会说,hashMap不是线程安全的,不能在多线程下使用,偏要用出现死循环了怪谁。但是带着这些问题,能让我们多思考,源码为什么要这么设计
- 在扩容的时候还需要再计算元素的hash位置吗
- 当然还有最基本的为什么key要复写hashCode和equals方法就不再赘述了
为什么我会强调jdk1.8,就是因为jdk1.8里面的hashMap做了一些优化,本文也会从jdk1.7和jdk1.8的区别来分析下hashMap的实现原理。
参数
hashMap采用的是数组+链表+红黑数(jdk1.8增加)的方式来存储数据。
Node<K,V>[] table;
int threshold;
float loadFactor;
int modCount;
int size; //map中键值对个数
Node[]table就是最重要的存储数据的结构,很明显是一个数组链表,也叫哈希桶。很明显这个数组的大小非常关键,如何在减少hash冲突的同时,减少map所占用的内存,还要减少resize()发生。
table初始大小设定
在初始化时指定map大小,可以有效降低map扩容带来的性能损耗,查看指定map大小的代码,发现会将你指定的大小转换为一个最接近你指定的cap的2的n次方的值。为什么要这样在后面解析put源码时解释。
/** * Returns a power of two size for the given target capacity. */
int tableSizeFor(int cap) {
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
threshold与loadFactor
loadFactor为负载因子,thresHold = table.length * loadFactor,也就是当size > thresHold时候,要对map进行扩容。默认值负载因子取0.75。
确定桶位置
在put和get时都要查找key值应该落在哪个hash桶里面。因为数组长度n都是2的m次方,那么与n-1进行&运算就相当于取哈希值的低m位,也就是哈希值对n取模(%),效率更高。这也就是为什么数组的长度必须为2的整数次方。
n= table.length(); //数组长度
table[h&(n-1)] //获取首节点
get put流程
这个相信大家已经非常熟悉
V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//初始化tab
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//如果桶位置为空,直接生成node放入即可
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
//桶的链表首节点与key相同,先暂存在变量e中
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) {
//没有相同的key,生成node放在链表尾部
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))))
//存在相同key的节点,还是暂存在e中
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
//!onlyIfAbsent将旧value值覆盖
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//如果size超过了负载阈值,则要扩容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
扩容优化
jdk1.7之所以在多线程环境下可能导致死循环,就是在扩容的时候可能会让链表形成环路。原因是会重新计算元素在新的table里面桶的位置,而且还会将链表翻转过来。这里有很多文章详细分析了,如果产生链表环路从而造成死循环的,我也不再赘述。直接看jdk1.8是如何避免了死循环问题的。
Node<K,V>[] resize() {
//这儿是计算newCap(变为之前两倍)和threshold的地方,有一些边界值的判断,其实很简单
//但是占用篇幅比较大,忽略掉
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;
//只需要计算一个bit的值就能确定桶的位置
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;
}
if ((e.hash & oldCap) == 0),只需要判断一个位是否为0就能确定元素在新桶的位置。
- 记住计算桶位置方法为 h&(n-1),n是2的m次方
- 比如扩容之前比如长度为n=16,m=4; n的二进制为10000;n-1的二进制为1111
可以看到只是多了一个高位bit来进行&值,而hash在这个高位bit位要么是0,要么是1;
- 如果hash值在M+1位是0,那么h&(n-1)还是原值
- 如果hash值在m+1为是1,那么h&(n-1)还是就是原值加上2的m次方,也就是原长度n
如下图所示:
而且链表不再翻转,这样也不会产生多线程下死循环了,当然还是不能在多线程下使用,有太多的地方会产生竞争条件了,会造成数据丢失。
总结
前面的问题都得到答案了吗?
今天的文章JDK1.8 hashMap优化分享到此就结束了,感谢您的阅读。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/14269.html