数据结构和内存分配 - redis-skiplist - 《开发笔记》

跳跃表结构
Java实现跳跃表

跳跃表结构

//跳跃表节点
typedef struct zskiplistNode {
    sds ele;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned long span;
    } level[];
} zskiplistNode;
//跳跃表
typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;
    int level;
} zskiplist;

跳跃表的插入

zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) {
    //存储插入节点
    zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
    //存储span
    unsigned int rank[ZSKIPLIST_MAXLEVEL];
    int i, level;
    serverAssert(!isnan(score));
    x = zsl->header;
    //找到forward节点
    for (i = zsl->level-1; i >= 0; i--) {
        /* store rank that is crossed to reach the insert position */
        rank[i] = i == (zsl->level-1) ? 0 : rank[i+1];
        while (x->level[i].forward && (x->level[i].forward->score < score || (x->level[i].forward->score == score && sdscmp(x->level[i].forward->ele,ele) < 0)))
        {
            rank[i] += x->level[i].span;
            x = x->level[i].forward;
        }
        update[i] = x;
    }
    //随机生成level==> (生成的level: 2, 当前的level: 1)
    level = zslRandomLevel();
    //生成的level大于跳跃表当前的level
    if (level > zsl->level) {
        //1-->2, 新生成的level直接指向null，span为跳跃表的长度
        for (i = zsl->level; i < level; i++) {
            rank[i] = 0;
            update[i] = zsl->header;
            update[i]->level[i].span = zsl->length;
        }
        zsl->level = level;
    }
    //创建跳跃表节点
    x = zslCreateNode(level,score,ele);
    //从最底层一直处理到最高层
    for (i = 0; i < level; i++) {
        //原来 a-->b
        //现在 a-->c-->b
        //a = update[i]->level[i]--> b=update[i]->level[i].forward
        //处理链表的逻辑，只不过切换成了多层链表 层=level[i].forward==next指针
        x->level[i].forward = update[i]->level[i].forward;
        update[i]->level[i].forward = x;
        /* update span covered by update[i] as x is inserted here */
        x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]);
        update[i]->level[i].span = (rank[0] - rank[i]) + 1;
    }
    /* increment span for untouched levels */
    for (i = level; i < zsl->level; i++) {
        update[i]->level[i].span++;
    }
    x->backward = (update[0] == zsl->header) ? NULL : update[0];
    if (x->level[0].forward)
        x->level[0].forward->backward = x;
    else
        zsl->tail = x;
    zsl->length++;
    return x;
}

Java实现跳跃表

package io.github.chenshun00.data.list;
import java.util.Arrays;
/**
 * <ul>
 *     <li>1、一个跳表应该有几个层组成，第一层包含所有的元素</li>
 *     <li>2、每一层都是有序链表</li>
 *     <li>3、如果元素x出现在第i层，则所有比i小的层都包含x</li>
 *     <li>4、第i层的元素通过一个down指针指向下一层拥有相同值的元素</li>
 * </ul>
 *
 * @author chenshun00@gmail.com
 * @since 2022/2/12 3:37 下午
 */
