几个集合工具知识回顾

    以前看过一些JDK源码，最近回顾了一下笔记，所以在这里对几个常见的集合工具做个记录。

 

一、跳表

    

    跳表SkipList就是有序链表+二分搜索的组合。它的效率可以做到和二分相同，时间复杂度是O(logn)，空间复杂度是O(n)。

    它的基本特征是：

1. 它是一个多层结构，每一层都是一个有序链表，且至少包含两个链表节点(头head节点和尾tail节点)；
2. 如果一个元素出现在某一层的链表中，那么在该层之下的链表也全都会出现（上一层的元素是当前层的元素的子集），最底层的链表包含了所有的元素；
3. 链表中的每个节点都包含两个指针，一个指向下一个兄弟链表节点，一个指向下一层的子链表节点；

    理想情况下，第二层只有第一层一半的节点数，而且均匀间隔，第三层则是1/4的节点数，以此类推，这样理想的层数就是logN。

    工作过程：

• 搜索过程很简单，就是从最高层链表开始，如果比当前节点大、比下一个节点小，那么去下一层查找，以此类推，一直找到最底层的最后一个节点；
• 插入过程需要确定插入的层数，通常给定一个统计概率p，产生一个0到1之间的随机数，如果这个随机数小于p，则将高度加1，直到产生的随机数大于概率p才停止。当概率为1/2或者是1/4的时候，整体的性能会比较好（当p为1/2的时候，也就是抛硬币的方法了）。而后，就是将元素插入到从最底层到第k层；

 

1.  ConcurrentSkipListMap

    ConcurrentSkipListMap内部的数据结构就是Index，它是跳表中的索引，本身是一个bucket(KV链表)，同时包含右指针和下指针。它通过HeadIndex(包含level层级)作为跳表每层的头结点，将整张表拎出来。

    先说删除操作，对于跳表而言主要是定位待删结点+删除该结点的一个复合操作，而在并发跳表中则是这样：

    ⑴ 先通过key和HeadIndex定位到待删除节点(二分搜索定位，比较器比较key是否相等)；
    ⑵ 将待删结点value值置为null(即标记待删除)，失败则自旋；
    ⑶ 向待删结点的next后继位置新增一个空的marker标记结点(用于分散并发冲突，即key值是否对应、value值是否为null、marker节点为空，如果不是则重试)；
    ⑷ 断链操作，让待删结点的pre前驱节点越过本身指向后继结点(非marker节点)，那么待删结点和marker标记结点将游离结点，最终被GC掉；

    插入操作类似，简单来说就是：先通过概率随机得到level值，然后新增一个结点到最底层的链表上，并新增一个纵向的引用关联，最后链接各个索引层次上的新节点。

 

二、哈希表

    HashMap的底层是基于“数组+链表”组成的，不过在JDK1.7和1.8中具体实现稍有不同。

    默认的负载因子0.75(4/3)，默认容量为16，也就意味着当容量达到了16*0.75=12就需要进行2的n次幂扩容，rehash、数据拷贝而耗性能，所以对大数据、性能敏感的应用通常提前预估好HashMap大小，减少rehash次数。

    工作过程：对传入key值做hash运算，而后与数组长度取模得到数组下标index。因为性能问题，HashMap规定数组的长度为2次幂，这样用2^n-1做位运算与取模效果一致，并且效率还要高的多。而判定key值是否相等的条件，是hashcode+key。

    谈hashmap就不得不说它存在的这两个问题：

• 链表过深：

  当hash冲突严重时，每个桶的链表越来越深，遍历效率越来越低。而在Java7之后，通过红黑树来对大链表做优化，提升查询效率。

  比如在put时，如果当前bucket(链表)的大小大于阈值(默认是8)时，将其转为红黑树；而get时，判断当前Node如果是TreeNode就按照树的方式查找，不是则按照链表的方式遍历查找。

