java教程

Java HashMap高并发

位置:首页 > java教程 > java技巧,2018-01-09 01:54
本文主要介绍java7的hashmap底层设计结构,即数组+单向链表,但是java8为了方便get查询效率,在链表基础上新加红黑树结构,(重点研究),java7和8的不同
首先讲一下HashMap的Resize机制:

1.Hashmap在插入元素过多的时候需要进行Resize,Resize的条件是



HashMap.Size   >=  Capacity * LoadFactor。

Resize:HashMap的容量是有限的。当经过多次元素插入,使得HashMap达到一定饱和度时,Key映射位置发生冲突的几率会逐渐提高。这时候,HashMap需要扩展它的长度,也就是进行Resize

影响发生Resize的因素有两个:

   1.Capacity

   HashMap的当前长度。上一期曾经说过,HashMap的长度是2的幂。

   2.LoadFactor

   HashMap负载因子,默认值为0.75f。




2.Hashmap的Resize包含扩容ReHash两个步骤,ReHash在并发的情况下可能会形成链表环。
  当调用Get查找一个不存在的Key,而这个Key的Hash结果的位置恰好是带有环形链表的位置的时候,程序会进入死      循环

1.扩容


创建一个新的Entry空数组,长度是原数组的2倍。

2.ReHash

遍历原Entry数组,把所有的Entry重新Hash到新数组。为什么要重新Hash呢?因为长度扩大以后,Hash的规则也随之改变。

让我们回顾一下Hash公式:

index =  HashCode(Key) &  (Length - 1) 


当原数组长度为8时,Hash运算是和111B做与运算;新数组长度为16,Hash运算是和1111B做与运算。Hash结果显然不同。

扩容前:

Java HashMap(图0)

扩容后:

Java HashMap(图1)


高并发环境下做插入操作有可能出现的环形链表:


Java HashMap(图2)


TAGS:Java HashMap

猜你喜欢


NewHot手机版