HashMap底层结构及扩容机制详解
在Java 7及之前的版本中,HashMap的底层数据结构主要是数组加链表。具体实现如下:
数组:HashMap的核心是一个Entry数组(
Entry<K,V>[] table
),这个数组的大小总是2的幂。每个数组元素是一个单一的Entry节点,或者是一个链表的头节点。
链表:当两个或更多的键经过哈希运算后映射到数组的同一个索引上时,就会形成链表。Entry节点包含了键值对以及指向下一个Entry的引用,以此来解决哈希冲突。
Java 8及之后版本
从Java 8开始,HashMap的底层结构除了数组加链表之外,还引入了红黑树,以优化在链表过长时的查找性能。结构变为数组加链表加红黑树。
数组:同样是一个Entry数组(Java 8中称为Node),大小仍然是2的幂,用于快速定位。
链表:在哈希冲突时,键值对仍会以链表形式链接在一起。但与Java 7不同的是,Java 8对链表的处理增加了转换为红黑树的条件。
红黑树:当一个桶中的链表长度超过8且HashMap的容量大于64时,链表会被转换成红黑树。这种转换提高了在大量哈希冲突情况下的查找效率,因为红黑树的查找时间复杂度为O(log n),相较于链表的O(n)有显著提升。
数据插入
在JDK1.7的时候,采用的是头插法。
在JDK1.8改成了尾插法,这是因为头插法在多线程环境下扩容时可能会产生循环链表问题。
线程不安全
无论是JDK1.7还是1.8都是线程不安全的。下图是1.8中的put方法。
tab是就是HashMap的数组table,第一个if判断时做了赋值。框起来的部分表示如果没有hash冲突就直接在数组上插入元素,但是如果两个线程hash一样且都进入到了这个if下,线程1先执行的插入数据,线程2会覆盖1插入的数据。
那么什么是循环链表问题呢?这就不得不介绍一下HashMap的扩容机制了。
扩容机制
首先讲几个HashMap的属性。
- table:数组,存放链表或红黑树的头节点
- Node:节点,属性有hash、key、value、next(下一个节点)
- size:元素个数,即节点node个数,非数组长度
- Capacity:当前数组长度
- loadFactor:加载因子,默认为0.75f,简称loadFactor
- threshold:扩容门槛,值为capacity*loadFactor,size达到这个门槛就扩容
当size大于threshold时,就会进行扩容
resize()
。
- 创建一个新的数组,长度为原数组的两倍
-
遍历所有Node节点,重新计算index值(Java8首先会重新计算hash值),放到新数组里,存在hash冲突的就放到链表或红黑树。
为什么要重新计算index值,直接把张三这条链表复制到新的数组中不行吗?
答案是不行的,因为index规则是根据数组长度来的。
所以index的计算公式是这样的:
- index = HashCode(key) & (Length - 1)
循环链表问题
循环链表问题理解起来比较麻烦,如果理解不了就知道JDK1.7HashMap扩容的时候有这么回事就行。但是可能是我自己太笨了,万一大家一看就懂了呢。
我们来看一下Java1.7扩容的源码。
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
transfer(newTable);
table = newTable;
threshold = (int)(newCapacity * loadFactor);
}
void transfer(Entry[] newTable) {
Entry[] src = table;
int newCapacity = newTable.length;
for (int j = 0; j < src.length; j++) {
Entry<K,V> e = src[j];
if (e != null) {
src[j] = null;
do {
Entry<K,V> next = e.next;
//重新计算元素在数组中的索引
int i = indexFor(e.hash, newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
} while (e != null);
}
}
}
重点在于transfer方法,作用是重新计算index值然后将旧数组中的数据迁移到新数组
循环链表的产生:
原因:
假设我们有两个Thread都在执行resize方法,Thread1第一步刚执行完第23行
Entry<K,V> next = e.next;
就卡住了,这时Thread2执行完了resize方法。
- Thread1第一次执行完Entry<K,V> next = e.next后,e=张三,next=李四,也就是说第二步执行李四的插入
- Thread2执行完resize后,李四的next变成了张三
- 此时又回到Thread1,第二次执行Entry<K,V> next = e.next后,e=李四,next=张三,也就是说又要执行张三的插入,循环链表产生!
由此我们知道了循环链表产生的关键在于头部插入元素A时,元素A的next元素B的next是元素A本身,所以Java8采用了尾插法,避免了循环链表。
求赞!求关注!!以后会更新更多有用的内容!!!꒰⑅•ᴗ•⑅꒱
保佑大家代码永无bug ╰( ´︶` )╯
以上就是电脑114游戏给大家带来的关于HashMap底层结构及扩容机制详解全部内容,更多攻略请关注电脑114游戏。
电脑114游戏-好玩游戏攻略集合版权声明:以上内容作者已申请原创保护,未经允许不得转载,侵权必究!授权事宜、对本内容有异议或投诉,敬请联系网站管理员,我们将尽快回复您,谢谢合作!