HashMap原理总结
问题:
1.为什么7头部插入,8改成尾部插入?
7为了提升效率,尾部插入需要遍历链表,同时扩容时链表会反转,存在循环链表问题;
8引入红黑树,必须知道链表长度才能进行转换,会遍历链表,并直接在尾部插入,同时避免7中扩容引起的循环链表问题;
2.默认负载因子为什么是0.75?
提升效率,减少空间浪费的一个折中方案;
3.为什么初始化容量是2的n次方-1?
hash & (table.length - 1) 2n次方-1 保证余下来的都是 1111 ,如果有0,hash后无论0、1与运算都为0,桶一直都不会有值,位与运算计 算出下标,保证分布均匀
位运算:全是1则为1,有0则为0
计算过程:
16 - 1 = 15 -> 1111
1111
1101 0011 1010 1100 1011
------------------------
1011 -> 11
所得结果范围在0-15,最后index为11
4.什么时候扩容?
扩容条件:size >= threshold && null != table[bucketIndex]
1.实际元素个数大于等于预期值
2.目标位置不为null
5.扩容过程?
jdk7: transfer():新建长度2倍的数组,循环旧数组,遍历数组上的链表根据hash结果计算下标放到新数组里,从头拿元素,从头插元素,链表倒序插入;
jdk8: 高低位运算,扩容为原来2倍时,低位不变,高位变化
6.并发问题?
多线程问题:jdk7 扩容时,因为是链表需要移到新的桶上,头变尾,链表发生倒序过程,会产生循环链表,线程一直循环;
jdk8是在尾部插入不会有循环问题,因为顺序和原来的一致,但是多线程会有问题;
7.jdk8对HashMap的改进?
1)数组+链表/红黑树
2)扩容时插入顺序改变
3)函数forEach等
Jdk7
ConcurrentHashMap:
原理:有一个Segment概念,Segment[] 数组组成,包含多个Segment对象(相当于Enatry对象),每个是一个小的HashMap,都实现了RentrantLock,put时会先tryLock(),finally中会释放锁,初始化时根据并发级别初始Segment[]容量大小,取2的指数幂
Jdk8
HashMap:
Put时判断是TreeNode还是链表,链表会遍历长度,并在尾部插入,如果达到8则转换为链表,jdk7中是在头部插入;
伪代码:
if(instanceof TreeNode){
// 在树中插入
} else {
//链表
for(){
// 遍历链表长度,并在尾部插入元素
if(p.next == null){
p.next = newNode;
if(){
//最后如果长度大于8转换成红黑树
treeifyBin();
}
}
}
}
HashMap:
哈希表:基于哈希值的桶和链表;
HashMap创建时不会初始化,在第一次put时初始化
网友评论