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

上一节，我们一起学习了关于跳表的理论知识，相信通过上一节的学习，你一定可以给面试官完完整整地讲清楚跳表的来龙去脉，甚至能够边讲边画图。

然而，面试官说，既然你这么精通跳表，不如实现一个呗^^

我，我，实现就实现，谁怕谁，哼~~

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

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

好了，开始今天的学习吧，Let's Go!

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

通用实现

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

数据结构

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

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

类图大概是这样：

OK，给出代码如下：

友情提示：代码太长，请横屏观赏~~

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

查找元素

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

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

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

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

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

/**   * 查找元素   * 先找到前置索引节点，再往后查找   * @param value   * @return   */ public T get(T value) {     System.out.println("查询元素：u6b22u8fceu5173u6ce8u516cu4f17u53f7u5f64u54e5u8bfbu6e90u7801uff0cu83b7u53d6u66f4u591au67b6u6784u3001u57fau7840u3001u6e90u7801u597du6587uff01");     if (value == null) {         throw new NullPointerException();     }     Comparator cmp = this.comparator;     // 第一大步：先找到前置的索引节点     Node preIndexNode = findPreIndexNode(value, true);     // 如果要查找的值正好是索引节点     if (preIndexNode.value != null && cmp.compare(preIndexNode.value, value) == 0) {         return value;     }     // 第二大步：再按链表的方式查找     Node q;     Node 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 findPreIndexNode(T value, boolean contain) {     /*          * q---->r---->r          * |     |          * |     |          * v     v          * d     d          * q = query          * r = right          * d = down          */     // 从头节点开始查找，规律是先往右再往下，再往右再往下     Index q = this.head;     Index r, d;     Comparator cmp = this.comparator;     for(;;) {         r = q.right;         if (r != null) {             // 包含value的索引，正好有             if (contain && cmp.compare(r.node.value, value) == 0) {                 return r.node;             }             // 如果右边的节点比value小，则右移             if (cmp.compare(r.node.value, value) < 0) {                 q = r;                 continue;             }         }         d = q.down;         // 如果下面的索引为空了，则返回该节点         if (d == null) {             return q.node;         }         // 否则，下移         q = d;     } } 

添加元素

添加元素，相对来说要复杂得多。

首先，添加一个元素时，要先找到这个元素应该插入的位置，并将其添加到链表中;

然后，考虑建立索引，如果需要建立索引，又分成两步：一步是建立竖线(down)，一步是建立横线(right);

（编辑：应用网_阳江站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!