文章目录
前言
上一篇简单絮叨了一下CAS和final关键字，这篇博客开始絮叨一下Java并发容器。HashMap，ArrayList这种都是非线程安全的。在Java中我们如果想将HashMap和ArrayList直接变成线程安全的，则可以通过如下方法来实现
Collections.synchronizedList(new ArrayList<E>());
Collections.synchronizedMap(new HashMap<K,V>());
但是这种代码底层其实用的是synchronized同步代码块，效率会大打折扣。在比较老的Java版本中，有Hashtable和Vector两个容器是线程安全的，如果从源码中查看，这两个集合中的关键方法都是synchronized修饰的，并发性能也不是很高。因此才有了专门的并发容器，这篇博客开始总结一下Java中的并发容器。
Map接口
Map是key,value数据结构的顶层接口，我们常用的HashMap是Map接口的一个实现类。除了HashMap这个实现类，还有其他几个具体的实现类，每个都有不同的作用
| 实现类 | 作用 |
|---|---|
| HashMap | 非线程安全的K-V容器，允许key和value为null |
| Hashtable | Java老版本中的K-V集合，线程安全的，但是是基于synchronized实现的 |
| LinkedHashMap | 从名字可得知，在HashMap的基础上，采用链表记录了K-V插入的顺序 |
| TreeMap | 实现了Sort接口，可以根据key进行排序 |
HashMap的问题
HashMap除了不是线程安全的，同时在多线程扩容的时候，还会出现死循环，这个内容有些恶心的面试官会问这种无聊且没有实际作用的问题。这里还是记录一下吧，不展开总结了，直接给出这个问题总结的比较好的文章——JAVA HASHMAP的死循环。
这种问题的根本在于将本身不支持并发的HashMap，强行用于并发的场景，而导致了出现链表循环指向的问题。如果面试遇到这种问题，可以内心鄙视一下面试官，因为这个问题真的有点无聊，就好比本来可以用圆的轮胎来造自行车，而某些人偏要用正方形的轮胎，完了还要问你为啥方形的轮胎造出来的自行车不实用。
总之一点——HashMap不能强行用于并发的场合。同时HashMap和ConcurrentHashMap在1.7和1.8的JDK版本中有较大的差异，这篇博客都会简单总结一下
1.7版本中的HashMap和ConcurrentHashMap
1.7中的HashMap
这个是比较简单的，标示Key的，就是一个数组，然后数组中的每个元素都是一个单向链表，如果存在hash冲突的时候，就会采用拉链法来存储冲突元素。
1.7中的ConcurrentHashMap
1.7中的ConcurrentHashMap和HashMap差不多，但是ConcurrentHashMap是支持并发操作的。因此会稍微复杂点。由于ConcurrentHashMap支持分段锁，因此引入了一个槽（Segment）的数组。1.7中一个ConcurrentHashMap就是一个Segment的数组，Segment继承了ReentrantLock，因此线程每次在针对1.7中的ConcurrentHashMap进行并发操作的时候，只是锁住单个的Segment元素，只需要保证每个的Segment是线程安全的，就保证了整体的ConcurrentHashMap是线程安全的。
1.7中的ConcurrentHashMap默认包含16个Segment，由于1.7中是通过数组来存储Segment的，因此可以在初始化的时候指定Segment的个数，但是指定之后，就不能扩容。具体到每个Segment的内部，其实他内部就是一个HashMap的数据结构，但是是保证了线程安全的。
1.8版本中的HashMap和ConcurrentHashMap
1.8中的HashMap结构
1.8中的HashMap进行了一些整改，最大的不同就是在解决hash冲突的链表过长时，用到了红黑树。1.7中根据hash值定位到下标之后，还要进行走链的查找才能找到目标元素，这个查找的复杂度是O(n)。为了降低这个复杂度，在Java8中如果hash冲突的元素达到8个，会将这个链表转换成红黑树，这样查找的时间复杂度就变成了O(logN)
关于红黑树——红黑树详解。（个人认为，红黑树算法可移植性不强，只需简单了解即可）
1.8中的ConcurrentHashMap
1.8中对1.7的ConcurrentHashMap做了大的改动，ConcurrentHashMap的结构如下
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-adjPh7g2-1637484353960)(F:\blog_doc\blogPic\sync&JUC-learn\4.png)]
和1.8中的HashMap似乎没有区别，不过要保证线程安全，因此在源码上要复杂很多。
相关源码
putVal
final V putVal(K key, V value, boolean onlyIfAbsent) {
//这里不再支持key和value都为null的情况
if (key == null || value == null) throw new NullPointerException();
//计算hash值
int hash = spread(key.hashCode());
int binCount = 0;
//遍历每一个槽位
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
//槽位为空初始化槽位
if (tab == null || (n = tab.length) == 0)
tab = initTable();
//找到对应的hash的槽位为空，则直接放入数据，CAS的方式放入
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}
//如果槽位真正移动或者扩容
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);//则帮助扩容
else {//如果槽位不为空，且ConcurrentHashMap没有在扩容
V oldVal = null;
synchronized (f) {//获取数组该位置的头结点的监视器锁
if (tabAt(tab, i) == f) {//就是再次判断一下
if (fh >= 0) {//头结点的 hash 值大于 0，说明是链表
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
K ek;
// 如果发现了"相等"的 key，判断是否要进行值覆盖，然后也就可以 break 了
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
Node<K,V> pred = e;
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key,
value, null);
break;
}
}
}
else if (f instanceof TreeBin) {//如果是红黑树
Node<K,V> p;
binCount = 2;
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
}
}
if (binCount != 0) {
//判断是否需要转换成红黑树，这里的TREEIFY_THRESHOLD=8,就是转换成红黑树的阈值，超过8个就要转换成红黑树
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount);
return null;
}
get
public V get(Object key) {
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
//计算hash值
int h = spread(key.hashCode());
//槽位数组必须不能为空，且必须大于0
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) != null) {
if ((eh = e.hash) == h) {//如果是第一个节点，则直接返回第一个节点的数据
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}
else if (eh < 0)//如果hash值是一个负数，则说明是一个红黑树，需要根据从红黑树中去查找节点。
return (p = e.find(h, key)) != null ? p.val : null;
while ((e = e.next) != null) {//如果是链表，则走链查找
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
}
return null;
}
1.7和1.8中的对比
针对1.7和1.8中的HashMap和ConcurrentHashMap只是做了一个简单的对比，没有做更进一步的介绍，至于扩容，迁移数据，这些参考文末最后的总结文档吧（个人觉得实在没必要了解到那个层级）。
在数据结构方面，1.8中针对hash冲突的数据，在达到一定阈值之后，引入了红黑树的结构进行存储，在ConcurrentHashMap中节点数组其实是可以扩容的
在保证并发方面，1.7采用的是分段锁，其中的Segment继承至ReentrantLock，而在1.8中保证线程安全的操作是通过CAS+synchronized来实现的。
在查询的时间复杂度，1.7中为O(n)，1.8中为O(logN)
为什么1.8中要针对超过8个的冲突链表转换成红黑树呢？难道转换操作不更耗费性能么？这个在源码的注解中也有提及
HashMap中，节点冲突元素的个数，超过8个的概率是很低很低的。换句话说，1.8中发生将链表转换成红黑树的操作概率是极低的，这种对效率并不会造成什么影响，同时还能提高后续的查找效率，何乐而不为呢。
一个简单实例
/**
* autor:liman
* createtime:2021/11/21
* comment:简单的ConcurrentHashMap使用实例
*/
@Slf4j
public class ConcurrentHashMapOptionsNotSafeDemo implements Runnable{
private static ConcurrentHashMap<String ,Integer> scores = new ConcurrentHashMap<>();
public static void main(String[] args) throws InterruptedException {
scores.put("codeman",100);
Thread threadOne = new Thread(new ConcurrentHashMapOptionsNotSafeDemo());
Thread threadTwo = new Thread(new ConcurrentHashMapOptionsNotSafeDemo());
threadOne.start();
threadTwo.start();
threadOne.join();
threadTwo.join();
System.out.println(scores.get("codeman"));
}
@Override
public void run() {
for(int i=0;i<1000;i++){
Integer score = scores.get("codeman");
int newScore = score+1;
scores.put("codeman",newScore);
}
}
}
上述代码在多线程环境下运行，依旧不是线程安全的，因为其线程中虽然用到了ConcurrentHashMap，但是其修改值的操作并不是一个原子的操作，因此依旧不是线程安全的，这种错误在实际开发中是很常见的。正常的操作应该改成如下代码
@Override
public void run() {
for(int i=0;i<1000;i++){
while(true) {
Integer score = scores.get("codeman");
int newScore = score + 1;
//replace成功会返回true,可以根据这个返回值决定是否退出修改的操作。
boolean putsuccess = scores.replace("codeman", score, newScore);
if(putsuccess){//修改成功才退出
break;
}
}
}
}
总结
推荐一下大牛对HashMap和ConcurrentHashMap的总结，本篇大部分内容都参考了这篇博客，甚至有些图片，就来自于这篇文章，个人觉得网上没有比这篇博客写的更好的总结了——Java7/8 中的 HashMap 和 ConcurrentHashMap 全解析。