HashMap理解

日期:2018-11-21       浏览:386

一 底层实现原理

在jdk1.8之前的版本中,HashMap存储结构是数组+链表。计算保存对象的hash值除数组长度求余,根据余数将该对象保存到哪个链表。这种方式就要有很好的 hash 函数,尽量将数据平均保存到不同链表上。但是再好的hash 函数的选择也很难将数据均匀分布,而且当HashMap中有大量元素都保存在同一个链表上时,此时的查询效率将是O(n),当然这是最极端的情况。
jdk1.8之前版本的HashMap中,当调用 put 方法添加元素时,如果新元素的 hash 值或保存的 key 在原 HashMap 中不存在,则会检查要保存到的链表的 size 是否大于负载因子 threshold,如果达到扩容要求,则将原数组进行扩容,扩容后的数组容量是原数组的二倍,并将原Map中的元素重新计算hash值然后保存到新的数组中,如下图所示,假设一个HashMap的数组长度是4,负载因子是 0.75,有新的元素要保存到下标为2的数组上,这时就会触发 HashMap 的扩容。
HashMap数据结构及扩容
HashMap数据结构及扩容

二 不安全的HashMap

上面我们看到了HashMap的扩容过程,HashMap在扩容的过程中并没有对其进行加锁处理,也就是多个线程可以同时对同一个HashMap进行扩容处理,多线程同时扩容时很容易产生数据不一致,循环引用等并发问题。

三 链表与红黑树之间的转换

在jdk1.8及之后的版本中,当链表的长度等于8时,HashMap就会将链表的结构转换为红黑树,也就是 HashMap 的存储结构变为了数组+链表+红黑树。删除元素和扩容时,如果树中的元素个数较少时会对树进行修剪调整或还原为链表结构,以提高后续操作性能。
为什么长度为8时转红黑树?我们从查询平均时间复杂度上对比一下。
  • 链表平均时间复杂度 n/2
  • 红黑树平均时间复杂度 logn(以2为底)
我们再来对比一下
数据量 logn n/2 性能高
4 log4 = 2 4 / 2 = 2 链表 = 红黑树
8 log8 = 3 8 / 2 = 4 链表 < 红黑树
通过以上对比我们就知道为什么以8为转换基准了。
什么时候红黑树还原为链表呢?当树中节点数小于等于6时就会将树还原为链表,为什么是6,不应该也是8嘛?如果我们频繁的操作一个HashMap向其中添加元素,然后删除元素,每次都保存在同一个数组上,那就会频繁的触发链表与红黑树之间的转换,链表转树的效率是很低的。
扫码关注有惊喜

(转载本站文章请注明作者和出处 qbian)

暂无评论

Copyright 2016 qbian. All Rights Reserved.

文章目录