Qi

Cogito ergo sum

0%

JAVA-跳表

发表于 更新于 分类于 1.6k 6 分钟

二分查找要求元素可以随机访问，所以决定了需要把元素存储在连续内存。这样查找确实很快，但是插入和删除元素的时候，为了保证元素的有序性，就需要大量的移动元素了。
如果需要的是一个能够进行二分查找，又能快速添加和删除元素的数据结构，首先就是二叉查找树，二叉查找树在最坏情况下可能变成一个链表。
于是，就出现了平衡二叉树，根据平衡算法的不同有AVL树，B-Tree，B+Tree，红黑树等，但是AVL树实现起来比较复杂，平衡操作较难理解，这时候就可以用SkipList跳跃表结构。

Key-Value数据结构
目前常用的key-value数据结构有三种：Hash表、红黑树、SkipList，它们各自有着不同的优缺点（不考虑删除操作）：
Hash表：插入、查找最快，为O(1)；如使用链表实现则可实现无锁；数据有序化需要显式的排序操作。
红黑树：插入、查找为O(logn)，但常数项较小；无锁实现的复杂性很高，一般需要加锁；数据天然有序。
SkipList：插入、查找为O(logn)，但常数项比红黑树要大；底层结构为链表，可无锁实现；数据天然有序。

如果要实现一个key-value结构，需求的功能有插入、查找、迭代、修改，那么首先Hash表就不是很适合了，因为迭代的时间复杂度比较高；而红黑树的插入很可能会涉及多个结点的旋转、变色操作，因此需要在外层加锁，这无形中降低了它可能的并发度。而SkipList底层是用链表实现的，可以实现为lock free，同时它还有着不错的性能（单线程下只比红黑树略慢），非常适合用来实现我们需求的那种key-value结构。
LevelDB、Reddis的底层存储结构就是用的SkipList。

基于锁的并发

优点：

  1. 编程模型简单，如果小心控制上锁顺序，一般来说不会有死锁的问题；
  2. 可以通过调节锁的粒度来调节性能。

缺点：

  1. 所有基于锁的算法都有死锁的可能；
  2. 上锁和解锁时进程要从用户态切换到内核态，并可能伴随有线程的调度、上下文切换等，开销比较重；
  3. 对共享数据的读与写之间会有互斥。

无锁编程（lock free）

常见的lock free编程一般是基于CAS(Compare And Swap)操作：CAS(void *ptr, Any oldValue, Any newValue);
即查看内存地址ptr处的值，如果为oldValue则将其改为newValue，并返回true，否则返回false。X86平台上的CAS操作一般是通过CPU的CMPXCHG指令来完成的。CPU在执行此指令时会首先锁住CPU总线，禁止其它核心对内存的访问，然后再查看或修改*ptr的值。简单的说CAS利用了CPU的硬件锁来实现对共享资源的串行使用。

优点

  1. 开销较小：不需要进入内核，不需要切换线程；
  2. 没有死锁：总线锁最长持续为一次read+write的时间；
  3. 只有写操作需要使用CAS，读操作与串行代码完全相同，可实现读写不互斥。

缺点

  1. 编程非常复杂，两行代码之间可能发生任何事，很多常识性的假设都不成立。
  2. CAS模型覆盖的情况非常少，无法用CAS实现原子的复数操作。

而在性能层面上，CAS与mutex/readwrite lock各有千秋，简述如下：

  1. 单线程下CAS的开销大约为10次加法操作，mutex的上锁+解锁大约为20次加法操作，而readwrite lock的开销则更大一些。
  2. CAS的性能为固定值，而mutex则可以通过改变临界区的大小来调节性能；
  3. 如果临界区中真正的修改操作只占一小部分，那么用CAS可以获得更大的并发度。
  4. 多核CPU中线程调度成本较高，此时更适合用CAS。
    跳表和红黑树的性能相当，最主要的优势就是当调整(插入或删除)时，红黑树需要使用旋转来维护平衡性，这个操作需要动多个节点，在并发时候很难控制。而跳表插入或删除时只需定位后插入，插入时只需添加插入的那个节点及其多个层的复制，以及定位和插入的原子性维护。所以它更加可以利用CAS操作来进行无锁编程。

跳表使用多级链表来实现，可以在 O(log n) 的平均时间内执行插入、删除和查找操作。

以下是一个简单的 Java 实现示例，用于构建和使用跳表：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
import java.util.Random;

class SkipListNode {
    int value;
    SkipListNode[] next;

    public SkipListNode(int value, int level) {
        this.value = value;
        this.next = new SkipListNode[level + 1];
    }
}

public class SkipList {
    private int maxLevel;
    private SkipListNode head;
    private Random random;

    public SkipList() {
        this.maxLevel = 16; // 跳表的最大层级
        this.head = new SkipListNode(Integer.MIN_VALUE, maxLevel);
        this.random = new Random();
    }

    public int randomLevel() {
        int level = 1;
        while (random.nextDouble() < 0.5 && level < maxLevel) {
            level++;
        }
        return level;
    }

    public void insert(int value) {
        int level = randomLevel();
        SkipListNode newNode = new SkipListNode(value, level);

        SkipListNode current = head;
        for (int i = maxLevel; i >= 0; i--) {
            while (current.next[i] != null && current.next[i].value < value) {
                current = current.next[i];
            }
            if (i <= level) {
                newNode.next[i] = current.next[i];
                current.next[i] = newNode;
            }
        }
    }

    public boolean search(int value) {
        SkipListNode current = head;
        for (int i = maxLevel; i >= 0; i--) {
            while (current.next[i] != null && current.next[i].value < value) {
                current = current.next[i];
            }
            if (current.next[i] != null && current.next[i].value == value) {
                return true;
            }
        }
        return false;
    }

    public void display() {
        for (int i = maxLevel; i >= 0; i--) {
            SkipListNode current = head.next[i];
            System.out.print("Level " + i + ": ");
            while (current != null) {
                System.out.print(current.value + " ");
                current = current.next[i];
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        SkipList skipList = new SkipList();

        skipList.insert(3);
        skipList.insert(6);
        skipList.insert(9);
        skipList.insert(2);
        skipList.insert(5);

        skipList.display();

        System.out.println("Search 6: " + skipList.search(6)); // 输出 true
        System.out.println("Search 8: " + skipList.search(8)); // 输出 false
    }
}

在上面的示例中，我们首先定义了 SkipListNode 类来表示跳表中的节点。每个节点包含一个值和一个指向下一级的数组。然后，我们创建了 SkipList 类来实现跳表。randomLevel 方法用于随机生成节点的层级，insert 方法用于插入节点，search 方法用于搜索节点，display 方法用于打印跳表的内容。

请注意，这只是一个简单的跳表实现示例。在实际应用中，您可能需要考虑更多的功能和优化，以满足不同的需求。