跳跃表是一种比较巧妙的结构,其查询性能大部分都可以达到O(logN),Redis中的sorted set 就使用了这种结构。
Skip list的性质
(1) 由很多层结构组成,level是通过一定的概率随机产生的。
(2) 每一层都是一个有序的链表,默认是升序
(3) 最底层(Level 1)的链表包含所有元素。
(4) 如果一个元素出现在Level i 的链表中,则它在Level i 之下的链表也都会出现。
(5) 每个节点包含两个指针,一个指向同一链表中的下一个元素,一个指向下面一层的元素。
Java已经自带了这种
public class App { public static void main(String[] args) { Map<Integer, String> map = new ConcurrentSkipListMap<>(); map.put(1, "1"); map.put(3, "3"); map.put(2, "2"); map.forEach((k, v) -> { System.out.println(k + ":" + v); }); } }
参考:
https://blog.csdn.net/bigtree_3721/java/article/details/51291974