Map

ConcurrentHashMap

  1. 哈希表实现的容器
  2. 底层使用了分段锁
  3. 是现在多线程中使用比较多的一个容器

ConcurrentSkipListMap

  1. 通过跳表实现高并发：跳表—->跳跃式的寻找，要通过上一层的节点找到下一层的节点（跳下来），要找到下面的节点才能找到更详细的节点，所以要一层一层下来（上下层要有关联，上一层知道怎么跳到下一层去）
  2. 这个map中有排序
  3. 另一个有序的Map是TreeMap，但是没有相对应的Concurrent结构，主要是因为在树结构上用CAS操作太复杂了
  4. 所以构造了一个跳表结构来实现有序的并发Map（代替Tree的操作）
  5. 跳表的结构：在链表结构的基础上，拿出一些关键元素（一些常用的分界）在上面做一层，还可以再往上做！
  6. 每层链表的数据越来越少，并且分层，查找时从顶层向下查找，一层一层的缩小范围，有些像树结构（多分法结构）
  7. 跳表比单纯的链表在效率上高出很多，同时CAS操作在跳表数据结构上的实现难度比在Tree上容易很多（数据结构课）
  8. 单纯用链表效率太低

image.png

  1. ConcurrentSkipListMap与ConcurrentHashMap的区别：
    1. 一个是有序的，一个是无序的
    2. 并且两个都支持并发操作


HashMap和TreeMap

  1. LinkedHashMap只是在HashMap的基础上加了一个链/链表，可以提升遍历的效率；原来HashMap遍历的时候效率是比较低的，而加了链之后就可以提高迭代的效率
  2. LinkedHashMap除了具有HashMap特性外，对他进行迭代的时候效率会变高，仍然没有进行排序
  3. TreeMap用的是红黑树（连老师、公开课），本身是排好序的，自身有一些自平衡的操作，查找的时候效率比较高
  4. 只有ConcurrentHashMap，没有ConcurrentTreeMap，相当于缺了一个
  5. 为什么没有？
    1. ConcurrentHashMap中用的是CAS操作
    2. CAS操作用在树这种数据结构的时候，实现起来太复杂了，非常复杂
  6. 这时假如要用拍好序的ConcurrentHashMap，可以用跳表结构ConcurrentSkipListMap—->跳表的数据结构

CopyOnWriteList写时复制？

  1. 可以用ArrayList（会触发并发问题，因为多线程访问并且他没有锁）
  2. 可以用Vector
  3. CopyOnWriteArrayList写的时候进行复制：当我们要写入东西（往里面加元素）的时候，将里面的东西（元素）复制出来，再复制一份数组
  4. 适用于写情况少，而读情况多的情况，这样可以用CopyOnWriteList来提高效率
  5. 为什么效率变高？
    1. 因为写的时候不加锁，Vector写的时候都加锁
    2. 之前要停掉读线程才能向里面添加数据、写数据
    3. 但CopyOnWriteList写的时候会在原来的List上copy一个，copy的时候扩展出一个新元素来，然后将新添加的元素扔到最后的位置上，最后将老的引用指向新的List（将原来的引用指向新的数组）
  6. 原来读的还是老的，往外读的时候还是在老的List上面；换成新的之后对读线程严格来说是没有什么影响的，除非每次都要计算size，每次读的时候都要用到最新的size—->这时候还是要用锁的方式来实现
  7. 这个写的时候效率比较低，而读的时候效率高，因为每次写的时候都要复制
  8. 源码实现：add往里加的方法中用了synchronized加了锁，写的时候会加一把锁？？？？why？？？？
  9. 因为是数组，所以add写的时候要复制一份扩容？
  10. 写的时候加锁，读的时候不要加锁
  11. 读的时候不要加锁的原因：
    1. 因为写的时候通过getArray获取到其中的数组引用之后开辟了一个新的内存区域进行了复制，真正的操作是在这个新的内存区域做的，不会影响到读的时候通过getArray获取到其中的数组引用，所以根本不需要加锁
  12. 之前的Vector不管是写还是读，都是要加锁的；而CopyOnWriteList只要在写的时候加锁，在读的时候不需要加锁
  13. 用于读特别多，写比较少的情况下
  14. 本质上就是ReadWriteLock的概念，读的时候是共享锁，写的时候是独占锁（排他锁）
  15. CopyOnWriteList没有fail-fast的—->快速失败
  16. CopyOnWriteList读的时候不用加锁—->因为写的时候进行了复制，是在复制出来的数组上操作的；写的时候复制了，复制出的新的内容和老的内容完全是一致的，根本不需要加锁
  17. CopyOnWriteList只需要在写的时候加锁—->主要用在读特别多，写特别少的情况下
  18. CopyOnWriteList（读不加锁，写不加锁）对比Vector和synchronizedList（不管读写都要加锁）
  19. 都不需要加锁，因为读的时候是获取其中的数组，对数组进行读取的
  20. 而写的时候，依然可以去取其中的数组，但是不能多个线程同时写，如果多个线程同时写，会造成最后set的时候出现问题

image.png
image.png
image.png

与SynchronizedList对比

CopyOnWriteList没有fail-fast的

CopyOnWriteSet写时复制

SynchronizedList