ConcurrentSkipListMap - 有序

跳表

假设有一个链表，我们要查找某个节点，则我们需要逐个的查找链表的每个节点
image.png
如果链表是有序的，并且每隔一个节点都有一个指向其前面2个位置节点的指针，那我们只需要最多查找⌈N/2⌉个节点（N为链表长度）
image.png如果再每隔3个节点就有指向其前面4个位置节点的指针，那么我们就只需要查找不超过⌈N/4⌉+2个节点
image.png也即如果每个(2^i)位置的节点都有指向其前面2^i个位置节点的指针，则查找某个节点的次数可以下降到⌈log2^n⌉次（只是指针数会变为之前的双倍）
image.png这种数据结构可以用于快速的查找，只是插入和删除不太容易实现。

ConcurrentHashMap - 无序



CopyOnWriteArrayList - 写时复制

  1. 内部实现是采用写入数据的时候，会copy原数组，复制到一个新数组中，
  2. 然后将元素添加到新数组末尾。这个写的过程使用了ReentrantLock可重入锁。
  3. 但它读取数据是不加锁的。所以适用场景是读多写少的场景下。

BlockingQueue