数据结构跳表SkipList的原理和代码实现

雨点打透心脏的1/2处 2022-06-15 11:00 274阅读 0赞

# 跳表简介 #

跳表是平衡树的一种替代的数据结构，但是和红黑树不相同的是，跳表对于树的平衡的实现是基于一种随机化的算法的，这样也就是说跳表的插入和删除的工作是比较简单的。

我们知道，普通单链表查询一个元素的时间复杂度为O(n)，即使该单链表是有序的，我们也不能通过2分的方式缩减时间复杂度。

![这里写图片描述][251350258885508.png]

如上图，我们要查询元素为55的结点，必须从头结点，循环遍历到最后一个节点，不算-INF(负无穷)一共查询8次。那么用什么办法能够用更少的次数访问55呢？最直观的，当然是新开辟一条捷径去访问55。

![这里写图片描述][251350261549492.png]

如上图，我们要查询元素为55的结点，只需要在L2层查找4次即可。在这个结构中，查询结点为46的元素将耗费最多的查询次数5次。即先在L2查询46，查询4次后找到元素55，因为链表是有序的，46一定在55的左边，所以L2层没有元素46。然后我们退回到元素37，到它的下一层即L1层继续搜索46。非常幸运，我们只需要再查询1次就能找到46。这样一共耗费5次查询。

那么，如何才能更快的搜寻55呢？有了上面的经验，我们就很容易想到，再开辟一条捷径。

![这里写图片描述][251350264357706.png]

如上图，我们搜索55只需要2次查找即可。这个结构中，查询元素46仍然是最耗时的，需要查询5次。即首先在L3层查找2次，然后在L2层查找2次，最后在L1层查找1次，共5次。很显然，这种思想和2分非常相似，那么我们最后的结构图就应该如下图。  
![这里写图片描述][251350266383879.png]

我们可以看到，最耗时的访问46需要6次查询。即L4访问55，L3访问21、55，L2访问37、55，L1访问46。我们直觉上认为，这样的结构会让查询有序链表的某个元素更快。那么究竟算法复杂度是多少呢？

如果有n个元素，因为是2分，所以层数就应该是log n层 (本文所有log都是以2为底)，再加上自身的1层。以上图为例，如果是4个元素，那么分层为L3和L4，再加上本身的L2，一共3层；如果是8个元素，那么就是3+1层。最耗时间的查询自然是访问所有层数，耗时logn+logn，即2logn。为什么是2倍的logn呢？我们以上图中的46为例，查询到46要访问所有的分层，每个分层都要访问2个元素，中间元素和最后一个元素。所以时间复杂度为**O(logn)**。

# 实现跳跃表 #

## 插入 ##

跳跃表的初试状态如下图，表中没有一个元素：

![这里写图片描述][251350269202093.png]

如果我们要插入元素2，首先是在底部插入元素2，如下图：

![这里写图片描述][251350280607176.png]

然后我们抛硬币，结果是正面，那么我们要将2插入到L2层，如下图  
![这里写图片描述][251350282325890.png]

继续抛硬币，结果是反面，那么元素2的插入操作就停止了，插入后的表结构就是上图所示。接下来，我们插入元素33，跟元素2的插入一样，现在L1层插入33，如下图：

![这里写图片描述][251350284207834.png]

然后抛硬币，结果是反面，那么元素33的插入操作就结束了，插入后的表结构就是上图所示。接下来，我们插入元素55，首先在L1插入55，插入后如下图：

![这里写图片描述][251350286075076.png]

然后抛硬币，结果是正面，那么L2层需要插入55，如下图：

![这里写图片描述][251350287482034.png]

继续抛硬币，结果又是正面，那么L3层需要插入55，如下图：

![这里写图片描述][251350290765233.png]

继续抛硬币，结果又是正面，那么要在L4插入55，结果如下图：

![这里写图片描述][251350292162191.png]

继续抛硬币，结果是反面，那么55的插入结束，表结构就如上图所示。

以此类推，我们插入剩余的元素。当然因为规模小，结果很可能不是一个理想的跳跃表。但是如果元素个数n的规模很大，学过概率论的同学都知道，最终的表结构肯定非常接近于理想跳跃表。

## 搜索 ##

![这里写图片描述][ec9fd643-f85c-3072-8634-60cfc88ab334.jpg]  
例子：查找元素 117  
(1) 比较 21， 比 21 大，往后面找  
(2) 比较 37, 比 37大，比链表最大值小，从 37 的下面一层开始找  
(3) 比较 71, 比 71 大，比链表最大值小，从 71 的下面一层开始找  
(4) 比较 85， 比 85 大，从后面找  
(5) 比较 117， 等于 117， 找到了节点。