• 并发时环形链表：

  在rehash时，链表拷贝是逐个进行的(头插法)，这意味着顺序会颠倒。如果这个时候刚好有另外一个线程在操作，就可能会出现A->B->A的情况，即环形链表。

  这个问题在Java8得到了解决，通过尾插法，使用2次幂扩展长度的方式，即用key的高位运算结果，如果扩容后判断原来hash值新增的1个bit是0还是1，0的话索引没变，1的话变成“原索引+oldCap”。这样就省去了重新hash值的操作和时间，避免了环形链表的问题。

    一般在JDK集合类里都会有“Fail-Fast机制”，这在hashmap里也有：

快速失败策略在源码中的实现是通过modCount域，就是修改次数，对HashMap内容的修改都将增加这个值，那么在迭代器初始化过程中会将这个值赋给迭代器的expectedModCount。在迭代过程中，判断modCount跟expectedModCount是否相等，如果不相等就表示已经有其他线程修改了Map。

注意：经管modCount被声明为volatile，保证线程之间修改的可见性。但迭代器的快速失败行为并不能得到保证，比如，存在非同步的并发修改的时候。 

 

1.  ConcurrentHashMap

    ConcurrentHashMap由Segment[]数组+里面的Entry组成，通过锁分段的方式来降低并发度(16等分，每个Segment一个ReentrantLock)。即：并发读不加锁，并发写对操作的segment加独占锁。ConcurrentHashMap也有全量锁的时候，比如扩容、rehash的时候。主要目标还是最小化更新竞争的同时保持并发可读性，使得空间消耗与HashMap大致相同。

    工作过程：
    1）put时，第一次hash确定key在哪个segment中；
    2）tryLock尝试获取锁，失败则阻塞(Java7是会自旋一阵而后升级为阻塞锁，默认是64次)；
    3）而后第二次hash在segment中确定key在链表的哪个Entry链表中；
    4）遍历判断hashcode和key值是否相等，相等就覆盖，不相等就new一个；
    5）最后判断要不要扩容，在返回前解锁分段锁。

 

    在Java8之后，ConcurrentHashMap的数据结构发生了很大变化，首先抛弃了分段锁的方案，使用Unsafe的CAS+阻塞锁。虽然仍是Node数组+链表的形式，但将锁分段更细化了。

    工作过程：如果根据key定位是一个空的话，尝试利用CAS new一个新的bucket，失败则自旋保证；如果不是空的话，则对链表头加阻塞锁，使用同步块来细化。实际上，在每一个桶中，头node都作为这个bucket的锁而锁住整个bucket。这样的策略，使得对HashMap的并发粒度呈线性减低，因为一个桶中node节点不会太多，不会总是冲突，扩容时更会均匀打散，当链表过深时(默认为8)则用红黑树保证查询效率。

跨段操作：

    某些操作需要涉及到多个segment，比如size()。HashMap统计各个bucket基本的思路是“提前做”，结构性更新时对计数器加1减1，而在ConcurrentHashMap中因为存在并发，情况就不同了。

    在JDK1.7中，先不加锁计算三次，比较前后计算结果，结果一致就认为是准确的，不一致就对Segment加锁再计算；

    在JDK1.8之后，先CAS的对baseCount加减，如果CAS失败，则自旋对counterCells加减(每个bucket一个counterCells)。然后在调用size()或mappingCount()的时候，累加baseCount和counterCells数组。

   

三、延时队列

    这里，我们不妨先谈谈优先级队列。

1.  PriorityQueue

    PriorityQueue是一个优先级的无界队列，意味着每次从队列取出的都是最小的元素。内部使用小顶堆来实现。

    工作过程：

• PriorityQueue的建堆过程和大顶堆的建堆过程基本一样，从上往下做siftDown操作。siftDown的过程就是将一个节点和它的左右子节点进行比较，然后和最小的子节点交换位置，一直向下到叶子节点，保证它比它所有的子节点都要小。
• 而每次添加新元素实际上是在数组的后面追加。先判断数组长度是否需要扩容，而后做siftUp操作。和siftDown类似，一个节点和它的父节点比较，如果果它比父节点小则交换位置，一直向上到根节点这样，就变成符合条件的小顶堆了。

    默认情况下元素采用自然顺序升序排序。默认的长度为11，扩容时若容量小于64，则新容量是oldCap * 2 + 2，否则是oldCap * 1.5。即容量越小增长得越快。

    PriorityQueue在JDK中对应的实现类是PriorityBlockingQueue，优先级的无界阻塞队列。与ConcurrentHashMap不同，PriorityBlockingQueue在扩容时没有全量锁的时候，事实上为了获得更好的并发性，在扩容开始时PriorityBlockingQueue就释放了全局锁，后面的扩容操作通过乐观锁来进行并发控制。

 

