跳跃表-随机化数据结构

灰太狼 2022-08-20 13:09 140阅读 0赞

Skip list(跳表）是一种可以代替平衡树的数据结构

参考  
[http://www.mathcs.emory.edu/~cheung/Courses/323/Syllabus/Map/skip-list-impl.html][http_www.mathcs.emory.edu_cheung_Courses_323_Syllabus_Map_skip-list-impl.html]

[http://www.acmerblog.com/skip-list-impl-java-5773.html][http_www.acmerblog.com_skip-list-impl-java-5773.html]

Skip list的性质

(1) 由很多层结构组成，level是通过一定的概率随机产生的。  
(2) 每一层都是一个有序的链表，默认是升序  
(3) 最底层(Level 1)的链表包含所有元素。  
(4) 如果一个元素出现在Level i 的链表中，则它在Level i 之下的链表也都会出现。  
(5) 每个节点包含两个指针，一个指向同一链表中的下一个元素，一个指向下面一层的元素。

![这里写图片描述][20160229112003562]

Java代码实现：

1.  SkipListEntry.java ， 这是跳跃表中存储的每个元素实体类，包含 上下左右 四个指针。

package skiplist;
    
    public class SkipListEntry {
        public String key;
        public Integer value;
    
        public int pos;
    
        public SkipListEntry up, down, left, right;
    
        public static String negInf = new String("-oo");
        public static String posInf = new String("+oo");
    
        public SkipListEntry(String k, Integer v){
            key = k;
            value = v;
    
            up = down = left = right = null;
        }
    
        public String getKey() {
            return key;
        }
    
        public void setKey(String key) {
            this.key = key;
        }
    
        public Integer getValue() {
            return value;
        }
    
        public Integer setValue(Integer value) {
            Integer OldValue = value;
            this.value = value;
    
            return OldValue;
        }
    
        @Override
        public boolean equals(Object obj) {
            SkipListEntry ent;
            try{
                ent = (SkipListEntry) obj;
            } catch (ClassCastException ex){
                return false;
            }
            return (ent.getKey() == key) && (ent.getValue() == value);
        }
    
        @Override
        public String toString() {
            return "SkipListEntry [key=" + key + ", value=" + value + "]";
        }
    
    
    
    
    
    
    
    
    }

2 SkipList.java, 跳跃表类，包含算法的实现。 head 和 tail 分别是 顶层的头和尾。

package skiplist;
    
    import java.util.Random;
    
    public class SkipList { 
        public SkipListEntry head;
        public SkipListEntry tail;
    
        public int n; // 跳跃表中元素的个数
        public int h; // 跳跃表的高度
    
        public Random r;
    
        public SkipList()
        {
            SkipListEntry p1,p2;
    
            p1 = new SkipListEntry(SkipListEntry.negInf, null);
            p2 = new SkipListEntry(SkipListEntry.posInf, null);
    
            head = p1;
            tail = p2;
    
            p1.right = p2;
            p2.left = p1;
    
            n = 0;
            h = 0;
            r = new Random();
    
    
    
        }
    
        /** 返回包含元素的个数 */
        public int size()
        {
            return n;
        }
    
        /** 跳跃表是否为空 */
        public  boolean isEmpty()
        {
            return (n == 0);
        }
    
        /** 在最下面一层， 找到要插入的位置前面的哪个key*/
        public SkipListEntry findEntry(String k)
        {
            SkipListEntry p;
            p = head;
    
            while(true){
                while( p.right.key != SkipListEntry.posInf && 
                        p.right.key.compareTo(k) <= 0){
                    p = p.right;
    
                }
                if(p.down != null){
                    p = p.down;
                }else{
                    break;
                }
            }
    
            return p;
        }
    
        /** 返回和key绑定的值 */
        public Integer get(String k)
        {
            SkipListEntry p;
    
            p = findEntry(k);
            if (k.equals(p.getKey())){
                return p.value;
            }else{
                return null;
            }
    
        }
    
        /** 放一个key-value到跳跃表中 ，替换原有的并返回*/
        public Integer put(String k , Integer v){
            SkipListEntry p, q;
            int i;
            /** 找到key 就返回原值， 将新值替换进链表 */
            p = findEntry(k);
            if(k.equals(p.getKey())){
                Integer old = p.value;
                p.value = v;
                return old;
            }
    
            /** 如果没有找到新值，就新建一个 */
            q = new SkipListEntry(k, v);
    
            q.left = p;
            q.right = p.right;
            p.right.left = q;
            p.right = q;
    
            i = 0;
            while(r.nextDouble() < 0.5){
                //如果超出了高度，需要重新建一个顶层
                if (i >= h) {
                    SkipListEntry p1, p2;
    
                    h = h + 1;
                    p1 = new SkipListEntry(SkipListEntry.negInf, null);
                    p2 = new SkipListEntry(SkipListEntry.posInf, null);
    
                    p1.right = p2;
                    p1.down = head;
    
                    p2.left = p1;
                    p2.down = tail;
    
                    head.up = p1;
                    tail.up = p2;
    
                    head = p1;
                    tail = p2;
                }
    
                // 将p移动到 最左边
                while(p.up == null){
                    p = p.left;
                }
    
                p = p.up;
    
                SkipListEntry e;
    
                e = new SkipListEntry(k, null); 
                e.left = p;
                e.right = p.right;
                e.down = q;
    
                p.right.left = e;
                p.right = e;
                q.up = e;
    
                q = e; // q 进行下一层迭代
                i = i + 1; // 当前层 +1
    
            }
    
            n = n + 1;
    
            return (null);
    
        }
    
    
        public Integer remove(String key) {
            return (null);
        }
    
        public void printHorizontal() {
            String s = "";
            int i;
            SkipListEntry p;
    
            p = head;
    
            while (p.down != null) {
                p = p.down;
            }
    
            i = 0;
            while (p != null) {
                p.pos = i++;
                p = p.right;
            }
    
            p = head;
            while (p != null) {
                s = getOneRow(p);
                System.out.println(s);
    
                p = p.down;
            }
        }
    
        //用了打印测试
        public String getOneRow(SkipListEntry p) {
            String s;
            int a, b, i;
    
            a = 0;
    
            s = "" + p.key;
            p = p.right;
    
            while (p != null) {
                SkipListEntry q;
    
                q = p;
                while (q.down != null)
                    q = q.down;
                b = q.pos;
    
                s = s + " <-";
    
                for (i = a + 1; i < b; i++)
                    s = s + "--------";
    
                s = s + "> " + p.key;
    
                a = b;
    
                p = p.right;
            }
    
            return (s);
        }
    
        //用了打印测试
        public void printVertical() {
            String s = "";
            SkipListEntry p;
            p = head;
            while (p.down != null)
                p = p.down;
    
            while (p != null) {
                s = getOneColumn(p);
                System.out.println(s);
    
                p = p.right;
            }
        }
        //用了打印测试
        public String getOneColumn(SkipListEntry p) {
            String s = "";
            while (p != null) {
                s = s + " " + p.key;
                p = p.up;
            }
            return (s);
        }
    }

3 测试类，Test.java

package skiplist;
    
    public class Test {
        public static void main(String[] args) {
            SkipList S = new SkipList();
    
            S.printHorizontal();
            System.out.println("------");
            // S.printVertical();
            // System.out.println("======");
    
            S.put("ABC", 123);
            S.printHorizontal();
            System.out.println("------");
            // S.printVertical();
             //System.out.println("======");
    
            S.put("DEF", 123);
            S.printHorizontal();
            System.out.println("------");
            // S.printVertical();
            // System.out.println("======");
    
            S.put("KLM", 123);
            S.printHorizontal();
            System.out.println("------");
            // S.printVertical();
            // System.out.println("======");
    
            S.put("HIJ", 123);
            S.printHorizontal();
            System.out.println("------");
            // S.printVertical();
            // System.out.println("======");
    
            S.put("GHJ", 123);
            S.printHorizontal();
            System.out.println("------");
            // S.printVertical();
            // System.out.println("======");
    
            S.put("AAA", 123);
            S.printHorizontal();
            System.out.println("------");
            // S.printVertical();
            // System.out.println("======");
    
        }
    }

输出结果

-oo <-> +oo ------
    -oo <-> ABC <-> +oo ------
    -oo <-> ABC <-> DEF <-> +oo ------
    -oo <-----------------> KLM <-> +oo
    -oo <-> ABC <-> DEF <-> KLM <-> +oo ------
    -oo <-----------------> HIJ <---------> +oo
    -oo <-----------------> HIJ <---------> +oo
    -oo <-----------------> HIJ <---------> +oo
    -oo <-----------------> HIJ <-> KLM <-> +oo
    -oo <-> ABC <-> DEF <-> HIJ <-> KLM <-> +oo ------
    -oo <-------------------------> HIJ <---------> +oo
    -oo <-------------------------> HIJ <---------> +oo
    -oo <-----------------> GHJ <-> HIJ <---------> +oo
    -oo <-----------------> GHJ <-> HIJ <-> KLM <-> +oo
    -oo <-> ABC <-> DEF <-> GHJ <-> HIJ <-> KLM <-> +oo ------
    -oo <---------------------------------> HIJ <---------> +oo
    -oo <---------------------------------> HIJ <---------> +oo
    -oo <-------------------------> GHJ <-> HIJ <---------> +oo
    -oo <-------------------------> GHJ <-> HIJ <-> KLM <-> +oo
    -oo <-> AAA <-> ABC <-> DEF <-> GHJ <-> HIJ <-> KLM <-> +oo ------

[http_www.mathcs.emory.edu_cheung_Courses_323_Syllabus_Map_skip-list-impl.html]: http://www.mathcs.emory.edu/~cheung/Courses/323/Syllabus/Map/skip-list-impl.html
[http_www.acmerblog.com_skip-list-impl-java-5773.html]: http://www.acmerblog.com/skip-list-impl-java-5773.html
[20160229112003562]: /images/20220731/4f5048bb06a9419dacfe558599fb841a.png