/* 如果存在 x, 返回 x 所在的节点， * 否则返回 x 的后继节点 */  
    find(x)   
    {  
        p = top;  
        while (1) {  
            while (p->next->key < x)  
                p = p->next;  
            if (p->down == NULL)   
                return p->next;  
            p = p->down;  
        }  
    }

## 删除 ##

在各个层中找到包含 x 的节点，使用标准的 delete from list 方法删除该节点。  
例子：删除 71

![这里写图片描述][7bab9ad1-9f5a-37d0-bc38-89ee50d1bc0d.jpg]

# Java的跳表实现 #

表节点SkipListNode

package com.hqq.list;
    
    import java.net.CacheRequest;
    
    /** * SkipListNode * 跳跃表的节点,包括key-value和上下左右4个指针 * Created by heqianqian on 2017/6/1. */
    public class SkipListNode<T> {
        private int key;
        private T value;
        public SkipListNode<T> up, down, left, right;
    
        public static final int HEAD_KEY = Integer.MIN_VALUE;//负无穷
        public static final int TAIL_KEY = Integer.MAX_VALUE;//正无穷
    
        public SkipListNode(int k, T v) {
            this.key = k;
            this.value = v;
        }
    
        public int getKey() {
            return key;
        }
    
        public void setKey(int key) {
            this.key = key;
        }
    
        public T getValue() {
            return value;
        }
    
        public void setValue(T value) {
            this.value = value;
        }
    
        @SuppressWarnings("unchecked")
        public boolean equals(Object o) {
            if (this == o) {
                return true;
            }
            if (o == null) {
                return false;
            }
            if (!(o instanceof SkipListNode<?>)) {
                return false;
            }
    
            SkipListNode<T> ent;
            try {
                ent = (SkipListNode<T>) o;
            } catch (Exception e) {
                return false;
            }
            return (ent.getKey() == key) && (ent.getValue() == value);
        }
    
        @Override
        public String toString() {
            return "key-value:"+key+"-"+value;
        }
    }

跳表SkipList

package com.hqq.list;
    
    import java.util.Comparator;
    import java.util.Random;
    
    /** * SkipList * 不固定层级的跳跃表 * Created by heqianqian on 2017/6/1. */
    public class SkipList<T extends Comparable<? super T>> { 
    
        private SkipListNode<T> head, tail;
        private int nodes;//节点总数
        private int listLevel;//层数
        private Random random;//用于产生随机数
        private static final double PROBABILITY = 0.5;//向上提升一个的概率
    
        public SkipList() {
            random = new Random();
            clear();
        }
    
        /** * 清空跳跃表 */
        public void clear() {
            head = new SkipListNode<T>(SkipListNode.HEAD_KEY, null);
            tail = new SkipListNode<T>(SkipListNode.TAIL_KEY, null);
            horizontalLink(head, tail);
            listLevel = 0;
            nodes = 0;
        }
    
        /** * 水平双向连接 */
        private void horizontalLink(SkipListNode<T> node1, SkipListNode<T> node2) {
            node1.right = node2;
            node2.left = node1;
        }
    
        /** * 垂直双向连接 */
        private void vertiacallLink(SkipListNode<T> node1, SkipListNode<T> node2) {
            node1.down = node2;
            node2.up = node1;
        }
    
        /** * 在最下面一层，找到要插入的位置前面的那个key */
        private SkipListNode<T> findNode(int key) {
            SkipListNode<T> p = head;
            while (true) {
                while (p.right.getKey() != SkipListNode.TAIL_KEY && p.right.getKey() <= key) {
                    p = p.right;
                }
                if (p.down != null) {
                    p = p.down;
                } else {
                    break;
                }
            }
            return p;
        }
    
        /** * 查找是否存储key，存在则返回该节点，否则返回null */
        public SkipListNode<T> search(int key) {
            SkipListNode<T> p = findNode(key);
            return (key == p.getKey()) ? p : null;
        }
    
        /** * 向跳跃表中添加key-value */
        public void put(int k, T v) {
            SkipListNode<T> p = findNode(k);
            //如果key值相同，替换原来的vaule即可结束
            if (k == p.getKey()) {
                p.setValue(v);
                return;
            }
            SkipListNode<T> q = new SkipListNode<T>(k, v);
            backLink(p, q);
            int currentLevel = 0;//当前所层次是0
            //产生随机数
            while (random.nextDouble() < PROBABILITY) {
                //新建一个层
                if (currentLevel >= listLevel) {
                    listLevel++;
                    SkipListNode<T> p1 = new SkipListNode<T>(SkipListNode.HEAD_KEY, null);
                    SkipListNode<T> p2 = new SkipListNode<T>(SkipListNode.TAIL_KEY, null);
                    horizontalLink(p1, p2);
                    vertiacallLink(p1, head);
                    vertiacallLink(p2, tail);
                    head = p1;
                    tail = p2;
                }
                //把p移动到上一层
                while (p.up == null) {
                    p = p.left;
                }
                p = p.up;
    
                SkipListNode<T> e = new SkipListNode<T>(k, null);
                backLink(p, e);
                vertiacallLink(e, q);
                q = e;
                currentLevel++;
            }
            nodes++;
        }
    
        /** * 在node1后插入node2 */
        private void backLink(SkipListNode<T> node1, SkipListNode<T> node2) {
            node2.left = node1;
            node2.right = node1.right;
            node1.right.left = node2;
            node1.right = node2;
        }
    
        public boolean isEmpty() {
            return nodes == 0;
        }
    
        public int size() {
            return nodes;
        }
    
        @Override
        public String toString() {
            if (isEmpty()) {
                return "跳跃表为空";
            }
            StringBuilder builder = new StringBuilder();
            SkipListNode<T> p = head;
            while (p.down != null) {
                p = p.down;
            }
            while (p.left != null) {
                p = p.left;
            }
            if (p.right != null) {
                p = p.right;
            }
            while (p.right != null) {
                builder.append(p);
                builder.append("\n");
                p = p.right;
            }
            return builder.toString();
        }
    }

