Skiplist

介绍ConcurrentSkipListSet底层是通过ConcurrentNavigableMap来实现的，它是一个有序的线程安全的集合。 源码分析它的源码比较简单，跟通过Map实现的Set基本是一致，只是多了一些取最近的元素的方法。 // 实现了NavigableSet接口，并没有所谓的ConcurrentNavigableSet接口public class ConcurrentSkipListSet<E> extends AbstractSet<E> implements NavigableSet<E>, Cloneable, java.io.Serializable { private static final long serialVersionUID = -2479143111061671589L; // 存储使用的map private final ConcurrentNavigableMap<E,Object> m; // 初始化 public ConcurrentSkipListSet() { m = new ConcurrentSkipListMap<E,Object>(); } // 传入比较器 public ConcurrentSkipListSet(Comparator<? super E> comparator) { m = new ConcurrentSkipListMap<E,Object>(comparator); } // 使用ConcurrentSkipListMap初始化map // 并将集合c中所有元素放入到map中 public ConcurrentSkipListSet(Collection<? extends E> c) { m = new ConcurrentSkipListMap<E,Object>(); addAll(c); } // 使用ConcurrentSkipListMap初始化map // 并将有序Set中所有元素放入到map中 public ConcurrentSkipListSet(SortedSet<E> s) { m = new ConcurrentSkipListMap<E,Object>(s.comparator()); addAll(s); } // ConcurrentSkipListSet类内部返回子set时使用的 ConcurrentSkipListSet(ConcurrentNavigableMap<E,Object> m) { this.m = m; } // 克隆方法 public ConcurrentSkipListSet<E> clone() { try { @SuppressWarnings("unchecked") ConcurrentSkipListSet<E> clone = (ConcurrentSkipListSet<E>) super.clone(); clone.setMap(new ConcurrentSkipListMap<E,Object>(m)); return clone; } catch (CloneNotSupportedException e) { throw new InternalError(); } } /* ---------------- Set operations -------------- */ // 返回元素个数 public int size() { return m.size(); } // 检查是否为空 public boolean isEmpty() { return m.isEmpty(); } // 检查是否包含某个元素 public boolean contains(Object o) { return m.containsKey(o); } // 添加一个元素 // 调用map的putIfAbsent()方法 public boolean add(E e) { return m.putIfAbsent(e, Boolean.TRUE) == null; } // 移除一个元素 public boolean remove(Object o) { return m.remove(o, Boolean.TRUE); } // 清空所有元素 public void clear() { m.clear(); } // 迭代器 public Iterator<E> iterator() { return m.navigableKeySet().iterator(); } // 降序迭代器 public Iterator<E> descendingIterator() { return m.descendingKeySet().iterator(); } /* ---------------- AbstractSet Overrides -------------- */ // 比较相等方法 public boolean equals(Object o) { // Override AbstractSet version to avoid calling size() if (o == this) return true; if (!(o instanceof Set)) return false; Collection<?> c = (Collection<?>) o; try { // 这里是通过两次两层for循环来比较 // 这里是有很大优化空间的，参考上篇文章CopyOnWriteArraySet中的彩蛋 return containsAll(c) && c.containsAll(this); } catch (ClassCastException unused) { return false; } catch (NullPointerException unused) { return false; } } // 移除集合c中所有元素 public boolean removeAll(Collection<?> c) { // Override AbstractSet version to avoid unnecessary call to size() boolean modified = false; for (Object e : c) if (remove(e)) modified = true; return modified; } /* ---------------- Relational operations -------------- */ // 小于e的最大元素 public E lower(E e) { return m.lowerKey(e); } // 小于等于e的最大元素 public E floor(E e) { return m.floorKey(e); } // 大于等于e的最小元素 public E ceiling(E e) { return m.ceilingKey(e); } // 大于e的最小元素 public E higher(E e) { return m.higherKey(e); } // 弹出最小的元素 public E pollFirst() { Map.Entry<E,Object> e = m.pollFirstEntry(); return (e == null) ? null : e.getKey(); } // 弹出最大的元素 public E pollLast() { Map.Entry<E,Object> e = m.pollLastEntry(); return (e == null) ? null : e.getKey(); } /* ---------------- SortedSet operations -------------- */ // 取比较器 public Comparator<? super E> comparator() { return m.comparator(); } // 最小的元素 public E first() { return m.firstKey(); } // 最大的元素 public E last() { return m.lastKey(); } // 取两个元素之间的子set public NavigableSet<E> subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive) { return new ConcurrentSkipListSet<E> (m.subMap(fromElement, fromInclusive, toElement, toInclusive)); } // 取头子set public NavigableSet<E> headSet(E toElement, boolean inclusive) { return new ConcurrentSkipListSet<E>(m.headMap(toElement, inclusive)); } // 取尾子set public NavigableSet<E> tailSet(E fromElement, boolean inclusive) { return new ConcurrentSkipListSet<E>(m.tailMap(fromElement, inclusive)); } // 取子set，包含from，不包含to public NavigableSet<E> subSet(E fromElement, E toElement) { return subSet(fromElement, true, toElement, false); } // 取头子set，不包含to public NavigableSet<E> headSet(E toElement) { return headSet(toElement, false); } // 取尾子set，包含from public NavigableSet<E> tailSet(E fromElement) { return tailSet(fromElement, true); } // 降序set public NavigableSet<E> descendingSet() { return new ConcurrentSkipListSet<E>(m.descendingMap()); } // 可分割的迭代器 @SuppressWarnings("unchecked") public Spliterator<E> spliterator() { if (m instanceof ConcurrentSkipListMap) return ((ConcurrentSkipListMap<E,?>)m).keySpliterator(); else return (Spliterator<E>)((ConcurrentSkipListMap.SubMap<E,?>)m).keyIterator(); } // 原子更新map，给clone方法使用 private void setMap(ConcurrentNavigableMap<E,Object> map) { UNSAFE.putObjectVolatile(this, mapOffset, map); } // 原子操作相关内容 private static final sun.misc.Unsafe UNSAFE; private static final long mapOffset; static { try { UNSAFE = sun.misc.Unsafe.getUnsafe(); Class<?> k = ConcurrentSkipListSet.class; mapOffset = UNSAFE.objectFieldOffset (k.getDeclaredField("m")); } catch (Exception e) { throw new Error(e); } }}可以看到，ConcurrentSkipListSet基本上都是使用ConcurrentSkipListMap实现的，虽然取子set部分是使用ConcurrentSkipListMap中的内部类，但是这些内部类其实也是和ConcurrentSkipListMap相关的，它们返回ConcurrentSkipListMap的一部分数据。 ...

