谈谈ConcurrentHashMap与HashMap
HashMap与1.7相比的重大变化:
- 数据结构:取消了segment,直接用table保存数据,锁的粒度更小,减少并发冲突的概率。
- 时间复杂度:Table+链表和红黑树的形式,纯链表的形式时间复杂度O(n),红黑树的形式时间复杂度O(logn),性能提升大。链表转红黑树,必要条件:个数超过了8个。当链表个数小于等于6的时候,从红黑树转化为链表。
- 线程并发安全机制:从1.7的ReentrantLock+segment+HashEntry到CAS+synchronize+HashEntry+红黑树
- 锁的粒度:从1.7的对操作元素的segment加锁到1.8的对每个数组元素(Node中)加锁。
- 元素插入:1.7用的是头插法,而JDK1.8及之后使用的都是尾插法,因为JDK1.7是用单链表进行的纵向延伸,当采用头插法时会容易出现逆序且环形链表死循环问题。但是在1.8之后是因为加入了红黑树使用尾插法,能够避免出现逆序且链表死循环的问题。
HashMap 的工作原理?
- HashMap 底层是 hash 数组和单向链表实现,数组中的每个元素都是链表,由 Node 内部类(实现
Map.Entry接口)实现,HashMap 通过 put & get 方法存储和获取。
存储对象时,将 K/V 键值传给 put() 方法: - ①、调用 hash(K) 方法计算 K 的 hash 值,然后结合数组长度,计算得数组下标;
- ②、调整数组大小(当容器中的元素个数大于
capacity * loadfactor 时,容器会进行扩容resize 为 2n);
③、
i.如果 K 的 hash 值在HashMap 中不存在,则执行插入,若存在,则发生碰撞;
ii.如果 K 的 hash 值在 HashMap 中存在,且它们两者 equals 返回 true,则更新键值对;
iii. 如果 K 的 hash 值在 HashMap 中存在,且它们两者 equals 返回 false,则插入链表的尾部(尾插法)或者红黑树中(树的添加方式)。
(JDK 1.7 之前使用头插法、JDK 1.8 使用尾插法)
获取对象时,将 K 传给 get() 方法:①、调用 hash(K) 方法(计算 K 的 hash 值)从而获取该键值所在链表的数组下标;②、顺序遍历链表,equals()方法查找相同 Node 链表中 K 值对应的 V 值。
ConcurrentHashMap的弱一致性:
可能你期望往ConcurrentHashMap底层数据结构中加入一个元素后,立马能对get可见,但ConcurrentHashMap并不能如你所愿。换句话说,put操作将一个元素加入到底层数据结构后,get可能在某段时间内还看不到这个元素,若不考虑内存模型,单从代码逻辑上来看,却是应该可以看得到的。
ConcurrentHashMap的弱一致性主要是为了提升效率,是一致性与效率之间的一种权衡。要成为强一致性,就得到处使用锁,甚至是全局锁,这就与Hashtable和同步的HashMap一样了。
何为加载因子?
加载因子是表示Hsah表中元素的填满的程度.若:加载因子越大,填满的元素越多,好处是,空间利用率高了,但:冲突的机会加大了.
反之,加载因子越小,填满的元素越少,好处是:冲突的机会减小了,但:空间浪费多了.
冲突的机会越大,则查找的成本越高.反之,查找的成本越小.因而,查找时间就越小.
因此,必须在 "冲突的机会"与"空间利用率"之间寻找一种平衡与折衷. 这种平衡与折衷本质上是数据结构中有名的"时-空"矛盾的平衡与折衷.
HashMap中的加载因子
HashMap默认的加载因子是0.75,最大容量是16,因此可以得出HashMap的默认容量是:0.75*16=12。
用户可以自定义最大容量和加载因子。
HashMap 包含如下几个构造器:
- HashMap():构建一个初始容量为 16,负载因子为 0.75 的 HashMap。
- HashMap(int initialCapacity):构建一个初始容量为 initialCapacity,负载因子为 0.75 的
HashMap。 - HashMap(int initialCapacity, float loadFactor):以指定初始容量、指定的负载因子创建一个
HashMap。
ConcurrentHashMap与HashMap的区别
除了线程安全以外,还有允许键值为空,但是ConcurrentHashMap不允许
为什么 ConcurrentHashMap 比 HashTable 效率要高?
HashTable 使用一把锁(锁住整个链表结构)处理并发问题,多个线程竞争一把锁,容易阻塞;
ConcurrentHashMap
- JDK 1.7 中使用分段锁(ReentrantLock + Segment + HashEntry),相当于把一个 HashMap
分成多个段,每段分配一把锁,这样支持多线程访问。锁粒度:基于 Segment,包含多个 HashEntry。 - JDK 1.8 中使用 CAS + synchronized + Node + 红黑树。锁粒度:Node数组(首结 点)(实现Map.Entry)。锁粒度降低了。
红黑树的特点:
- 每个节点非红即黑
- 根节点总是黑色的
- 如果节点是红色的,则它的子节点必须是黑色的(反之不一定)
- 每个叶子节点都是黑色的空节点(NIL节点)
- 从根节点到叶节点或空子节点的每条路径,必须包含相同数目的黑色节点(即相同的黑色高度)
ConcurrentHashMap 在 JDK 1.8 中,为什么要使用内置锁 synchronized 来代替重入锁 ReentrantLock?
- ①、粒度降低了;
- ②、JVM 开发团队没有放弃 synchronized,而且基于 JVM 的 synchronized 优化空间更大,更加自然。
- ③、在大量的数据操作下,对于 JVM 的内存压力,基于 API 的 ReentrantLock 会开销更多的内存。
针对 ConcurrentHashMap 锁机制具体分析(JDK 1.7 VS JDK 1.8)
JDK 1.7 中,采用分段锁的机制,实现并发的更新操作,底层采用数组+链表的存储结构,包括两个核心静态内部类 Segment 和 HashEntry。
- ①、Segment 继承 ReentrantLock(重入锁) 用来充当锁的角色,每个 Segment 对象守护每个散列映射表的若干个桶;
- ②、HashEntry 用来封装映射表的键-值对;
- ③、每个桶是由若干个 HashEntry 对象链接起来的链表
JDK 1.8 中,采用Node + CAS + Synchronized来保证并发安全。取消类 Segment,直接用 table 数组存储键值对;当 HashEntry 对象组成的链表长度超过 TREEIFY_THRESHOLD 时,链表转换为红黑树,提升性能。底层变更为数组 + 链表 + 红黑树。
欢迎大家关注我的公众号一起交流