平时大家都会经常使用到 Map, 面试的时候又经常会遇到问 Map 的, 其中主要就是 ConcurrentHashMap, 在说 ConcurrentHashMap. 我们还是先看一下,
其他两个基础的 Map 类: HashMap 和 TreeMap
- HashMap:
- public class HashMap<K,V> extends AbstractMap<K,V>
- implements Map<K,V>, Cloneable,Serializable { // 这里有个很逗的事情 hashMap 继承了 AvstractMap 为什么还要实现 Map? 据说, 作者说的 这只是个错误的写法 Q_Q
- TreeMap:
- public class TreeMap<K,V>
- extends AbstractMap<K,V>
- implements NavigableMap<K,V>, Cloneable, java.io.Serializable
- public interface NavigableMap<K,V> extends SortedMap<K,V>
实现 | 存储 | 遍历 | 性能损耗 | 键值对 | 安全 | 效率 | |
TreeMap | SortMap 接口,基于红黑树 & nbsp; | 默认按键的升序排序 & nbsp; | Iterator 遍历是排序的 | 插入、删除 | 键、值都不能为 null | 适用于在 Map 中插入、删除和定位元素 | |
HashMap | 基于哈希散列表实现 | 随机存储 | Iterator 遍历是随机的 & nbsp; | 基本无 | 只允许键、值均为 null | 适用于按自然顺序或自定义顺序遍历键 (key) |
HashMap 通常比 TreeMap 快一点 (树和哈希表的数据结构使然), 建议多使用 HashMap, 在需要排序的 Map 时候才用 TreeMap.
那么现在就聊一下 HashMap 和 ConcurrentHashMap
我们都知道 ConcurrentHashMap 是线程安全的. 那为什么 HashMap 就线程不安全了呢?
这里有很不错的解释 https://my.oschina.NET/hosee/blog/673521
还有一个路径太长了. 给个短的 还可以的
总结起来就是:
1. resize 死循环
我们都知道 HashMap 初始容量大小为 16, 一般来说, 当有数据要插入时, 都会检查容量有没有超过设定的 thredhold, 如果超过, 需要增大 Hash 表的尺寸, 但是这样一来, 整个 Hash 表里的元素都需要被重算一遍. 这叫 rehash, 这个成本相当的大.
在 rehash 的时候, 在多线程的时候容易造成环形链表
2.fail-fast
如果在使用迭代器的过程中有其他线程修改了 map, 那么将抛出 ConcurrentModificationException, 这就是所谓 fail-fast 策略.
这个异常意在提醒开发者及早意识到线程安全问题, 具体原因请查看 ConcurrentModificationException 的原因以及解决措施 http://my.oschina.NET/hosee/blog/612718 看了这个 我觉得需要去修改一下我原来说的 CopyAndWriteArrayList 了
ConcurrentHashMap 来了. 面试以前遇到了很多次
(1) 结构 [Java7 与 Java8 不同]
JDK7
1.ConcurrentHashMap 中的分段锁称为 Segment, 它即类似于 HashMap(JDK7 与 JDK8 中 HashMap 的实现 http://my.oschina.NET/hosee/blog/618953 ) 的结构, 即内部拥有一个 Entry 数组, 数组中的每个元素又是一个链表; 同时又是一个 ReentrantLock(Segment 继承了 ReentrantLock)
2 . 当我们读取某个 Key 的时候它先取出 key 的 Hash 值, 并将 Hash 值得高 sshift 位与 Segment 的个数取模, 决定 key 属于哪个 Segment. 接着像 HashMap 一样操作 Segment. 为了保证不同的 Hash 值保存到不同的 Segment 中, ConcurrentHashMap 对 Hash 值也做了专门的优化.
3. 如果并发度设置的过小, 会带来严重的锁竞争问题; 如果并发度设置的过大, 原本位于同一个 Segment 内的访问会扩散到不同的 Segment 中, CPU cache 命中率会下降, 从而引起程序性能下降.(文档的说法是根据你并发的线程数量决定, 太多会导性能降低)
2. JDK8 中的实现
ConcurrentHashMap 在 JDK8 中进行了巨大改动, 很需要通过源码来再次学习下 Doug Lea 的实现方法.
它摒弃了 Segment(锁段) 的概念, 而是启用了一种全新的方式实现, 利用 CAS 算法. 它沿用了与它同时期的 HashMap 版本的思想, 底层依然由 "数组"+ 链表 + 红黑树的方式思想 (JDK7 与 JDK8 中 HashMap 的实现 http://my.oschina.NET/hosee/blog/618953 ), 但是为了做到并发, 又增加了很多辅助的类, 例如 TreeBin,Traverser 等对象内部类.
总结
JDK6,7 中的 ConcurrentHashmap 主要使用 Segment 来实现减小锁粒度, 把 HashMap 分割成若干个 Segment, 在 put 的时候需要锁住 Segment,get 时候不加锁, 使用 volatile 来保证可见性, 当要统计全局时 (比如 size), 首先会尝试多次计算 modcount 来确定, 这几次尝试中, 是否有其他线程进行了修改操作, 如果没有, 则直接返回 size. 如果有, 则需要依次锁住所有的 Segment 来计算.
jdk7 中 ConcurrentHashmap 中, 当长度过长碰撞会很频繁, 链表的增改删查操作都会消耗很长的时间, 影响性能, 所以 jdk8 中完全重写了 concurrentHashmap, 代码量从原来的 1000 多行变成了 6000 多 行, 实现上也和原来的分段式存储有很大的区别.
主要设计上的变化有以下几点:
不采用 segment 而采用 node, 锁住 node 来实现减小锁粒度.
设计了 MOVED 状态 当 resize 的中过程中 线程 2 还在 put 数据, 线程 2 会帮助 resize.
使用 3 个 CAS 操作来确保 node 的一些操作的原子性, 这种方式代替了锁.
sizeCtl 的不同值来代表不同含义, 起到了控制的作用.
至于为什么 JDK8 中使用 synchronized 而不是 ReentrantLock, 我猜是因为 JDK8 中对 synchronized 有了足够的优化吧.
总结:
HashMap 非线程安全, ConcurrentHashMap 线程安全 (可以看下这个, 很有 ConcurrentHashMap 能完全替代 HashTable 吗? http://my.oschina.NET/hosee/blog/675423 )
HashMap 允许 Key 与 Value 为空, ConcurrentHashMap 不允许
HashMap 不允许通过迭代器遍历的同时修改, ConcurrentHashMap 允许. 并且更新可见
来源: https://www.cnblogs.com/aihuxi/p/9688711.html