Java下的并发容器

预备知识-HASH

就是把任意长度的输入（又叫做预映射， pre-image），通过散列算法，变换成固定长度的输出，该输出就是散列值。这种转换是一种压缩映射，也就是，散列值的空间通常远小于输入的空间，不同的输入可能会散列成相同的输出，所以不可能从散列值来确定唯一的输入值。简单的说就是一种将任意长度的消息压缩到某一固定长度的消息摘要的函数。常用HASH函数：直接取余法、乘法取整法、平方取中法

处理冲突方法

• 开放寻址法
• 再散列法
• 链地址法(拉链法，常用)

常用hash算法的介绍：（1) MD4（2) MD5它对输入仍以512位分组，其输出是4个32位字的级联（3) SHA-1

预备知识-位运算

• 有符号右移>>(若正数,高位补0,负数,高位补1)
• 有符号左移<<
• 无符号右移>>>(不论正负,高位均补0)
• 取模a % (2^n) 等价于 a & (2^n - 1)，所以在map里的数组个数一定是2的乘方数，计算key值在哪个元素中的时候，就用位运算来快速定位
• a * 2 等价于 a<<1
• a / 2 等价于 a>>1

常用集合容器

• Hashtable：使用synchronized实现同步，是锁了整个容器，已经淘汰
• ArrayList linkedlist HashSet HashMap：未考虑多线程安全（未实现同步）
• Collections.synchronizedXXX：同步工具类，可以把非同步容器转为同步容器，仍然使用synchronized关键字实现同步，锁整个容器
• ConcurrentHashMap：用CAS+sync+分段锁实现了锁，在多线程读取的时候效率非常高
• TreeMap(TreeSet)：红黑树排序Map，线程不安全
• LinkedHashMap：用一个列表维护插入Map的节点时的插入顺序，天生实现了LRU算法
• ConcurrentSkipListMap：高并发并且排序，跳表实现CAS操作比Tree简单，所以没有ConcurrentTreeMap
• CopyOnWriteArrayList（CopyOnWriteArraySet）：读的时候不加锁，写的时候加锁，并且把原数组复制一份，长度+1，把新元素加入，在把引用指向新数组，读特别多，写特别少用CopyOnWriteArrayList

JDK1.7中并发条件下HashMap的死锁问题

在多线程环境下，使用HashMap进行put操作会引发多线程扩容，由于JDK1.7中HashMap的链表采用头插法，多线程扩容后会形成环形数据结构，一旦形成环形数据结构，Entry的next节点永远不为空，就会产生死循环获取Entry，导致在get遍历查找元素的时候进入死循环，使得CPU利用率接近100%

HashMap之所以在并发下的扩容造成死循环，是因为，多个线程并发进行时，因为一个线程先期完成了扩容，将原Map的链表重新散列到自己的表中，并且链表变成了倒序，后一个线程再扩容时，又进行自己的散列，再次将倒序链表变为正序链表。于是形成了一个环形链表，当get表中不存在的元素时，造成死循环

ConcurrentHashMap

JDK1.7下的实现

• JDK1.7下采用了分段锁的概念，分段（Segment）的个数在初始化时就已经指定，后续不可扩展，这里的锁是CAS可重入锁
• 每个Segment下挂载一个table，用来存储HashEntry，冲突采用链表方式解决
• 每个table容量超过扩容因子，则会扩容，申请新空间，重新计算Hash位置，并移动元素

JDK1.8下的实现

• JDK1.8下面取消了1.7的Segment结构，直接使用数组
• 锁的粒度更细，是table里面的每个头节点
• Hash冲突的解决引入了红黑树，并且设置了阀值，链表长度超过8，链表转红黑树，长度低于6，红黑树转链表
• 锁采用了CAS分段锁+synchronized关键字（JDK1.8对sync做了很多优化）
• 扩容时采用了多工作线程协作模式，每个线程负责固定步长原子的迁移

并发下的Map常见面试题汇总

HashMap 和 HashTable 有什么区别？

①、HashMap 是线程不安全的，HashTable 是线程安全的

②、由于线程安全，所以 HashTable 的效率比不上 HashMap

③、HashMap最多只允许一条记录的键为null，允许多条记录的值为null，而 HashTable 不允许

④、HashMap 默认初始化数组的大小为16，HashTable 为 11，前者扩容时，扩大两倍，后者扩大两倍+1

