public abstract class SkipListUtil {
/**
* 按照规则生成随机层数，层数越大，概率越低
*
* @return
*/
public static int generateRandomLevel() {
int result = SkipListConfig.MIN_LEVEL;
Random random = new Random();
while (random.nextInt(SkipListConfig.MAX_LEVEL) < SkipListConfig.MAX_LEVEL * SkipListConfig.P && result < SkipListConfig.MAX_LEVEL) {
result++;
}
return result;
}
/**
* 计算跳跃表的平均高度
*
* @param skipList
* @param <T>
* @return
*/
public static <T> double computeAvgLevel(SkipList<T> skipList) {
double result = 0;
for (SkipListNode<T> skipListNode : skipList) {
result += skipListNode.getLevels().length;
}
return result / skipList.length;
}
}
public abstract class SkipListConfig {
/**
* 每一层节点提升为上层节点的概率，概率越大，层数越高
*/
public static final double P = 0.5;
public static final int MAX_LEVEL = 64;
public static final int MIN_LEVEL = 1;
}
/**
* 跳表节点
*/
@Data
@Accessors(chain = true)
@EqualsAndHashCode
public class SkipListNode<T> implements Comparable<SkipListNode<T>> {
/**
* 存储数据
*/
private T element;
/**
* 排序的分值，约定0为最小分数
*/
private double score;
/**
* 后退指针（指向前一个节点）
* <p>
* 头结点指向null
*/
private SkipListNode<T> prev;
/**
* 每个节点的数组长度不一样，随机生成一个层级
* <p>
* 例如，层级为8，代表该节点出现在8个层级上
* <p>
* 值越大，出现概率越低
*/
private SkipListLevel<T>[] levels;
@Override
public int compareTo(SkipListNode<T> other) {
return Double.compare(this.score, other.score);
}
@Data
@NoArgsConstructor
@AllArgsConstructor
public static class SkipListLevel<T> {
/**
* 同一层的下一个结点
*/
private SkipListNode<T> next;
/**
* 当前结点与同层的next节点之间的距离
*/
private int span;
}
public SkipListNode(int levelNum) {
this.element = null;
this.score = 0;
prev = null;
levels = new SkipListLevel[levelNum];
for (int i = 0; i < levels.length; i++) {
levels[i] = new SkipListLevel<>(null, 0);
}
}
public SkipListNode() {
this.element = null;
score = 0;
prev = null;
levels = new SkipListLevel[SkipListUtil.generateRandomLevel()];
for (int i = 0; i < levels.length; i++) {
levels[i] = new SkipListLevel<>(null, 0);
}
}
@Override
public String toString() {
return "SkipListNode{" +
"element=" + element +
", score=" + score +
", prev=" + prev +
", levels=" + levels.length +
'}';
}
}
public class SkipList<T> implements Iterable<SkipListNode<T>> {
/**
* 头结点
*/
SkipListNode<T> head;
/**
* 尾结点
*/
SkipListNode<T> tail;
/**
* 除头结点之外的节点个数
*/
int length;
/**
* 跳跃表的高度
*/
int level;
public SkipList() {
// 初始化头结点
head = new SkipListNode<T>(SkipListConfig.MAX_LEVEL);
tail = null;
this.length = 0;
this.level = 1;
}
/**
* 查询节点所在的位置（有序链表）
* <p>
* 1. 查询上层节点（每一层都是有序链表）
* <p>
* 2. 上层发现大于或为null，查找下一层
*
* @param node
* @return
*/
public SkipListNode<T>[] find(SkipListNode<T> node) {
SkipListNode<T>[] update = new SkipListNode[node.getLevels().length];
SkipListNode<T> pNode = this.head;
SkipListNode<T> nextNode;
// 当插入节点层数为1时，会退化，因此需要进行优化
for (int i = node.getLevels().length - 1; i >= 0; i--) {
while ((nextNode = pNode.getLevels()[i].getNext()) != null && nextNode.compareTo(node) < 0) {
pNode = nextNode;
}
update[i] = pNode;
}
// 返回每一个层级插入位置的前一个节点
return update;
}
/**
* 插入节点
* <p>
* 1. 查询插入位置
* <p>
* 2. 调整跳跃表高度
* <p>
* 3. 插入节点
* <p>
* 4. 调整prev指针
*
* @param node 待插入节点
*/
public void add(SkipListNode<T> node) {
if (this.length++ == 0) {
this.tail = node;
SkipListNode.SkipListLevel<T>[] headLevels = this.head.getLevels();
for (int i = 0; i < node.getLevels().length; i++) {
headLevels[i].setNext(node);
}
return;
}
SkipListNode.SkipListLevel<T>[] levels = node.getLevels();
// 更新跳表的最大层数
this.level = Math.max(this.level, levels.length);
// 查询前置节点
SkipListNode<T>[] preNodes = find(node);
for (int i = 0; i < levels.length; i++) {
SkipListNode.SkipListLevel<T> preNodeLevel = preNodes[i].getLevels()[i];
SkipListNode<T> nextNode = preNodeLevel.getNext();
// 当前插入节点连接下一个结点
levels[i].setNext(nextNode);
// nextNode连接当前结点
nextNode.setPrev(node);
// 前置节点连接当前插入节点
preNodeLevel.setNext(node);
}
// 如果当前结点插入在尾结点之后，那么当前插入的节点就是新的尾结点
SkipListNode<T> preNode = preNodes[0];
if (preNode == tail) {
tail = node;
}
node.setPrev(preNode);
}
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
for (SkipListNode<T> skipListNode : this) {
builder.append(skipListNode.toString()).append("->");
}
return builder.toString();
}
/**
* 自定义迭代器
*/
private class SkipListIterator implements Iterator<SkipListNode<T>> {
SkipListNode<T> prevNode;
int cursor;
public SkipListIterator() {
this.prevNode = tail;
this.cursor = length - 1;
}
@Override
public boolean hasNext() {
return cursor >= 0;
}
@Override
public SkipListNode<T> next() {
SkipListNode<T> result = prevNode;
prevNode = prevNode.getPrev();
cursor--;
return result;
}
}
@Override
public Iterator<SkipListNode<T>> iterator() {
return new SkipListIterator();
}
}
测试代码
public class MainDemo {
public static void main(String[] args) {
SkipList<String> skipList = new SkipList<>();
SkipListNode<String> skipListNodeD = new SkipListNode<>(4);
skipListNodeD.setElement("4");
skipListNodeD.setScore(4);
skipList.add(skipListNodeD);
SkipListNode<String> skipListNodeA = new SkipListNode<>(1);
skipListNodeA.setElement("2");
skipListNodeA.setScore(2);
skipList.add(skipListNodeA);
SkipListNode<String> skipListNodeB = new SkipListNode<>(1);
skipListNodeB.setElement("1");
skipListNodeB.setScore(1);
skipList.add(skipListNodeB);
SkipListNode<String> skipListNodeC = new SkipListNode<>(1);
skipListNodeC.setElement("3");
skipListNodeC.setScore(3);
skipList.add(skipListNodeC);
System.out.println(skipList);
}
}