public class SkipList<E> {
    private static final double p = 0.25D;
    int MAX_LEVEL = 32;
    /**
     * 跳表实际层数
     */
    int level;
    /**
     * 跳表头节点
     */
    SkipListNode<E> header;
    /**
     * 创建节点
     *
     * @param level 节点所在层数
     * @param key   节点key
     * @param value 节点value
     * @return {@link SkipListNode<E>}
     */
    private SkipListNode<E> createNode(int level, int key, E value) {
        return new SkipListNode<E>(key, value, level);
    }
    /**
     * 初始化跳跃表
     * 1、初始化level为1级
     * 2、填充header的的next指针为null
     */
    public SkipList() {
        this.level = 0;
        this.header = createNode(MAX_LEVEL, Integer.MIN_VALUE, null);
        for (int i = 0; i < MAX_LEVEL; i++) {
            this.header.forwards[i] = null;
        }
    }
    /**
     * 添加节点到跳跃表
     *
     * @param key   ke3y
     * @param value value
     */
    public void add(int key, E value) {
        final int randomLevel = getRandomLevel();
        final SkipListNode<E> node = createNode(randomLevel, key, value);
        //从高层开始向底层遍历，为每一层补充节点信息，操作方式同链表
        for (int i = level - 1; i >= 0; i--) {
            SkipListNode<E> closable = header;
            //找到这一层的下一个节点
            while (closable.forwards[i] != null) {
                if (key == closable.forwards[i].key) {
                    closable.forwards[i].value = value;
                    return;
                } else if (key > closable.forwards[i].key) {
                    closable = closable.forwards[i];
                } else {
                    break;
                }
            }
            if (randomLevel > i) {
                if (closable.forwards[i] == null) {
                    closable.forwards[i] = node;
                } else {
                    final SkipListNode<E> next = closable.forwards[i];
                    closable.forwards[i] = node;
                    node.forwards[i] = next;
                }
            }
        }
        if (randomLevel > level) { //如果随机出来的层数比当前的层数还大，那么超过currentLevel的head 直接指向newNode
            for (int i = level; i < randomLevel; i++) {
                header.forwards[i] = node;
            }
            this.level = randomLevel;
        }
    }
    public E get(int key) {
        SkipListNode<E> closable = header;
        for (int i = level - 1; i >= 0; i--) {
            //找到这一层的下一个节点
            while (closable.forwards[i] != null) {
                if (key == closable.forwards[i].key) {
                    return closable.forwards[i].value;
                } else if (key > closable.forwards[i].key) {
                    closable = closable.forwards[i];
                } else {
                    break;
                }
            }
            if (closable.forwards[i] != null && closable.forwards[i].key == key) {
                return closable.forwards[i].value;
            }
        }
        return null;
    }
    public void remove(int key) {
        SkipListNode<E> closable = header;
        for (int i = level - 1; i >= 0; i--) {
            //找到这一层的下一个节点
            while (closable.forwards[i] != null) {
                if (key > closable.forwards[i].key) {
                    closable = closable.forwards[i];
                } else {
                    break;
                }
            }
            if (closable.forwards[i] != null && closable.forwards[i].key == key) {
                final SkipListNode<E> current = closable.forwards[i];
                final SkipListNode<E> next = current.forwards[i];
                closable.forwards[i] = next;
            }
        }
    }
    public void printList() {
        for (int i = level - 1; i >= 0; i--) {
            SkipListNode<E> curNode = this.header.forwards[i];
            System.out.print("HEAD->");
            while (curNode != null) {
                String line = String.format("(%s,%s)->", curNode.key, curNode.value);
                System.out.print(line);
                curNode = curNode.forwards[i];
            }
            System.out.println("NIL");
        }
    }
    private int getRandomLevel() {
        int lvl = 1;
        //Math.random() 返回一个介于 [0,1) 之间的数字
        while (lvl < MAX_LEVEL && Math.random() < p) {
            lvl++;
        }
        return lvl;
    }
    private static class SkipListNode<E> {
        /**
         * key 信息
         * <p>
         * 这个是什么？index 吗？
         */
        int key;
        /**
         * 存放的元素
         */
        E value;
        /**
         * 向前的指针
         * <p>
         * 跳表是多层的，这个向前的指针，最多和层数一样。
         *
         * @since 0.0.4
         */
        SkipListNode<E>[] forwards;
        @SuppressWarnings("all")
        public SkipListNode(int key, E value, int level) {
            this.key = key;
            this.value = value;
            this.forwards = new SkipListNode[level];
        }
        @Override
        public String toString() {
            return "SkipListNode{" +
                    "key=" + key +
                    ", value=" + value +
                    ", forwards=" + Arrays.toString(forwards) +
                    '}';
        }
    }
}