面试题之跳表

概述

本文主要讲解跳表的原理、代码实现以及常见的面试题。
跳表本质上是一种查找结构，相比于平衡树，不仅实现简单，而且插入、删除、查找的时间复杂度均为O(logN)。跳表其实就是链表，只是对有序的链表增加上附加的前进链接（增加是以随机化的方式进行的），所以在列表中的查找可以快速的跳过部分列表从而快速检索。
由于跳表在Redis的使用，导致面试中经常会被提及，所以深入了解跳表的实现非常必要。

代码实现

第一种实现方法

这种实现方法构建的跳表整体如下图所示：

这种实现方式中的SkipNode定义如下所示。

  private class SkipNode<K, V> {
        private K key;
        private V value;
        private SkipNode<K, V>[] forward;

        public SkipNode( K key, V value, int levels ) {
            this.key = key;
            this.value = value;
            this.forward = (SkipNode<K, V>[]) new SkipNode[levels+1];
            for (int i = 0; i <= levels; i++)
                this.forward[i] = null;
        }
        public K key() { return this.key; }
        public V value() { return this.value; }
        ······
    }

SkipNode定义中需要留意就是forward数组，这个数组的大小是随机的，大小代表这个节点的高度，数组中每个元素代表了这一层的下一个SkipNode。
下面来看insert的代码实现。

    /**
     * 将新值插入到链表中
     * @param k
     * @param newValue
     */
    public void insert(K k, V newValue) {
        int newLevel = randomLevel();
        // 如果随机的层大于现在的最大层, 进行层调整
        if (newLevel > level)
            adjustHead(newLevel);
        this.level = newLevel;
        SkipNode<K, V>[] update = (SkipNode<K, V>[]) new SkipNode[level+1];
        SkipNode<K, V> x = this.head;
        // 找寻每一层的插入位置
        for (int i=level; i>=0; i--) {
            while((x.forward[i] != null) &&
                    ((k.compareTo(x.forward[i].key())) > 0))
                x = x.forward[i];
            update[i] = x;
        }
        // 创建新节点
        x = new SkipNode<K, V>(k, newValue, newLevel);
        // 类似于链表插入
        for (int i=0; i <= newLevel; i++) {
            x.forward[i] = update[i].forward[i];
            update[i].forward[i] = x;
        }
        this.size++;
    }

从上面的代码中可以看出insert主要有几个步骤：

首先随机产生层数,创建新节点
每层遍历，得到新节点在每层插入的前一个节点
逐层插入新节点（类似于链表插入）

下面来看find的代码实现。

    public V find(K searchKey) {
        SkipNode<K, V> x = this.head;
        // 类似于一个下楼梯的过程
        for (int i=level; i>=0; i--)
            while ((x.forward[i] != null) &&
                    (searchKey.compareTo(x.forward[i].key()) > 0))
                x = x.forward[i];
        x = x.forward[0];
        if ((x != null) && (searchKey == x.key()))
            return x.value();
        else return null;
    }

find的过程比较简单，类似于生活中下楼梯，具体过程见上图中的红线所示。

第二种实现方法

这种方式最终创建的跳表如下所示。

SkipListEntry的定义如下。

public class SkipListEntry<K extends Comparable, V> {

    public K key;
    public V value;
    public int pos;
    public SkipListEntry up, down, left, right;

    // 构造函数
    public SkipListEntry(K k, V v) {
        key = k;
        value = v;
        up = down = left = right = null;
    }
}

skipList的初始化操作。定义了头和尾节点，并且把它们相连接。

  public SkipList(){
        SkipListEntry p1, p2;

        p1 = new SkipListEntry<K, V>(null, null);
        p2 = new SkipListEntry<K, V>(null, null);
        head = p1;
        tail = p2;
        p1.right = p2;
        p2.left = p1;
        n = 0;
        h = 0;
        r = new Random();
    }

查找操作如下所示。查找操作依然类似于下楼梯。

     public SkipListEntry<K, V> findEntry(K k) {
        SkipListEntry<K, V> p = head;

        while ( true ) {
            //首先向右走
            while ( p.right.key != null &&
                    p.right.key.compareTo(k) <= 0 ) {
                p = p.right;
            }
            // 向下走
            if ( p.down != null )
            {
                p = p.down;
            }
            else break;    
        }
        return(p);
    }

添加节点的实现如下。

  public Object put (K k, V v)
    {
        SkipListEntry p, q;
        int       i;
        // 待插入的前一个位置
        p = findEntry(k);
        if ( k.equals( p.getKey())) {
            Object old = p.getValue();
            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;                   // Current level = 0
        // 随机插入
        while ( r.nextDouble() < 0.5 )
        {
            // 当前插入的是第i层
            if ( i >= h ) {
                SkipListEntry p1, p2;
                h = h + 1;
                p1 = new SkipListEntry(null,null);
                p2 = new SkipListEntry(null,null);
                p1.right = p2;
                p1.down  = head;
                p2.left = p1;
                p2.down = tail;
                head.up = p1;
                tail.up = p2;
                head = p1;
                tail = p2;
            }

            while ( p.up == null ){
                p = p.left;
            }
            p = p.up;

            SkipListEntry 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;    

            i = i + 1;    

        }
        n = n + 1;
        return null;
    }

和第一种实现方式不同的是，第二种实现方法的插入操作在每一层都需要重新创建节点进行插入，空间浪费。所以推荐第一种实现方法。