skiplist

跳跃表：是基于链表来是实现的。

我们可以先看看单链表的数据的结构。如下图

在这样一个链表中，如果我们要查找某个数据，那么需要从头开始逐个进行比较，直到找到包含数据的那个节点，或者找到第一个比给定数据大的节点为止（没找到）。也就是说，时间复杂度为O(n)。同样，当我们要插入新数据的时候，也要经历同样的查找过程，从而确定插入位置。假如我们每相邻两个节点增加一个指针，让指针指向下下个节点，如下图：

这样所有新增加的指针连成了一个新的链表，但它包含的节点个数只有原来的一半（上图中是7, 19, 26）。现在当我们想查找数据的时候，可以先沿着这个新链表进行查找。当碰到比待查数据大的节点时，再回到原来的链表中进行查找。比如，我们想查找23，查找的路径是沿着下图中标红的指针所指向的方向进行的：

23首先和7比较，再和19比较，比它们都大，继续向后比较。
但23和26比较的时候，比26要小，因此回到下面的链表（原链表），与22比较。
23比22要大，沿下面的指针继续向后和26比较。23比26小，说明待查数据23在原链表中不存在，而且它的插入位置应该在22和26之间。
在这个查找过程中，由于新增加的指针，我们不再需要与链表中每个节点逐个进行比较了。需要比较的节点数大概只有原来的一半。

skiplist正是受这种多层链表的想法的启发而设计出来的。实际上，按照上面生成链表的方式，上面每一层链表的节点个数，是下面一层的节点个数的一半，这样查找过程就非常类似于一个二分查找，使得查找的时间复杂度可以降低到O(log n)。但是，这种方法在插入数据的时候有很大的问题。新插入一个节点之后，就会打乱上下相邻两层链表上节点个数严格的2:1的对应关系。如果要维持这种对应关系，就必须把新插入的节点后面的所有节点（也包括新插入的节点）重新进行调整，这会让时间复杂度重新蜕化成O(n)。删除数据也有同样的问题。

skiplist为了避免这一问题，它不要求上下相邻两层链表之间的节点个数有严格的对应关系，而是为每个节点随机出一个层数(level)。比如，一个节点随机出的层数是3，那么就把它链入到第1层到第3层这三层链表中。为了表达清楚，下图展示了如何通过一步步的插入操作从而形成一个skiplist的过程：

从上面skiplist的创建和插入过程可以看出，每一个节点的层数（level）是随机出来的，而且新插入一个节点不会影响其它节点的层数。因此，插入操作只需要修改插入节点前后的指针，而不需要对很多节点都进行调整。这就降低了插入操作的复杂度。实际上，这是skiplist的一个很重要的特性，这让它在插入性能上明显优于平衡树的方案。这在后面我们还会提到。

根据上图中的skiplist结构，我们很容易理解这种数据结构的名字的由来。skiplist，翻译成中文，可以翻译成“跳表”或“跳跃表”，指的就是除了最下面第1层链表之外，它会产生若干层稀疏的链表，这些链表里面的指针故意跳过了一些节点（而且越高层的链表跳过的节点越多）。这就使得我们在查找数据的时候能够先在高层的链表中进行查找，然后逐层降低，最终降到第1层链表来精确地确定数据位置。在这个过程中，我们跳过了一些节点，从而也就加快了查找速度。

下面是使用PHP实现的跳跃表的一个例子

<?php
/**
 * 跳跃表
 * Head nodes          Index nodes
 * +-+    right        +-+                      +-+
 * |2|---------------->| |--------------------->| |->null
 * +-+                 +-+                      +-+
 *  | down              |                        |
 *  v                   v                        v
 * +-+            +-+  +-+       +-+            +-+       +-+
 * |1|----------->| |->| |------>| |----------->| |------>| |->null
 * +-+            +-+  +-+       +-+            +-+       +-+
 *  v              |    |         |              |         |
 * Nodes  next     v    v         v              v         v
 * +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+
 * | |->|A|->|B|->|C|->|D|->|E|->|F|->|G|->|H|->|I|->|J|->|K|->null
 * +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+  +-+
 */

