太刺激了，面试官让我手写跳表，而我用两种实现方式吊打了TA

前言

本文，我将通过两种方式手写跳表，并结合画图，彻底搞定跳表实现的细节。

第一种方式为跳表的通用实现，第二种方式为彤哥自己发明的实现，并运用到HashMap的改写中。

好了，开始今天的学习吧，Let’s Go！

文末有跳表和红黑树实现的HashMap的对比，不想看代码的同学也可以直达底部。

通用实现

通用实现主要参考JDK中的ConcurrentSkipListMap，在其基础上，简化，并优化一些东西，学好通用实现也有助于理解JDK中的ConcurrentSkipListMap的源码。

数据结构

首先，我们要定义好实现跳表的数据结构，在通用实现中，将跳表的数据结构分成三种：

• 普通节点，处于0层的节点，存储数据，典型的单链表结构，包括h0
• 索引节点，包含着对普通节点的引用，同时增加向右、向下的指针
• 头索引节点，继承自索引节点，同时，增加所在的层级

类图大概是这样：

OK，给出代码如下：

/**
  * 头节点：标记层  * @param <T>
  */private static class HeadIndex<T> extends Index<T> {
    // 层级    int level;    public HeadIndex(Node<T> node, Index<T> down, Index<T> right, int level) {
        super(node, down, right);        this.level = level;    }}/**  * 索引节点：引用着真实节点  * @param <T>
  */private static class Index<T> {
    // 真实节点    Node<T> node;
    // 下指针（第一层的索引实际上是没有下指针的）    Index<T> down;
    // 右指针    Index<T> right;
    public Index(Node<T> node, Index<T> down, Index<T> right) {
        this.node = node;        this.down = down;        this.right = right;    }}/**  * 链表中的节点：真正存数据的节点  * @param <T>
  */static class Node<T> {
    // 节点元素值    T value;    // 下一个节点    Node<T> next;
    public Node(T value, Node<T> next) {
        this.value = value;        this.next = next;    }    @Override    public String toString() {        return (value==null?"h0":value.toString()) +"->" + (next==null?"null":next.toString());    }}

查找元素

查找元素，是通过头节点，先尽最大努力往右，再往下，再往右，每一层都要尽最大努力往右，直到右边的索引比目标值大为止，到达0层的时候再按照链表的方式来遍历，用图来表示如下：

所以，整个过程分成两大步：

1. 寻找目标节点前面最接近的索引对应的节点；
2. 按链表的方式往后遍历；

请注意这里的指针，在索引中叫作right，在链表中叫作next，是不一样的。

这样一分析代码实现起来就比较清晰了：

/**
  * 查找元素  * 先找到前置索引节点，再往后查找  * @param value  * @return  */
public T get(T value) {
    System.out.println("查询元素：\u6b22\u8fce\u5173\u6ce8\u516c\u4f17\u53f7\u5f64\u54e5\u8bfb\u6e90\u7801\uff0c\u83b7\u53d6\u66f4\u591a\u67b6\u6784\u3001\u57fa\u7840\u3001\u6e90\u7801\u597d\u6587\uff01");
    if (value == null) {
        throw new NullPointerException();
    }
    Comparator<T> cmp = this.comparator;
    // 第一大步：先找到前置的索引节点
    Node<T> preIndexNode = findPreIndexNode(value, true);
    // 如果要查找的值正好是索引节点
    if (preIndexNode.value != null && cmp.compare(preIndexNode.value, value) == 0) {
        return value;
    }
    // 第二大步：再按链表的方式查找
    Node<T> q;
    Node<T> n;
    int c;
    for (q = preIndexNode;;) {
        n = q.next;
        c = cmp.compare(n.value, value);
        // 找到了
        if (c == 0) {
            return value;
        }
        // 没找到
        if (c > 0) {
            return null;
        }
        // 看看下一个
        q = n;
    }
}
/**
  *  * @param value 要查找的值  * @param contain 是否包含value的索引  * @return  */
private Node<T> findPreIndexNode(T value, boolean contain) {
    /*
         * q---->r---->r         * |     |
         * |     |
         * v     v         * d     d         * q = query         * r = right         * d = down         */
    // 从头节点开始查找，规律是先往右再往下，再往右再往下
    Index<T> q = this.head;
    Index<T> r, d;
    Comparator<T> cmp = this.comparator;
    for(;;) {
        r = q.right;
        if (r != null) {