测试

package com.hqq.list;
    
    /** * SkipListTest * Created by heqianqian on 2017/6/1. */
    public class SkipListTest { 
        public static void main(String[] args) {
            SkipList<String> list = new SkipList<>();
            System.out.println(list);
            list.put(2, "he");
            list.put(1, "qianqian");
            list.put(1, "qianqian");//测试同一个key值
            list.put(3, "何");
            list.put(4, "芊");
            System.out.println(list);
            System.out.println(list.size());
        }
    }

测试结果

跳跃表为空
    key-value:1-qianqian
    key-value:2-he
    key-value:3-何
    key-value:4-芊
    
    4

--------------------

参考文章  
[http://www.cnblogs.com/acfox/p/3688607.html][http_www.cnblogs.com_acfox_p_3688607.html]  
[http://kenby.iteye.com/blog/1187303][http_kenby.iteye.com_blog_1187303]

[251350258885508.png]: /images/20220615/52a5417536e247378ff01ae415aeba5e.png
[251350261549492.png]: /images/20220615/01c36fee71e249f299a890393572bcf8.png
[251350264357706.png]: /images/20220615/54da7ed018a545b5a42b58c4be78398f.png
[251350266383879.png]: /images/20220615/79d0d11629d14d77b06bfc5f4c6ab1fb.png
[251350269202093.png]: /images/20220615/2004f295a1e24fe1b285d7d749e11a71.png
[251350280607176.png]: /images/20220615/70ad0b2c41b647b0a1be230350595e59.png
[251350282325890.png]: /images/20220615/60a77e07bbf94ae88368871549211601.png
[251350284207834.png]: /images/20220615/58a7887972d24fd0a663892ca909676c.png
[251350286075076.png]: /images/20220615/749c97d1617c42629f6f4a666c3b405d.png
[251350287482034.png]: /images/20220615/fc8441c2068b45bb84e0c6c93dc71ffe.png
[251350290765233.png]: /images/20220615/7f2e747808bc43628e55a4813f9ce766.png
[251350292162191.png]: /images/20220615/74f03daecd89457b9a35ce1d773c1299.png
[ec9fd643-f85c-3072-8634-60cfc88ab334.jpg]: /images/20220615/b760ec644215432a8cfe975947a6cf2d.png
[7bab9ad1-9f5a-37d0-bc38-89ee50d1bc0d.jpg]: /images/20220615/157c38d745544ecf86b23446223b7020.png
[http_www.cnblogs.com_acfox_p_3688607.html]: http://www.cnblogs.com/acfox/p/3688607.html
[http_kenby.iteye.com_blog_1187303]: http://kenby.iteye.com/blog/1187303