class Node
{
    /**
     * @var Node
     */
    public $nextNode; //指向下一个节点

    /**
     * 索引值
     * @var int
     */
    public $score;

    /**
     * @var mixed
     */
    public $data;

    public function __construct($score)
    {
        $this->score = $score;
    }

    public function setData($val)
    {
        $this->data = $val;
    }
}

class IndexNode extends Node
{
    /**
     * @var IndexNode|Node
     */
    public $downNode = null;

    /**
     * @var int 当前的层数
     */
   // public $level = 0;


}


class SkipList
{
    /**
     * 跳跃表层高
     * @var int
     */
    public $level = 1;

    /**
     * 最高层头结点
     * @var IndexNode
     */
    public $head = null;

    CONST SKIPLIST_P = 0.5;
    /**
     * 最大层数
     */
    const MAX_LEVEL  = 16;

    /**
     * SkipList constructor.
     */
    public function __construct()
    {
        $this->head = new IndexNode(null);
    }

    /**
     *
     *理论来讲，一级索引中元素个数应该占原始数据的 50%，二级索引中元素个数占 25%，三级索引12.5% ，一直到最顶层。
     * 因为这里每一层的晋升概率是 50%。对于每一个新插入的节点，都需要调用 randomLevel 生成一个合理的层数。
     *该 randomLevel 方法会随机生成 1~MAX_LEVEL 之间的数，且 ：
     *50%的概率返回 1
     *25%的概率返回 2
     *12.5%的概率返回 3 ...
     *
     */
    public function randomLevel()
    {
        $level = 0;
        while (lcg_value() < self::SKIPLIST_P && $level < self::MAX_LEVEL) {
            $level++;
        }
        return $level;
    }

    /**
     * @param $score
     * @return Node|null
     */
    public function findEntry($score)
    {
        /**
         * @var Node|IndexNode $list
         */
        /**
         * @var Node|IndexNode $list
         */
        $list = $this->head;
        while ($list) {
            while ($list->nextNode && $list->nextNode->score < $score) {
                $list = $list->nextNode;
            }
            if (isset($list->downNode) && !empty($list->downNode)) {
                $list = $list->downNode;
            } else {
                break;
            }
        }
        return $list;
    }

    /**
     * @param $score
     * @return Node|null
     */
    public function findEntry2($score)
    {
        /**
         * @var Node|IndexNode $list
         */
        $list = $this->head;
        while ($list) {
            while ($list->nextNode && $list->nextNode->score < $score) {
                $list = $list->nextNode;
                echo '::'.$list->score.'::'.PHP_EOL;
            }
            if (isset($list->downNode) && !empty($list->downNode)) {
                $list = $list->downNode;
            } else {
                break;
            }
        }
        return $list;

    }

    /**
     * 获取值
     * @param $score
     * @return Node|null
     */
    public function get($score)
    {
        $node = $this->findEntry($score);

        if ($node->nextNode && $node->nextNode->score == $score) {
            return $node->nextNode;
        }
        return null;
    }

    public function addNode($score,$val)
    {
        $node = new Node($score);
        $node->setData($val);

        $entryNode = $this->findEntry($score);
        if ($entryNode && $entryNode->score == $score && $entryNode->data == $val) {
            return;
        }

        $node->nextNode      = $entryNode->nextNode;
        $entryNode->nextNode = $node;

        $head = $down = $this->head;
        /**
         * @var IndexNode|Node $newIndex
         */
        $newIndex = null;
        //因为不是双向链接指定，所以要在当前层，往下一层一层添加 索引节点
        for ($i = $this->level; $i>=1;$i--) {
            while ($down->nextNode && $down->nextNode->score < $score) {
                $down = $down->nextNode;
            }
            if ($down->nextNode && $down->nextNode->score == $score) {
                if ($newIndex) {
                    $newIndex->downNode = $down->nextNode;
                }
                continue;
            } else {
                $upNewIndex = $newIndex ? $newIndex : null;
                $newIndex = new IndexNode($score);
                $newIndex->nextNode = $down->nextNode;
                $down->nextNode = $newIndex;
                if ($upNewIndex) {
                    $upNewIndex->downNode = $newIndex;
                }
            }
            $down = $head->downNode;
            $head = $head->downNode;
        }

        $level = $this->randomLevel();
        //因为层数大于当前层，所以要在当前层，往上一层一层添加 索引节点，并建立索引节点的上下关系
        $up = $this->head;
        for ($i = $this->level+1;$i<= $level;$i++) {
            $downUp       = $up ?? null;
            $up           = new IndexNode(null);
            $newIndex     = new IndexNode($score);
            $up->nextNode = $newIndex;
            if ($downUp) {
                $up->downNode = $downUp;
            }
            while ($downUp->nextNode && $downUp->nextNode->score < $score) {
                $downUp = $downUp->nextNode;
            }
            if ($down->nextNode->score == $score) {
                $newIndex->downNode = $down->nextNode;
                continue;
            }
        }

        $this->head = $up;
        $this->level = $this->level < $level ? $level:$this->level;
    }