2.  DelayQueue

    DelayQueue等同于BlockingQueue + PriorityQueue + Delayed接口。
    DelayQueue是一个延时的无界阻塞队列。其实就是使用PriorityQueue进行元素的排序，以元素过期时间为排序条件，以ReentrantLock作为主锁，即头元素是最先过期的元素。它会根据time的先后时间排序，若time相同则根据sequenceNumber序号排序。

    DelayQueue核心字段是：全局独占锁，优先级队列(用于存储元素)，leader即当前消费者线程，和available条件变量。DelayQueue的内部实现，其实就是你在offer一个过期时间为N的元素时，先入优先级队列，之后你take一个任务的时候，判断列表头的到期时间，到期就去消费，没到期则通过available条件变量进行await阻塞等待，过N个时间单位到期唤醒后再去消费。

    具体的工作过程：

• 当你offer一个元素时：
  1）先加锁，入优先级队列；
  2）然后peek一下，如果队首元素是刚插入的元素，则设置leader为null，并唤醒阻塞在available上的线程进行消费；
  3）释放锁；
• 当你要take一个元素时：
  1）先加锁；
  2）然后peek一下，如果队首元素为空则阻塞，不为空则获取队首元素的超时时间，已超时则poll出队；
  3）如果leader不为null，说明消费者线程已拿到锁，阻塞当前线程；
  4）如果leader为null则将leader指向当前线程，阻塞等待剩余的到期时间，唤醒后将leader置为null。这时再判断一次，如果leader为null并且队列不为空，说明没有其他线程在等待，则唤醒available上的线程；
  5）释放锁；

 

3.  TimingWheel

    JDK的Timer和DelayQueue插入和删除操作的平均时间复杂度为O(nlogn)，不能满足一般分布式系统的性能要求，而基于时间轮(TimingWheel)算法则可以将插入和删除操作的时间复杂度降为O(1)。 

    

    Kafka中的时间轮(TimingWheel)是一个存储定时任务的环形队列，队列中的每个元素是一个用于存储定时任务的双端链表，链表中的每一项就是定时任务项，里面是真正的定时任务。

    环形队列中的每个元素就是一个个时间格，每个时间格代表当前时间轮的基本时间跨度(tickMs)。时间格的个数是固定的(wheelSize)，整个时间轮的总体时间跨度(interval)为 tickMs × wheelSize。时间轮有一个表盘指针(currentTime)，表示时间轮当前所处的时间，它是tickMs的整数倍。currentTime指向的当前时间格，就需要处理此时间格所对应的TimerTaskList的所有任务。

时间轮 = 时间格(环形队列) » 定时任务列表(双端链表) » 定时任务项

    初始情况下表盘指针currentTime指向时间格0。当对某个时间格做相应的到期操作时，同时有定时任务插入，则复用时间轮，这就是环形队列的好处了。整个时间轮的总体跨度是不变的，随着指针currentTime的推进，当前时间轮所能处理的时间段也在不断后移。

    对于每个使用到的TimerTaskList都会加入到DelayQueue中，根据TimerTaskList对应的到期时间来排序，这意味着最短到期时间的会在列表头，优先执行。

 

    

    超长任务问题：现在看来情况良好，没有什么问题，但倘若有个定时时长大于或者远大于interval的任务进来，如果直接扩充wheelSize是没有底限的，而且对于超长定时任务，过多的内存占用，性能效率都不会太好。因此引入了层级时间轮的概念，通过时间轮升/降级来解决大于当前时间周期的定时任务。

    当任务的到期时间超过了当前时间轮的时间跨度时，尝试添加到上层时间轮中。每一层时间轮的时间格个数wheelSize是差不多固定的，但上一层的基本时间跨度tickMs为下一层的总体时间跨度interval，以此类推。

    你应该注意到，越上层的时间轮时间跨度越大，即便currentTime当前指向某个时间格，任务的到期操作也很难执行。这时又会有一个时间轮降级的动作，会将这个定时任务重新提交到下一层的时间轮中，依次类推。可想而知，底层的时间轮，基本时间跨度很小，比如在Kafka默认实现中，tickMs=1ms，wheelSize=20，而在Quartz中，tickMs=1ms，wheelSize=60，秒、分、时。

 

    性能调优：

