彻底搞懂HashMap以及相关面试题
2022-04-01 13:13:32 1 举报
登录查看完整内容
彻底搞懂HashMap以及相关面试题
作者其他创作
大纲/内容
思考：单线程场景下，HashMap的扩容机制如上所示，那多线程场景下仍然使用同样的扩容机制，会不会有什么问题呢？
链表node
二：put方法详解
next
4
张三：123
一：hashMap构造函数
线程1
HashTable
6
查询和put时通过一个key而不是具体的下标，查询效率自然没有下标快
3
2
key是否为null
0
e
5
1
7
ConcurrentHashMap
2：putForNullKey(value)
整个对象加一把锁
concurrentHashMap源码分析
王五：123
oldTable
modCount++
优点：并发安全缺点：插入效率和查询效率变低
一：构造函数
h & length-1
跟迭代器有关
3：int hash=hash(key);
表示对数组的长度-1进行逻辑与操作
1：数组初始化inflateTable(threadhold)threadhold为数组初始化容量16
这么做的目的是什么？让数的二进制高位也参与到运算中去，让hash值更散列一点，减少hash冲突
二：resize(2*table.length)
ConcurrentHashMap的Segment的长度为大于等于并发级别的2的幂次方数，比如并发级别为16，则segment也为16
JDK7 HashMap扩容机制
ConcurrentHashMap的初始化容量指的是HashEntry数组的长度，默认为16
5：遍历Entry数组上面的链表
快速失败机制
思考：能不能不给整个hashmap对象加锁，而是只给每个分段加锁，即分段锁
数据结构：数组+链表
将原来的值返回，并且覆盖现在的值，同一个数组下标内容为新的value
结束：retrun null；
李四：123（尾节点）
newTable
https://www.yuque.com/u736203/phywhw/wxtb11
线程2
三：transfer();将老数组的元素复制到新数组中
头插法伪代码
三：e= e.next
如果没有rehash，老数组元素复制到新数组元素的下标为老数组下标或者是老数组下标+老数组长度，比如老数组长度为3，数组元素下标为2，那么转移到新数组的下标为2或者2+3=5
数组Entry对象的4个属性
循环链表也是hashmap线程不安全的原因
整个对象加一把锁的问题
数组的初始化大小为16，加载因子为0.75f
实现思路：key.hashCode() % table.lengthkey的hashcode对数组长度取余，结果会得到一个数组下标index比如put(\"张三\
JDK7 HashMap源码流程
jdk7 HashMap源码分析
如何解决hash冲突？
线程安全
张三（123）
一：如果整个hashmap存放的元素数量（数组+链表的数量）大于阈值且当前数组元素存在，则扩容
默认并发级别
Segment[]
一：roundUpToPowerOf2(toSize)方法求数组容量大小
并不是真正的跟数组长度进行取余操作
否
算出数组下标
二：newTable[i] = e
对key进行hash运算
直接返回
循环链表
李四：123(尾节点)
2的幂次方数确定方式为将数字转换为二进制后，判断所有bit位是否只有一个是1，其他都为0，那么则是2的幂次方数
初始化容量默认16
阈值：threshold=数组长度table.length*加载因子（默认0.75f）
Segment{HashEntry[] table;}HashEntry{keyvaluehashnext}
一：e.next = newTable[i]
王五：123（头节点）
扩容后的数组大小是原来数组大小的两倍
一：头插
头插法+向下移动
默认加载因子默认0.75f
表示数组容量为一个大于等于初始容量的2的幂次方数，比如toSize为10，那么capacity为16
key相同时的链表循环赋值操作
这里表明，key的hash值不是简单的hashCode运算结果，而是首先通过和hashCode异或运算之后再通过右位移运算的出来的结果
思考：key通过hashCode()运算的结果是随机的，对数组长度取余后的下标可能是相同的，即出现hash冲突，那又如何解决呢如王五计算出来的数组下标也是3，和李四下标冲突了
一：扩容操作
Entry对象
李四（123）
是
数组，存放的是Entry对象
李四：123
object
key和hash都和数组上对象下标的key以及hash都相同
threshold
数组为空数组？
jdk7 ConcurrentHashMap源码分析
这个是什么鬼？
二：向下移动
扩容插入数据（头插法+向下移动）
0 条评论
回复 删除
下一页