介绍跳表是一个随机化的数据结构，实质就是一种可以进行二分查找的有序链表。 跳表在原有的有序链表上面增加了多级索引，通过索引来实现快速查找。 跳表不仅能提高搜索性能，同时也可以提高插入和删除操作的性能。 存储结构跳表在原有的有序链表上面增加了多级索引，通过索引来实现快速查找。 源码分析主要内部类内部类跟存储结构结合着来看，大概能预测到代码的组织方式。 // 数据节点，典型的单链表结构static final class Node<K,V> { final K key; // 注意：这里value的类型是Object，而不是V // 在删除元素的时候value会指向当前元素本身 volatile Object value; volatile Node<K,V> next; Node(K key, Object value, Node<K,V> next) { this.key = key; this.value = value; this.next = next; } Node(Node<K,V> next) { this.key = null; this.value = this; // 当前元素本身(marker) this.next = next; }}// 索引节点，存储着对应的node值，及向下和向右的索引指针static class Index<K,V> { final Node<K,V> node; final Index<K,V> down; volatile Index<K,V> right; Index(Node<K,V> node, Index<K,V> down, Index<K,V> right) { this.node = node; this.down = down; this.right = right; }}// 头索引节点，继承自Index，并扩展一个level字段，用于记录索引的层级static final class HeadIndex<K,V> extends Index<K,V> { final int level; HeadIndex(Node<K,V> node, Index<K,V> down, Index<K,V> right, int level) { super(node, down, right); this.level = level; }}（1）Node，数据节点，存储数据的节点，典型的单链表结构； ...

skiplist简介skip List是一种随机化的数据结构，基于并联的链表，实现简单，插入、删除、查找的复杂度均为O(logN)（大多数情况下），因为其性能匹敌红黑树且实现较为简单，因此在很多著名项目都用跳表来代替红黑树，例如LevelDB、Reddis的底层存储结构就是用的SkipList。目前常用的key-value数据结构有三种：Hash表、红黑树、SkipList，它们各自有着不同的优缺点：Hash表：插入、查找最快，为O(1)；如使用链表实现则可实现无锁；数据有序化需要显式的排序操作。红黑树：插入、查找为O(logn)，但常数项较小；无锁实现的复杂性很高，一般需要加锁；数据天然有序。SkipList：插入、查找为O(logn)，但常数项比红黑树要大；底层结构为链表，可无锁实现；数据天然有序。SkipList基本数据结构及其实现一个跳表，应该具有以下特征：1、一个跳表应该有几个层（level）组成；通常是10-20层，leveldb中默认为12层。2、跳表的第0层包含所有的元素；且节点值是有序的。3、每一层都是一个有序的链表；层数越高应越稀疏，这样在高层次中能’跳过’许多的不符合条件的数据。4、如果元素x出现在第i层，则所有比i小的层都包含x；5、每个节点包含key及其对应的value和一个指向该节点第n层的下个节点的指针数组x->next[level]表示第level层的x的下一个节点skiplist的查询过程查询的第一个比vx大的节点的前一个值，看是否相等。相等则存在，否则查找下一层，直到层数为0。以已有数据13、22、75、80、99为例从最高层（此处为2）开始1、level2找到结点Node75小于80，且level2.Node75->next 大于80，则进入level1查找(此处已经跳过了13~75中间的结点（22), 2、level1.Node75 < 80 < level1.Node75->next，进入level03、level0.Node75->next 等于80，找到结点skiplist的插入过程假设插入一新键值key，值为84，level为当前层1、从最高层开始找到每一层比84大的节点的前一个值，存入prev[level]。这里prev[2] = leve2.Node75prev[1] = leve1.Node75prev[0] = level0.Node802、初始化一个新的节点843、为x随机选择一个高度h,这里选24、x->next[0..h-1] = prev[0..h-1]->next5、prev[0..h-1]->next[0..h-1] = x（步骤4、5为链表插入结点的操作）skiplist删除操作删除操作类似于插入操作，包含如下3步：1、查找到需要删除的结点 2、删除结点 3、调整指针总结如果要实现一个key-value结构，需求的功能有插入、查找、迭代、修改，那么首先Hash表就不是很适合了，因为迭代的时间复杂度比较高；而红黑树的插入很可能会涉及多个结点的旋转、变色操作，因此需要在外层加锁，这无形中降低了它可能的并发度。而SkipList底层是用链表实现的，可以实现为lock free，同时它还有着不错的性能（单线程下只比红黑树略慢），非常适合用来实现我们需求的那种key-value结构。