摘要：跳表全稱叫做跳躍表，簡稱跳表。跳表在原有的有序鏈表上面增加了多級索引，通過索引來實現(xiàn)快速查找。跳表不僅能提高搜索性能，同時也可以提高插入和刪除操作的性能。每個節(jié)點包含兩個指針，一個指向同一鏈表中的下一個元素，一個指向下面一層的元素。

增加了向前指針的鏈表叫作跳表。跳表全稱叫做跳躍表，簡稱跳表。跳表是一個隨機化的數(shù)據(jù)結(jié)構(gòu)，實質(zhì)就是一種可以進行二分查找的有序鏈表。跳表在原有的有序鏈表上面增加了多級索引，通過索引來實現(xiàn)快速查找。跳表不僅能提高搜索性能，同時也可以提高插入和刪除操作的性能。

1.由很多層結(jié)構(gòu)組成
2.每一層都是一個有序的鏈表
3.最底層(第一層)的鏈表包含所有元素
4.如果一個元素出現(xiàn)在 第 i 層 的鏈表中，則它在第 i 層 之下的鏈表也都會出現(xiàn)。
5.每個節(jié)點包含兩個指針，一個指向同一鏈表中的下一個元素，一個指向下面一層的元素。

栗子：查找元素 6
1.頭指針最開始在第一層最小值INT_MIN處
2.于是和旁邊的1比較,當然了1大嘛,于是指針移向1
3.再和當前層4比較， 比 4 大，跳到4
4.與7比較,比7小,于是向下跳到第二層4
5..與5比較,比5大,跳到5
6.與7比較,比7小,跳到最低層5
7.只能依次向后比較了,于是找到了6

1.節(jié)點定義,共三個成員變量:value,right,down

package crabapple;

/*
 * Copyright (c) This is zhaoxubin"s Java program.
 * Copyright belongs to the crabapple organization.
 * The crabapple organization has all rights to this program.
 * No individual or organization can refer to or reproduce this program without permission.
 * If you need to reprint or quote, please post it to zhaoxubin2016@live.com.
 * You will get a reply within a week,
 *
 */

import java.util.Random;

/**
 * 節(jié)點類定義
 */
class Node {

    //值
    public int value = 0;

    //當前層下一個節(jié)點
    public Node right;

    //下一層,直連的節(jié)點
    public Node down;

    //構(gòu)造函數(shù)
    public Node() {

    }

    public Node(int value) {
        this.value = value;
    }
}

2.跳表類 定義,大家可以清晰的看請代碼邏輯結(jié)構(gòu),該類只暴露insert()和search()兩個方法,其它變量及方法均設(shè)為私有.

/**
 * 跳表定義
 */
public class SkipTable {

    //表層數(shù)
    private int levelCount;
    
    //表的頭指針
    private Node firstNode;

    //初始化:層數(shù)為1,共前后兩個節(jié)點,一個最小值,一個最大值
    private void init() {
        levelCount = 1;
        firstNode=new Node();
        firstNode.value = Integer.MIN_VALUE;
        firstNode.right = new Node(Integer.MAX_VALUE);
    }

    public SkipTable() {
        init();
    }

    /**
     * 查找值
     * @param value
     * @return
     */
    public boolean search(int value) {

        Node current = firstNode;
        return toSearch(current, value);
    }

    private boolean toSearch(Node node, int value) {
        if (node.value == value)
            return true;
        else if (node.right!=null&&value >= node.right.value)
            return toSearch(node.right, value);
        else if (node.down != null)
            return toSearch(node.down, value);
        return false;
    }

    
    
    /**
     * 插入值
     * @param value
     * @return
     */
    public boolean insert(int value) {

        //判斷是否有這個元素
        if (search(value))
            return false;

        //隨機獲取一個層數(shù)
        int willLevel = updateLevelCount();

        //判斷是否添加新層
        if (willLevel > levelCount) {
            Node newFirstNode = new Node();
            addLevel(firstNode, newFirstNode);
            firstNode=newFirstNode;
            levelCount = willLevel;
        }

        //插入新元素
        Node port = firstNode;
        int skipLevel = levelCount - willLevel;

        //迭代到指定層
        while ((skipLevel--) > 0)
            port = port.down;

        //上下層新節(jié)點的橋梁
        Node insertNode = null;

        while (port != null) {

            //獲取當前層第一個節(jié)點指針
            Node curPort = port;

            //迭代到右邊的節(jié)點值比自己大為止
            while (port.right.value < value)
                port = port.right;

            //準備插入的新節(jié)點
            Node curInNode = new Node(value);

            //更新當前節(jié)點和前節(jié)點指針指向
            curInNode.right = port.right;
            port.right = curInNode;

            //將當前節(jié)點引用給上層節(jié)點
            if (insertNode != null)
                insertNode.down = curInNode;

            //將新插入的節(jié)點指針更新到insertNode,以備在下一層建立指向
            insertNode = curInNode;

            //行頭指針向下迭代
            port = port.down;
        }
        return true;

    }

    /**
     * 添加新層
     *
     * @param oldFirst
     * @param newFirst
     */
    private void addLevel(Node oldFirst, Node newFirst) {

        newFirst.value = oldFirst.value;
        newFirst.down = oldFirst;
        if (oldFirst.right != null) {
            Node newRightNode = new Node();
            newFirst.right = newRightNode;
            addLevel(oldFirst.right, newRightNode);
        }
    }

    /**
     * 以一定概率使得獲取一個和老層數(shù)差值不超過1的新層數(shù)
     * @return
     */
    private int updateLevelCount() {

        Random random=new Random();
        int v = random.nextInt(10);
        return v ==0 ? random.nextInt(levelCount) + 2 : random.nextInt(levelCount)+1 ;
    }
}

3.測試類

package crabapple;


public class Main {
    
    public static void main(String[] args) {
        //測試
        SkipTable skipTable=new SkipTable();
        skipTable.insert(1);
        skipTable.insert(2);
        skipTable.insert(3);
        skipTable.insert(4);
        skipTable.insert(5);
        skipTable.insert(6);
        skipTable.insert(7);
        skipTable.insert(8);
        skipTable.insert(9);
        skipTable.insert(10);

        //健壯性邊界值測試
        System.out.println(skipTable.search(0));
        System.out.println(skipTable.search(1));
        System.out.println(skipTable.search(2));
        System.out.println(skipTable.search(5));
        System.out.println(skipTable.search(9));
        System.out.println(skipTable.search(10));
        System.out.println(skipTable.search(11));
    }
}

//output:
/**
 * false
 * true
 * true
 * true
 * true
 * true
 * false
 *
 * Process finished with exit code 0
 */

上面的代碼,大家是可以直接運行,筆者能力有限,代碼也許還有不足,望大家多多指教.