⑤、HashMap 需要重新计算 hash 值，而 HashTable 直接使用对象的 hashCode

Java 中的另一个线程安全的与 HashMap 极其类似的类是什么？同样是线程安全，它与 HashTable 在线程同步上有什么不同？

ConcurrentHashMap 类（是 Java并发包 java.util.concurrent 中提供的一个线程安全且高效的 HashMap 实现）。

HashTable 是使用 synchronize 关键字加锁的原理（就是对对象加锁）；

而针对 ConcurrentHashMap，在 JDK 1.7 中采用分段锁的方式；JDK 1.8 中直接采用了CAS（无锁算法）+ synchronized，也采用分段锁的方式并大大缩小了锁的粒度。

HashMap & ConcurrentHashMap 的区别？

除了加锁，原理上无太大区别

另外，HashMap 的键值对允许有null（key为null放在table的0号位置），但是ConCurrentHashMap 都不允许

在数据结构上，红黑树相关的节点类

为什么 ConcurrentHashMap  比 HashTable 效率要高？

HashTable 使用一把锁（锁住整个链表结构）处理并发问题，多个线程竞争一把锁，容易阻塞

ConcurrentHashMap  

JDK 1.7 中使用分段锁（ReentrantLock + Segment + HashEntry），相当于把一个 HashMap 分成多个段，每段分配一把锁，这样支持多线程访问。锁粒度：基于 Segment，包含多个 HashEntry。

JDK 1.8 中使用 CAS + synchronized + Node + 红黑树。锁粒度：Node（首结点）（实现 Map.Entry<K,V>）。锁粒度降低了。

针对 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 时，链表转换为红黑树，提升性能。底层变更为数组 + 链表 + 红黑树

ConcurrentHashMap 在 JDK 1.8 中，为什么要使用内置锁 synchronized 来代替重入锁 ReentrantLock？

• JVM 开发团队在1.8中对 synchronized做了大量性能上的优化，而且基于 JVM 的 synchronized 优化空间更大，更加自然。
• 在大量的数据操作下，对于 JVM 的内存压力，基于 API  的 ReentrantLock 会开销更多的内存。

ConcurrentHashMap 简单介绍？

①、重要的常量：

private transient volatile int sizeCtl;

当为负数时，-1 表示正在初始化，-N 表示 N - 1 个线程正在进行扩容

当为 0 时，表示 table 还没有初始化

当为其他正数时，表示初始化或者下一次进行扩容的大小

②、数据结构：

Node 是存储结构的基本单元，继承 HashMap 中的 Entry，用于存储数据

TreeNode 继承 Node，但是数据结构换成了二叉树结构，是红黑树的存储结构，用于红黑树中存储数据

TreeBin 是封装 TreeNode 的容器，提供转换红黑树的一些条件和锁的控制

③、存储对象时（put() 方法）：

1. 如果没有初始化，就调用 initTable() 方法来进行初始化
2. 如果没有 hash 冲突就直接 CAS 无锁插入
3. 如果需要扩容，就先进行扩容
4. 如果存在 hash 冲突，就加锁来保证线程安全，两种情况：一种是链表形式就直接遍历到尾端插入，一种是红黑树就按照红黑树结构插入
5. 如果该链表的数量大于阀值 8，就要先转换成红黑树的结构，break 再一次进入循环
6. 如果添加成功就调用 addCount() 方法统计 size，并且检查是否需要扩容

④、扩容方法 transfer()：默认容量为 16，扩容时，容量变为原来的两倍

helpTransfer()：调用多个工作线程一起帮助进行扩容，这样的效率就会更高

⑤、获取对象时（get()方法）：

1. 计算 hash 值，定位到该 table 索引位置，如果是首结点符合就返回；
2. 如果遇到扩容时，会调用标记正在扩容结点 ForwardingNode.find()方法，查找该结点，匹配就返回；
3. 以上都不符合的话，就往下遍历结点，匹配就返回，否则最后就返回 null

ConcurrentHashMap 的并发度是什么？

1.7中程序运行时能够同时更新 ConccurentHashMap 且不产生锁竞争的最大线程数。默认为 16，且可以在构造函数中设置。当用户设置并发度时，ConcurrentHashMap 会使用大于等于该值的最小2幂指数作为实际并发度（假如用户设置并发度为17，实际并发度则为32）

1.8中并发度则无太大的实际意义了，主要用处就是当设置的初始容量小于并发度，将初始容量提升至并发度大小