SkipList

A Java implementation of skip list.

跳表的Java语言实现。

Introduction

Skip lists are data structures that use probabilistic balancing rather than strictly enforced balancing. As a result, the algorithms for insertion and deletion in skip lists are much simpler and significantly faster than equivalent algorithms for balanced trees.

跳表是90年代由William Pugh发明的一种概率平衡数据结构。跳表的平衡是一种基于随机的非严格平衡。它完全基于链表实现，而不涉及树的结构，和普通的平衡树相比， 跳表的新增和删除操作实现相对简单很多。跳表的核心思想就是将扁平的列表进行分层，每个节点在插入的时候会生成一个随机的层数，基于此随机的层数与跳表中相邻的数据连接。 跳表的增删改查操作具有O(log N)的均摊复杂度。

Implementation

The SkipListMap uses skip list as the underlying essential data structure and implements java.util.Map. Two extra sentinel nodes(head and tail) are used for the sake of convenience. The SkipListMap is generic and supports particular comparision function by passing a custom java.util.Comparator to the constructor.

SkipListMap是基于跳表的实现的map。 基本思路与跳表原著论文一致，在实现时为了方便起见，加入了head和tail两个哨兵节点。

Todo List

• Implement java.util.NavigableMap interface.
• Add more test cases.

Reference

• Skip lists: a probabilistic alternative to balanced trees
• Redis ZSET implementation
• java.util.concurrent.ConcurrentSkipListMap By Doug Lea

License

MIT License