多线程高并发学习之并发容器

HashMap相关的同步容器

前世今生介绍：HashMap是从HashTable演变过来的，HashTable设计之初的意愿是容器的的所有方法必须都得是同步的，所以HashTable的所有方法都是加了synchronized关键字来保证同步，这显然是不太合理的，因为大多数情况下，都是只有一个线程来操作容器，所以又在HashTable之后推出了HashMap
- HashTable——>全锁操作
- HashMap——>无锁操作
- ConcurrentHashMap——>新的同步容器（CAS）
- HashMap也应该有同步方法，所以又出了一个Collections这么一个工具类，他可以把HashMap变成一个同步容器，如下图，还可以将许多容器都变为同步容器
- Collections.synchronizedMap( )给出的同步容器HashMap和HashTable有什么区别呢，区别其实很小，就是HashTable用的是方法锁，而Collections.synchronizedMap( )用的是同步代码块，都是用的synchronized，只不过相比于HashTable锁的力度要小一些，效率略高一丢丢，ConcurrentHashMap采用的是CAS无锁操作，在put的过程中如果没有发生冲突，则采用CAS操作进行无锁化更新，只有发生了哈希冲突的时候才锁住在链表上添加新Node或者更新Node的操作
读写效率：
- HashTable写入效率高，实测100W数据写入用时700毫秒左右，读效率低，100W数据读取用时37秒左右
- Collections.synchronizedMap( )写入效率高，实测100W数据写入用时600毫秒左右，读效率低，100W数据读取用时38秒左右
- ConcurrentHashMap写入效率低，实测100W数据写入用时1.8秒左右，读效率超高，100W数据读取用时1.7秒左右
- 总结：实际用哪一个需要看项目的使用场景，到底是读操作多，还是写操作多，然后根据实际压测数据来决定到底是用哪个同步容器

List、Vector、Queue

List同步需要加锁，或者上图所示，使用collectios的synchronizedXXX的方法，获取同步的List，原理也是synchronized代码块
Vector是同步容器，是在方法上加了synchronized关键字，为方法锁，相比synchronizedList锁的力度要大一些，所以效率偏慢一丢丢
Queue队列，实现类中有多个同步队列，都可以实现同步，甚至还有的实现了生产者消费者模型，所以大并发下单个元素的操作，尽量可以多考虑Queue，少考虑List

经常在多线程下使用的容器

Map

ConcurrentHashMap，基于CAS实现，不多解释
ConcurrentSkipListMap，基于跳表实现
- 可能是因为，考虑到利用CAS实现了一个ConcurrentHashMap，也应该需要用CAS实现一个 ”ConcurrentTreeMap“ （此处多逼逼一句，TreeMap基于红黑树实现），但不幸的是，使用CAS实现 ”ConcurrentTreeMap“ 太难了，难度超高，超复杂，所以退一步，使用跳表实现了一个ConcurrentSkipListMap
HashTable
Collections.synchronizedMap( )

List

CopyOnWriteArrayList，写时复制，顾名思义，在写入数据的时候，将array数组copy一次，如下图
- 有点类似Lock里的ReadWriteLock，读不加锁，写入加锁
Collections.synchronizedList( )
- 和上边提到的Collections.synchronizedMap( )一个样子，都是同步代码块

Queue

ConcurrentLinkedQueue
- 方法介绍：
  - add：添加元素，加不进去，满了，跑异常
  - offer：添加元素，添加成功返回true，满了添加不进去了，返回false
  - peek：获取元素，但是获取后不删除元素
  - poll：获取元素并且删除元素

BlockingQueue：天生的生产者消费者模型

LinkedBlockingQueue无界队列

介绍：基于链表实现的无界队列，可以一直添加，直到内存溢出
方法介绍：除了上边的add、offer、peek、poll方法外
- put：添加元素，如果添加满了，就阻塞住，等待可以继续添加元素
- take：获取元素，如果没有可以获取的元素，就阻塞住，等待可以继续往外取元素