• 在插入任务之前先检查任务是否完成，因为存在有些任务超时直接就完成超时操作的场景；
• 每个双向链表TimerTaskList都会有一个哨兵节点，来简化边界条件。它是一个附加的链表节点，作为第一个节点，值域中并不存储任何东西；
• 每一层的currentTime都必须是tickMs的整数倍，这是用一个单线程来维护的，也叫“到期操作收割机”，通过“拨动”执行指针来触发定时任务；

“空推进”问题：

    DelayQueue中的列表头到期时间是确定的，这里获取DelayQueue的队头只需要O(1)的时间复杂度，但如果是每秒定时推进的话，比如到期时间200s，那么获取到这个定时任务需要执行200次推进且有199次属于“空推进”，这样无疑会无故空耗机器的性能资源。

    所以，为了避免“空推进”，引入DelayQueue来做时间“拨动”，以少量空间换时间，优化性能。简单来说就是，用时间轮TimingWheel来做任务的插入和删除操作，用延迟队列DelayQueue来做时间推进的工作。

 

4.  RingBuffer

    这里说的是Disruptor的RingBuffer，它不像传统的队列和其它RingBuffer，具有head、tail、count这三个指针，也是三个冲突点。每次操作元素时，入队列、出队列还有区分是否空队列都会有竞争，而且这三个变量，通常也在一个缓冲行里，又会有“伪共享”问题，无论操作哪一个都会导致其它缓存不命中。而而Disruptor的RingBuffer的优点是：通过减少竞争点，比如不删除数据而是直接覆盖，所以不需要tail尾指针；通过RingBuffer重复利用数组，来减少GC；利用数组对CPU Cache友好的特性，缓存行填充，来避免伪共享，提高效率。

伪共享问题：

缓存是由缓存行组成的，通常是64字节（比较旧的处理器缓存行是32字节），引用主内存中的一块地址。若数据结构中的项在内存中不是彼此相邻的（比如链表），就得不到这种缓存加载所带来的性能优势。

如果有一个单独的变量head，然后又有另一个变量紧挨着它，tail。那么当加载head到缓存的时候，也免费加载了tail。那么，如果你更新了head的值，缓存中的值和内存中的值都被更新了，再想要读tail值时，整个缓存行都要重新从内存中读取，也就意味着应用程序被缓存未命中给拖慢了。如果两个独立的线程同时写这两个不同的值会更糟，因为遇到两个线程之间的写冲突了，尽管它们写入的是不同的变量。这就叫作“伪共享”，无声的性能杀手。

一般的解决方案是，增大数组元素的间隔使得由不同线程存取的元素位于不同的缓存行上，以空间换时间。俗称“缓存行填充”，将32字节、64字节或者128字节填满，不填满一样有伪共享问题，但这肯定是会浪费空间的。在JDK1.7中，Sun官方提供了一个优化方案，通过添加@Contended注解，JVM会自动的进行缓存行填充，但应用程序运行时必须加上虚拟机参数-XX:-RestrictContended，这个注解才会生效。

    Disruptor的RingBuffer，只需要一个序号指向下一个可用的空间，同时做缓存行填充，通过补全来确保RingBuffer的序号不会和其他东西同时存在于一个缓存行中，所以没有伪共享问题和非预期的竞争。   

    Disruptor的RingBuffer的工作原理，简单来说，就是把争抢多个窗口买票的行为，通过Barrier规范为：所有人先到Barrier处取号，然后凭序号去对应窗口买票。取号消耗的时间很短，一个Barrier就足够，而买票消耗时间很长，各个窗口独立服务。

    具体的工作过程：

