java多线程（五）并发容器

Hash

1. hash：散列。把任意长度的输入，变换成固定长度的输出，这个输出值就是散列值，属于压缩映射，容易产生hash冲突。Hash:直接取余
2. hash冲突解决办法：
   a,开放寻址
   b,再散列
   c,链地址法
3. 摘要算法或hash算法：md4,md5,sha

位运算
1）应用：权限

ConcurrentHashMap

1. 实现方式：jdk8之前和jdk8之后不一样
2. jdk8之前，
   1>Segment继承了ReentrantLock类
   2>concurrencyLevel（并发度）默认16，意思是默认情况下16个线程操作concurrentHashMap同步访问不会异常
   3>get方法
   a,定位segment：根据key的hashcode进行再散列值的高位
   b,定位table: key的hashcode进行再散列值取模
   c,一次扫描链表，要么找到元素，要么返回Null
   4>Segment不扩容，只扩容Segment里的table,扩容以2n的方式扩容。扩容时，会移动table的index发生变化的entry
   5>size方法，进行两次不加锁的统计，一致直接返回结果，不一致重新对segment加锁统计。所以尽量少用size方法
   6>ConcurrentHashMap是弱一致性的，因为在使用get()方法时，没有加锁
   7>put方法
   a,像get方法一定定位segment,table。在找到segment的后进行put操作的时候，在put方法中锁定当前的segment
   b,进行put操作，如果存在key的hash值相等，并且key值相等的数据，则返回旧的值，并用新的值替换旧的值
   c,进行put操作，如果不存在b的情况，将值放入对应的位置上，并返回null
   8>初始化
   a,初始设置table的size，默认大小是16
   b,初始的segment的大小也是16，而且不会变化
3. jdk8之后
   1）取消了segment数组，直接使用table保存数据，锁的粒度更小，减少并发冲突的概率
   2）内部结构变成：table数组+链表+红黑树。纯链表的时间复杂度O(n),红黑树的时间复杂度O(log n)。性能提升很大。
   链表转红黑树：必要条件是链表的个数大于等于8个的时候，当元素个数小于6个的时候由红黑树转成链表
   3）数据结构使用Node类存放key和value值
   4）初始化的时候，只是给成员变量赋值，put时进行实际数组的填充
   5）spread方法保证数据在map里分布的更均匀
   6）sizeCtl
   1>负数：表示进行初始化或者扩容，-1表示正在初始化，-N表示有N-1个线程在扩容
   2>正数：0表示还没有被初始化，大于0表示初始化或者是下一次进行扩容的阈值
   7）get方法
   8）put方法
   9）扩容：transfer方法进行实际的扩容，table的大小也是采用翻倍的方式。有一个并发扩容的机制（在put方法中helpTransfer）
   10）size方法,同样是弱一致，估计的大概数量，不是精确的数量

   4. ConcurrentHashMap实现图

      
      ConcurrentHashMap实现图.png

ConcurrentSkipListMap和ConcurrentSkipListSet,使用调表（SkipList）数据结构实现,以空间换时间，概率数据结构

ConcurrentLinkedQueue（LinkList的并发版本）无界非阻塞链表，遵循先进先出原则

1. add和offer将元素插入到尾部
2. peek（拿头部数据不移除）和poll（拿完头部数据后移除数据）

CopyOnWriteArrayList和CopyOnWriteArraySet写时复制容器

1. 只能保证数据最终一致，不能保证实时一致，最适用于读多写少的场景，如白名单，黑名单。
2. 占用内存大，对数据实时要求高的场景也不适合

阻塞队列

1. 当队列满的时候，插入元素的线程被阻塞，直到队列不满，而队列为空的时候，获取元素被阻塞，直到队列不为空
2. 适用于生产者消费者模式，解决生产者和消费者之间能力不匹配的问题
3. 常用方法
   1>插入
   2>移除
   3>检查
4. 常用阻塞队列类
   1>ArrayBlockingQueue：一个由数组组成的有界阻塞队列。按照先进先出原则，要求设定初始大小；只有一个锁，直接插入元素
   2>LinkedBlockingQueue：一个由链表组成的有界阻塞队列。按照先进先出，可以不设定初始大小；两个锁，需要转换
   3>PriorityBlockingQueue：一个支持优先级排序的无界界阻塞队列。默认情况按照自然顺序，可以实现compareTo()方法或者指定Comparator自定顺序
   4>DelayQueue：一个使用优先级队列的无界界阻塞队列。支持延时获取的元素阻塞队列，元素必须实现Delayed接口。可以应用在缓存系统，订单到期，限时支付
   5>SynchronouseQueue：一个不存储元素的阻塞队列。每一个Put操作都要等待一个take操作
   6>LinkedTransferQueue：一个由链表组成的无界阻塞队列。transfer()必须要消费者消费了以后方法才会返回和tryTransfer()无论消费者是否接收方法都立即返回
   7>LinkedBlockingDequeue：一个由链表组成的双向阻塞队列。队列的头和尾都可以插入和移除元素。（Fork-Join的工作密取使用类）