ConcurrentSkipListMap 学习笔记

ConcurrentSkipListMap 学习笔记

标签（空格分隔）： juc学习

基于跳跃表的线程安全的map集合。针对某一特殊需求而设计的——支持排序，同时支持搜索目标返回最接近匹配项的导航方法。

容器的主要功能：增删查

查

1. findPredecessor（key）从左上角一直往右，往下，往右，往下查，直到查到有相同key或者null
2. findNode(Object key)在查的时候直接或间接的帮忙删除节点。（像并查集，在查询的时候做删除操作，而删除动作简单）

增

1. 根据给定的key从跳表的左上方往右或者往下查找到Node链表的前驱Node结点，这个查找过程会删除一些已经标记为删除的结点。

2.找到前驱结点后，开始往后插入查找插入的位置（因为找到前驱结点后，可能有另外一个线程在此前驱结点后插入了一个结点，所以步骤①得到的前驱现在可能不是要插入的结点的前驱，所以需要往后查找）。

3. 随机生成一个种子，判断是否需要增加层级，并且在各层级中插入对应的Index结点。

删

1. 根据key值找到前驱结点，查找的过程会删除一个标记为删除的结点。

2. 从前驱结点往后查找该结点。

3. 在该结点后面添加一个marker结点，若添加成功，则将该结点的前驱的后继设置为该结点之前的后继。

4. 头结点的next域是否为空，若为空，则减少层级。

理解到的东西:
1、cas操作是根据Unsafe这个类，通过计算偏移量改写对象的属性值。
2、cas去实现并发，需要在代码每次都考虑是否被修改，代码可读性差。
3、for循环前可以加标志 xx,当多层循环嵌套时，可以break xx结束到最外层循环。