HashMap源码
2021/5/8 1:25:11
本文主要是介绍HashMap源码,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
HashMap源码阅读记录
- 先说说1.7
- 在1.8的优化
- 讲一下put方法,插入的流程
- 扩容的过程 resize
先说说1.7
1.7的时候主要存在几个问题
- key的hash值计算方式很复杂
- 在扩容的时候,因为使用的是尾插法,所以在多线程对这个变量进行操作的时候会产生一个环,导致死循环
- 最大的问题就是hash冲突问题,当一个桶里元素过多的时候,就相当于一个很长的链表,查询的时候需要从头到尾遍历一遍,时间复杂度是O(n)。
在1.8的优化
- hash计算方式,是通过key的hashcode的高16位与hashcode进行异或运算
/** * Computes key.hashCode() and spreads (XORs) higher bits of hash * to lower. Because the table uses power-of-two masking, sets of * hashes that vary only in bits above the current mask will * always collide. (Among known examples are sets of Float keys * holding consecutive whole numbers in small tables.) So we * apply a transform that spreads the impact of higher bits * downward. There is a tradeoff between speed, utility, and * quality of bit-spreading. Because many common sets of hashes * are already reasonably distributed (so don't benefit from * spreading), and because we use trees to handle large sets of * collisions in bins, we just XOR some shifted bits in the * cheapest possible way to reduce systematic lossage, as well as * to incorporate impact of the highest bits that would otherwise * never be used in index calculations because of table bounds. */ static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
- 使用了尾插法,解决了死循环的问题
- 计算初始容量的方式发生改变,1.7的时候是通过对1进行左移运算,直到找到比入参容量大的一个2的n次幂的数。1.8的时候,用了一种更优雅的方式,就是通过5个移位运算,得到一个低位全是1的值,最后得到一个初始容量。
/** * Returns a power of two size for the given target capacity. */ static final 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; }
- 最重要的就是使用了数组+链表+红黑树。在数组长度大于64并且链表的长度大于8的时候会转换成一个红黑树。这样他的查询效率得到提升,以前是O(n),红黑树是O(logn)
讲一下put方法,插入的流程
- 首先通过key的hashcode来计算hash值
- 这个时候看map是否为空,如果为空的话就会先进行一次resize扩容,这时候他的初始容量大小是16
- 通过hash值和hashmap长度-1进行与运算得到桶的索引下标
- 找到桶的位置后,观察这个桶的头节点是否为空,如果是空的话就直接放进去,因为hashmapkey是不允许相同的,所以,如果不为空就检查头节点的key是否与入参的key相同,如果相同的话就直接覆盖value,如果不同就遍历这个链表,如果发现相同的key也进行覆盖,否则通过尾插法插入到链表的最后。
- 当链表的长度大于8并且数组的长度大于64的时候,会转变为红黑树
扩容的过程 resize
这篇关于HashMap源码的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-20测试人员都是画画大神,让我看看谁还不会用代码图?
- 2024-05-20年薪百万的程序员都在用的摸鱼方式……
- 2024-05-19永别了,微服务架构!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了