HashMap与ConcurrentHashMap解析与比较
2019-04-01 本文已影响82人
乌鲁木齐001号程序员
HashMap HashMap底层数据结构.png
影响HashMap性能的2个因素
- 初始容量,默认为16,表示哈希表中桶的数量;
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
- 加载因子,默认值为0.75,表示哈希表的容量在自动增加之前可以达到多满的尺度,当哈希表中的条目数=哈希表的容量*加载因子,将触发扩容操作resize();
static final float DEFAULT_LOAD_FACTOR = 0.75f;
注:初始容量和加载因子2个值在哈希表初始化的时候可以设定;
HashMap的寻址方式
- 对于新插入的数据和要读取的数据,HashMap会将其key按照一定计算规则计算出哈希值,并对数组长度进行取模,结果作为其插入数组的index;
- 取模的代价远高于位运算的代价,所以HashMap中数组的长度要求必须是2^n, 具体为,将取模操作换成对2^n-1的与运算;
- HashMap初始化的时候传入的容量可以不是2^n, HashMap会根据传入的值得到一个相应的2^n的值;
- HashMap是线程不安全的,主要体现在resize的时候可能出现死循环,以及在使用迭代器的时候会出现ParsedFailed;
- 扩容的具体做法:创建一个新的,长度为原来容量2倍的数组,保证新的容量仍为2^n,并将原来的数组重新插入新数组,这个过程称为再哈希,这个方法不是线程安全的;
单线程下的resize图示
HashMap在单线程下的ReHash.png多线程resize时候出现死循环图示
-
线程1处理5到一半,5和9还没有完全断开,切到线程2,线程2已经把整个ReHash动作做完;
多线程下的ReHash_1.png -
切回线程1,把5挂在索引为1的元素后面;
多线程下的ReHash_2.png -
由于在线程1中,5和9没断开,线程1会把9再放到5前面,这是在新数组中完成的;
多线程下的ReHash_3.png -
处理完9后,线程1看到9后面还有5,这是因为线程2已经完成了ReHash动作,然后又将5排在9前面,9在5前面,5在9前面,这就死循环了;
多线程下的ReHash_4.png
ParsedFailed分析
- 在遍历HashMap的时候,如果HashMap中的元素有变更,ConcurrentModifacationException,这就是所说的ParseFailed;
解决方案
- Collections.synchronizedMap()构造出一个同步的Map;
- 或者直接使用ConcurrentHashMap();
ConcurrentHashMap
ConcurrentHashMap结构.png- 与HashMap不同的是,ConcurrentHashMap外面不是一个大数组,而是多个小数组,每个小数组是一个Segment;
- 在读写某个key时,先计算出该key的哈希值,并将哈希值的高sshift位对Segment个数取模,从而得到该key属于哪个Segment;
- 接着就像操作HashMap一样操作Segment;
- Segment继承自J.U.C的ReentrantLock,所以可以很方便的对每个Segment上锁,就是所谓分段锁;
HashMap与ConcurrentHashMap的区别
- ConcurrentHashMap是线程安全的,HashMap不是线程安全的;
- HashMap允许key和value为空,ConcurrentHashMap不允许;
- HashMap在用iterator遍历的同时,不允许修改HashMap;ConcurrentHashMap允许该行为,并且更新对后续的遍历是可见的;
Java8对ConcurrentMap的改进
- Java7中的ConcurrentHashMap理论上最大并发数和Segment个数相等;
-
Java8废弃的分段锁的方案,直接使用一个大数组,并对哈希碰撞下的寻址做了优化,当链表的长度超过一定值(默认8),列表将转换成红黑树,寻址的时间福在读从O(n)降为O(logn);
Java8中的ConcurrentHashMap的进步.png