    /**
     * 打印跳跃表
     */
    public function prinSkipList()
    {
        $down = $node = $this->head;
        while ($down) {
            $str = '';
            while ($node) {
                $str .= '['.$node->score.']['.(isset($node->downNode) ? $node->downNode->score : null).']['.(isset($node->nextNode) ? $node->nextNode->score : null).']--';
                $node = $node->nextNode;
            }
            echo $str.PHP_EOL;
            $down = $node = $down->downNode;
        }
    }

    /**
     * @param $score
     * @return bool
     */
    public function del($score)
    {
        $node = $this->get($score);
        if (empty($node)) {
            return true;
        }

        $head = $down = $this->head;
        for ($i = $this->level;$i>=1;$i--) {
            $nodeNum = 1;
            $levelNode = $down;
            while ($down->nextNode && $down->nextNode->score < $score) {
                $nodeNum++;
                $down = $down->nextNode;
            }
            if ($down->nextNode && $down->nextNode->score == $score) {
                $down->nextNode = $down->nextNode->nextNode;
                if ($nodeNum <= 2 && !$down->nextNode) {
                    $this->level = $this->level > 1 ? ($this->level - 1) : $this->level;
                    $head = $head->downNode ? $head->downNode : $head;
                }
            }
            $down = $levelNode->downNode ? $levelNode->downNode : $levelNode;
        }
        $this->head = $head;
    }

}

/**
 * Test 1
 */
$skipList = new SkipList();
$skipList->addNode(5,'5');
$skipList->addNode(8,'8');
$skipList->addNode(6,'6');
$skipList->addNode(7,'7');
$skipList->addNode(3,'3');
$skipList->addNode(2,'2');
$skipList->addNode(1,'1');
$skipList->addNode(0,'0');
$skipList->prinSkipList();
echo "-------------------------".PHP_EOL;

/**
 * Test 2
 */
$skipList = new SkipList();
$head2 = new IndexNode(null);
$head1 = new IndexNode(null);

$head2->downNode = $head1;



$data1 = new Node(1);
$data1->setData('1');
$index1 = new IndexNode(1);
$index1->downNode = $data1;

$index2 = new IndexNode(2);
$data2 = new Node(2);
$data2->setData('2');

$index2->downNode = $data2;
$index1->nextNode = $index2;

$data1->nextNode = $data2;


$data3 = new Node(3);
$data3->setData('3');
$data2->nextNode = $data3;

$data4 = new Node(4);
$data4->setData('4');
$data3->nextNode = $data4;


$head1->nextNode = $data1;
$head2->nextNode = $index1;

$head3 = new IndexNode(null);
$head3->downNode = $head2;
$head3->nextNode = new IndexNode(1);
$head3->nextNode->downNode = $index1;

$skipList->head  = $head3;
$skipList->level = 3;
$skipList->prinSkipList();
$skipList->del(1);
echo "-------------------------".PHP_EOL;
$skipList->prinSkipList();
echo "-------------------------".PHP_EOL;
$skipList->addNode(6,'6');
$skipList->prinSkipList();
//$node = $skipList->get(7);
//var_dump($node->score);