• 在定位元素时，与HashMap类似的，按size进行位运算来定位出数组的下标（所以数组长度也是2^n）。RingBuffer中每格都有序号，并用一个变量来指向可用的位置。
• 在插入元素时，为2阶段提交，首先申请sequence序号，如果发现所有数据都没被被消费，会等待（为了避免RingBuffer重叠）直到有可用的sequence；获取到可用的sequence后，再进行publish操作。

    那么，Disruptor如何防止多个线程重复写同一个元素呢？在多个生产者的情况下，Disruptor让每个线程获取不同的一段数组空间进行操作，就是在分配元素的时候，通过CAS判断一下这段空间是否已经分配出去即可。但这样做，意味着很有可能出现“脏读”，读到还未写的旧数据。“如何防止读取的时候读到还未写的元素”，Disruptor是这样做的，在多个生产者的情况下，引入了一个与RingBuffer大小相同的buffer：available Buffer。当某个位置写入成功的时候，便把availble Buffer相应的位置标记为写入成功。读取的时候，会遍历available Buffer，来判断元素是否已经就绪。

    Disruptor的等待策略：

名称	措施	备注
BlockingWaitStrategy	加锁	CPU资源占用少，延迟大、吞吐低
BusySpinWaitStrategy	自旋	通过自旋，来减少线程切换导致的系统调用。CPU资源占用高，延迟大
PhasedBackoffWaitStrategy	自旋+yield+自定义策略	混合上面多种策略，根据时间参数和传入的等待策略来决定使用哪种等待策略。
SleepingWaitStrategy	自旋+yield+sleep	多次自旋尝试不成功后，选择让出CPU，等待下次调度，多次调度后仍不成功，尝试睡眠一个纳秒级别的时间后再尝试。这种策略平衡了延迟和CPU资源占用，但延迟不均匀。
TimeoutBlockingWaitStrategy	加锁，有超时限制	相对于BlockingWaitStrategy来说，设置了等待时间，超时后抛异常
YieldingWaitStrategy	自旋+yield+自旋	多次自旋尝试不成功后，选择让出CPU，等待下次调度。这种策略平衡了延迟和CPU资源占用，延迟比较均匀。

 

四、COW列表

    在更新时申请写锁，复制对象并修改，修改完毕后切换对象引用，而读取则不加锁。这种方式被称为“写时复制（copy-on-write）”，即COW机制。CopyOnWriteArrayList就是COW的典型实现。

    CopyOnWriteArrayList的内部实现，拿add()方法来说，就是当对列表进行修改操作时，先lock一把(使用ReentrantLock)，copy一个数组(使用Arrays.copyOf()方法，其内部使用System.arraycopy函数拷贝数据，因为是native方法，效率比普通数组拷贝效率要高)，数组长度在当前基础上加1，然后在新数组追加新数据，再将该新数组的引用赋予当前数组，最后解锁。因为对更新操作是在副本中进行的，所以无锁，适合于读远多于写的情况。

与Java的COW不同的是，Linux下，不是直接将父进程的数据拷贝到子进程中，而是子进程共享父进程的物理空间，当父子进程有内存写入操作时触发异常中断，再将内存页复制一份。当我们通过fork()函数创建出的子进程，它会与父进程共享物理内存空间(其实是直接引用父进程的物理空间)。当父子进程中有更改数据段的行为发生时，再为子进程相应的分配物理空间。

具体来说，就是fork()之后，kernel把父进程中的内存页的权限都设为read-only，子进程的地址空间指向父进程。当父子进程都只读共享内存时，相安无事。当其中某个进程写内存时，CPU检测到内存页是read-only，触发页异常中断(page-fault)，开始走kernel的一个中断例程。在中断例程中，kernel就会把触发异常的页复制一份，父子进程各自持有独立的一份。

这样做是为了减少不必要的资源分配，如果没有修改数据就不会有副本。