ConcurrentHashMap等并集合

并发容器概览

• ConcurrentHashMap：线程安全的HashMap
• CopyOnWriteArrayList：线程安全的List
• BlockingQueue：这是一个接口，表示阻塞队列，非常适合用于作为数据共享的通道
• ConcurrentLinkedQueue:高效的非阻塞并发队列，使用链表实现。可以看做一个线程安全的LinkedList
• ConcurrentSkipListMap:是一个Map，使用跳表的数据结构进行快速查找

集合的历史

• Vector和HashTable：同步方法基本上使用synchronized修饰，虽然线程安全，但是在并发性能效率会比较低
• ArrayList和HashMap
  • 虽然这两个类不是线程安全的，但是可以用Collections.synchronizedList(new ArrayList< E>())和Collections.synchronizedMap(new HashMap<K,V>())使之变成线程安全的
• ConcurrentHashMap和CopyOnWriteArrayList
  • 取代同步的HashMap和同步的ArrayList(时代巨轮滚滚向前)
  • 绝大多数并发情况下，ConcurrentHashMap和CopyOnWriteArrayList的性能都更好
  • CopyOnWriteArrayList适合读多写少的场景,如果写的操作比较多,Collections.synchronizedList性能更好

ConcurrentHashMap

Map简介

• HashMap
• Hashtable
• LinkedHashMap
• TreeMap

HashMap线程不安全

• 同时put碰撞导致数据丢失
• 同时put扩容导致数据丢失
• 死循环造成的CPU100%,在多线程扩容的时候会造成链表的死循环,你指向我,我指向你 详细解释

HashMap 1.7

HashMap 1.8

• 红黑树
  • 对二叉查找树的一种平衡策略,O(logN) vs O(N)
  • 每个节点要么是红色,要么是黑色,但是根节点永远是黑色
  • 红色节点不能连续(也即是,红色节点的孩子和父亲都不能是红色)
  • 从任一节点到其子树中每个叶子接地那的路径都包含相同数量的黑色节点
  • 所有叶子节点都是黑色的

JDK1.7的ConcurrentHashMap实现和分析

• Java 7中的ConcurrentHashMap最外层是多个segment，每个segment的底层数据结构与HashMap类似，仍然是数组和链表组成的拉链法
• 每个segment独立上ReentrantLock锁，每个segment之间互不影响，提高了并发效率
• ConcurrentHashMap 默认有 16个 Segments，所以最多可以同时支持16各线程并发写(操作分别分布在不同的Segment 上)。这个默认值可以在初始化的时候设置为其他值，但是一旦初始化以后，是不可以扩容的
  

JDK1.8的ConcurrentHashMap实现和分析

• 为什么超过8要转为红黑树
  • 红黑树的空间占用是链表的两倍,正常情况下链表的冲突是很难达到8的
  • 默认是链表,链表占用的空间更少
  • 当红黑树的节点小于等于6的时候,红黑树会转回为链表
• putVal流程
  • 判断key value不为空
  • 计算hash值
  • 根据对应位置节点的类型，来赋值，或者helpTransfer，或者增长链表，或者给红黑树增加节点
  • 检查满足闯值就“红黑树化
  • 返回oldVal
• get流程
  • 计算hash值
  • 找到对应的位置，根据情况进行
  • 直接取值
  • 红黑树里找值
  • 遍历链表取值
  • 返回找到的结果

CopyOnWriteArrayList

• 代替Vector和SynchronizedList，就和ConcurrentHashMap代替SynchronizedMap的原因一样
• Vector和SynchronizedList的锁的粒度太大，并发效率相对比较低，并且迭代时无法编辑
• Copy-On-Write并发容器还包括CopyOnWriteArraySet，用来替代同步Set

使用场景

• 读操作可以尽可能的快,而写即使慢一些也没有太大关系
• 读多写少:黑名单，每日更新，监听器:迭代操作远多于修改操作

CopyOnWriteArrayList读写规则

• 回顾读写锁: 读读共享、其他都互斥(写写互斥、读写互斥写读互斥)
• 读写锁规则的升级:读取是完全不用加锁的，并且更厉害的是写入也不会阻塞读取操作。只有写入和写入之间需要进行同步等待

CopyOnWriteArrayList的缺点,所有CopyOnWrite类型都是一样的

• 数据一致性问题:CopyOnWrite容器只能保证数据的最终致性，不能保证数据的实时一致性。所以如果你希望写入的数据，马上能读到，请不要使用CopyOnWrite容器
• 内存占用问题:因为CopyOnWrite的写是复制机制，所以在进行写操作的时候，内存里会同时驻扎两个对象的内存

并发队列

为什么要使用队列

• 用队列可以在线程间传递数据:生产者消费者模式、银行转账
• 考虑锁等线程安全问题的重任从“你”转移到了“队列”上

阻塞队列BlockingQueue

• 阻塞队列是具有阻塞功能的队列，所以它首先是一个队列其次是具有阻塞功能
• 通常，阻塞队列的一端是给生产者放数据用，另一端给消费者拿数据用。阻塞队列是线程安全的，所以生产者和消费者都可以是多线程的

什么是阻塞队列

• 阻塞功能:最有特色的两个带有阻塞功能的方法是
• take() 方法: 获取并移除队列的头结点，一旦如果执行take的时候，队列里无数据，则阻塞，直到队列里有数据
• put() 方法: 插入元素。但是如果队列已满，那么就无法继续插入，则阻塞，直到队列里有了空闲空间
• 是否有界(容量有多大): 这是一个非常重要的属性，无界队列意味着里面可以容纳非常多(Integer.MAX VALUE，约为2的31次，是非常大的一个数，可以近似认为是无限容量 )
• 阻塞队列和线程池的关系:阻塞队列是线程池的重要组成部分

方法

• put,take
• add,remove,element
• offer,poll,peek

ArrayBlockingQueue

• 有界
• 指定容量
• 公平:还可以值定是否需要保证公平,如果想保证公平的话,那么等待了最长时间的线程会被优先处理,不过这会同时带来一定性能损耗

LinkedBlockingQueue

• 无界
• 容量Integer.MAX_VALUE
• 内部结构:Node,两把锁。

SynchronousQueue

• 它的容量为0
• 需要注意的是，SynchronousQueue的容量不是1而是0，因为SynchronousQueue不需要去持有元素，它所做的就是直接传递( direct handoff )
• 效率高
  

SynchronousQueue注意点

• SynchronousQueue没有peek等函数，因为peek的含义是取出头结点，但是SynchronousQueue的容量是0，所以连头结点都没有，也就没有peek方法。同理，没有iterate相关方法
• 是一个极好的用来直接传递的并发数据结构
• SynchronousQueue是线程池Executors.newCachedThreadPool()使用的阳塞队列

非阻塞并发队列

• 并发包中的非阻塞队列只有ConcurrentLinkedQueue这一种顾名思义ConcurrentLinkedQueue是使用链表作为其数据结构的，使用CAS非阻塞算法来实现线程安全(不备阻塞功能)，适合用在对性能要求较高的并发场景。用的相对比较少些
• 看源码的offer方法的CAS思想，内有p.casNext方法，用了UNSAFE.compareAndSwapObject