太刺激了，面试官让我手写跳表，而我用两种实现措施吊打了TA！
发布时间：2021-06-04 17:29:34 所属栏目：大数据 来源：互联网
导读：通用实现 通用实现主要参考JDK中的ConcurrentSkipListMap，在其基础上，简化，并优化一些东西，学好通用实现也有助于理解JDK中的ConcurrentSkipListMap的源码。 数据结构 首先，我们要定义好实现跳表的数据结构，在通用实现中，将跳表的数据结构分成三种：
|
通用实现
通用实现主要参考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层的时候再按照链表的方式来遍历，用图来表示如下：
所以，整个过程分成两大步：
寻找目标节点前面最接近的索引对应的节点;
按链表的方式往后遍历;
请注意这里的指针，在索引中叫作right，在链表中叫作next，是不一样的。
这样一分析代码实现起来就比较清晰了：
/**
* 查找元素
* 先找到前置索引节点，再往后查找
* @param value
* @return
*/
public T get(T value) {
System.out.println("查询元素：u6b22u8fceu5173u6ce8u516cu4f17u53f7u5f64u54e5u8bfbu6e90u7801uff0cu83b7u53d6u66f4u591au67b6u6784u3001u57fau7840u3001u6e90u7801u597du6587uff01");
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) {
// 包含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;
}
}
 （编辑：保山站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
