当前位置：首页 > PHP

跳表实现原理 php

2026-02-15 06:49:40PHP

跳表（Skip List）实现原理

跳表是一种概率性的数据结构，允许快速查找、插入和删除操作，时间复杂度为O(log n)。它通过多层链表实现，每一层都是下一层的子集。

跳表的基本结构

跳表由多个层级组成，最底层包含所有元素，每一上层都是下一层的子集。每个节点包含一个值和多个指向不同层级下一个节点的指针。

PHP实现跳表的关键步骤

定义节点类

class SkipListNode {
    public $value;
    public $forward = [];

    public function __construct($value, $level) {
        $this->value = $value;
        $this->forward = array_fill(0, $level + 1, null);
    }
}

初始化跳表

class SkipList {
    private $maxLevel;
    private $level;
    private $header;

    public function __construct($maxLevel = 16) {
        $this->maxLevel = $maxLevel;
        $this->level = 0;
        $this->header = new SkipListNode(null, $maxLevel);
    }
}

随机层级生成

private function randomLevel() {
    $level = 0;
    while (mt_rand(0, 1) && $level < $this->maxLevel - 1) {
        $level++;
    }
    return $level;
}

插入操作

public function insert($value) {
    $update = array_fill(0, $this->maxLevel, null);
    $current = $this->header;

    for ($i = $this->level; $i >= 0; $i--) {
        while ($current->forward[$i] !== null && $current->forward[$i]->value < $value) {
            $current = $current->forward[$i];
        }
        $update[$i] = $current;
    }

    $current = $current->forward[0];
    if ($current === null || $current->value !== $value) {
        $newLevel = $this->randomLevel();
        if ($newLevel > $this->level) {
            for ($i = $this->level + 1; $i <= $newLevel; $i++) {
                $update[$i] = $this->header;
            }
            $this->level = $newLevel;
        }

        $newNode = new SkipListNode($value, $newLevel);
        for ($i = 0; $i <= $newLevel; $i++) {
            $newNode->forward[$i] = $update[$i]->forward[$i];
            $update[$i]->forward[$i] = $newNode;
        }
    }
}

查找操作

public function search($value) {
    $current = $this->header;

    for ($i = $this->level; $i >= 0; $i--) {
        while ($current->forward[$i] !== null && $current->forward[$i]->value < $value) {
            $current = $current->forward[$i];
        }
    }

    $current = $current->forward[0];
    return $current !== null && $current->value === $value;
}

删除操作

public function delete($value) {
    $update = array_fill(0, $this->maxLevel, null);
    $current = $this->header;

    for ($i = $this->level; $i >= 0; $i--) {
        while ($current->forward[$i] !== null && $current->forward[$i]->value < $value) {
            $current = $current->forward[$i];
        }
        $update[$i] = $current;
    }

    $current = $current->forward[0];
    if ($current !== null && $current->value === $value) {
        for ($i = 0; $i <= $this->level; $i++) {
            if ($update[$i]->forward[$i] !== $current) {
                break;
            }
            $update[$i]->forward[$i] = $current->forward[$i];
        }

        while ($this->level > 0 && $this->header->forward[$this->level] === null) {
            $this->level--;
        }
        return true;
    }
    return false;
}