1.HashMap源码(JDK 8)
2023-08-22 17:58:43 5 举报
HashMap JDK8 源码分析
作者其他创作
大纲/内容
loHead
key=印value=bhash=xxnext=杨
key=杨value=1
hash(key),(n - 1) & hash=2
31
1
......
2
key=印value=bnext=杨
...
假设印和陈的Hash值 & 16(老数组长度)=0假设杨和高的Hash值 & 16(老数组长度)=16
15
1、默认初始容量=16,DEFAULT_INITIAL_CAPACITY = 1 << 4;2、数组容量达到75%就扩容,static final float DEFAULT_LOAD_FACTOR = 0.75f;面试题:为什么加载因子=0.75?因为空间和时间都考虑的情况下,0.75最优
HashCode+位运算,使Hash值尽量散列
4、如果Hash表中的元素是链表结构1)遍历链表上的元素,拆分成两个链表。每个元素的Hash值 & 老数组的长度=0,用loHead为首的链表连接,否则用hiHead为首的链表连接2)loHead链表位置不变,hiHead链表放在基于原来位置往后挪一个旧数组的长度
3
0
key=高value=1next=庞hash=xx
key=杨value=1hash=xxnext=高
this.threshold = tableSizeFor(initialCapacity);
key=印value=b
不同key发生Hash碰撞,并且当前不是红黑树节点TreeNode
演示
resize()
key=陈value=1hash=xxnext=null
否
newCap = DEFAULT_INITIAL_CAPACITY; //默认16newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//扩容阈值=12
数组是否初始化
是否转红黑树
hashMap.put(k,v)
如果key重复,则替换value值
是
数据迁移
HashMap hashMap = new HashMap(10);
用来解决JDK7,多线程扩容死循环问题
4
put
1、容量扩容2倍2、扩容阈值自然也翻倍
当插入链表第9个时,开始转红黑树但是如果Hash表容量<64时,优先做扩容
以上都是采用位运算,而不是取模或者加减乘除。因为位运算二进制最接近机器语言,效率远高于取模
newCap = oldCap << 1newThr = oldThr << 1
new Node[newCap];
hiTail
是否需要扩容
17
loTail
hiHead
3、创建一个新的数组
扩容迁移
key=杨value=a
putVal
18
数据结构底层基于数组,span style=\"font-size: inherit;\
0 条评论
回复 删除
下一页