Java实现跳跃表(skiplist)的简单实例-eolink官网

Java实现跳跃表(skiplist)的简单实例

跳跃链表是一种随机化数据结构，基于并联的链表，其效率可比拟于二叉查找树(对于大多数操作需要O(log n)平均时间)，并且对并发算法友好。

基本上，跳跃列表是对有序的链表增加上附加的前进链接，增加是以随机化的方式进行的，所以在列表中的查找可以快速的跳过部分列表(因此得名)。所有操作都以对数随机化的时间进行。

实现原理：

跳跃表的结构是：假如底层有10个节点，那么底层的上一层理论上就有5个节点，再上一层理论上就有2个或3个节点，再上一层理论上就有1个节点。所以从这里可以看出每一层的节点个数为其下一层的1/2个元素，以此类推。从这里我们可以看到，从插入时我们只要保证上一层的元素个数为下一层元素个数的1/2，我们的跳跃表就能成为理想的跳跃表。那么怎么才能保证我们插入时上层元素个数是下层元素个数的1/2呢，？很简单抛硬币就可以解决了，假设元素X要插入跳跃表，最底层是肯定要插入X的，那么次低层要不要插入呢，我们希望上层元素个数是下层的1/2，那么我们有1/2的概率要插入到次低层，这样就来抛硬币吧，正面就插入，反面就不插入，次次底层相对于次低层，我们还是有1/2的概率插入，那么就继续抛硬币吧，以此类推元，素X插入第n层的概率是(1/2)的n次。这样，我们能在跳跃表中插入一个元素了。

1 对跳表中各个元素（键值对）的封装类SkipListEntry.java

public class SkipListEntry

{

public String key;

public V value;

public int pos; // 主要为了打印链表用

public SkipListEntry up, down, left, right; // 上下左右四个指针

public static String negInf = new String("-oo"); // 负无穷

public static String posInf = new String("+oo"); // 正无穷

public SkipListEntry(String k, V v)

{

key = k;

value = v;

up = down = left = right = null;

}

public V getValue()

{

return value;

}

public String getKey()

{

return key;

}

public V setValue(V val)

{

V oldValue = value;

value = val;

return oldValue;

}

@SuppressWarnings("unchecked")

public boolean equals(Object o)

{

SkipListEntry entry;

try

{

entry = (SkipListEntry) o; // 检测类型

} catch (ClassCastException ex)

{

return false;

}

return (entry.getKey() == key) && (entry.getValue().equals(value));

}

public String toString()

{

return "(" + key + "," + value + ")";

}

2 Skip List的具体实现（包含增、删、改、查）

import java.util.Random;

/**

* 跳表的一种简单实现。key只能为字符串类型，value可以为任意对象类型

* @param

* @author xxx 2017年2月14日下午9:42:06

* @version v1.0

public class SkipList

{

public SkipListEntry head; // 顶层的第一个元素

public SkipListEntry tail; // 顶层的最后一个元素

public int size; // 跳跃表中的元素个数

public int height; // 跳跃表的高度

public Random flag; // 投掷硬币

/**

* 默认构造函数

* @author xxx 2017年2月14日下午9:32:22

* @since v1.0

public SkipList()

{

head = new SkipListEntry(SkipListEntry.negInf, null);

tail = new SkipListEntry(SkipListEntry.posInf, null);

head.right = tail;

tail.left = head;

size = 0;

height = 0;

flag = new Random();

}

/**

* 返回元素的个数

* @return

* @author xxx 2017年2月14日下午9:35:22

* @since v1.0

public int size()

{

return size;

}

/**

* 判断跳表中的元素个数是否为零

* @return

* @author xxx 2017年2月14日下午9:35:52

* @since v1.0

public boolean isEmpty()

{

return (size == 0);

}

/**

* 从最顶层的第一个元素，也即head元素开始查找，直到找到第0层、要插入的位置前面的那个key

* @param k

* @return

* @author xxx 2017年2月14日下午9:42:12

* @since v1.0

private SkipListEntry findEntry(String k)

{

SkipListEntry p = head;

while (true)

{

* 一直向右找，例: k=34。 10 ---> 20 ---> 30 ---> 40 ^ | p 会在30处停止

while (p.right.key != SkipListEntry.posInf && p.right.key.compareTo(k) <= 0)

{

p = p.right;

}

// 如果还有下一层，就到下一层继续查找

if (p.down != null)

{

p = p.down;

} else

{

break; // 到了最下面一层就停止查找

}

return p; // p.key <= k

}

/** 返回和key绑定的值 */

public V get(String k)

{

SkipListEntry p = findEntry(k);

if (k.equals(p.getKey()))

{

return p.value;

} else

{

return null;

}

/**

* 往跳表中插入一个键值对，如果键已经存在，则覆盖相应的值并返回旧值

* @param k

* @param v

* @return

* @author xxx 2017年2月14日下午9:48:54

* @since v1.0

public V put(String k, V v)

{

System.out.println("-----插入[" + k + "]之前的跳跃表是:-----");

printHorizontal();

SkipListEntry p, q;

p = findEntry(k);

if (k.equals(p.getKey()))

{

V old = p.value;

p.value = v;

return old;

}

q = new SkipListEntry(k, v);

q.left = p;

q.right = p.right;

p.right.left = q;

p.right = q;

int currentLevel = 0; // 当前层 currentLevel = 0

// 随机值小于0.5，则插入的键值对对应的键需要在上一层建立关联，同时有可能增加跳表的高度

while (flag.nextDouble() < 0.5)

{

// 如果超出了高度，需要重新建一个顶层

if (currentLevel >= height)

{

SkipListEntry p1, p2;

height = height + 1;

p1 = new SkipListEntry(SkipListEntry.negInf, null);

p2 = new SkipListEntry(SkipListEntry.posInf, null);

p1.right = p2;

p1.down = head;

p2.left = p1;

p2.down = tail;

head.up = p1;

tail.up = p2;

head = p1;

tail = p2;

}

while (p.up == null)

{

p = p.left;

}

p = p.up;

SkipListEntry e;

* 注意，本实现中只有第0层的链表持有键对应的值，1 ~ height 层中的SkipListEntry对象

* 仅仅持有键的引用，值为空，以便节省空间。

e = new SkipListEntry(k, null);

e.left = p;

e.right = p.right;

e.down = q;

p.right.left = e;

p.right = e;

q.up = e;

q = e; // q 进行下一层迭代

currentLevel = currentLevel + 1; // 当前层 +1

}

// 插入一个键值对后总数加1

size = size + 1;

System.out.println("-----插入[" + k + "]之后的跳跃表是:-----");

printHorizontal();

return null;

}

/**

* 根据键删除键值对

* @param key

* @return

* @author xxx 2017年2月14日下午10:08:17

* @since v1.0

public void remove(String key)

{

SkipListEntry p = findEntry(key);

if(!p.getKey().equals(key)) {

return;

}

//删除元素后重新关联，同时使被删除的对象游离，便于垃圾回收

http:// p.left.right = p.right;

p.right.left = p.left;

p.right = null;

p.left = null;

//自底向上，使所有键等于key的SkipListEntry对象左右两个方向的引用置空

while(p.up != null) {

p = p.up;

p.left.right = p.right;

p.right.left = p.left;

p.right = null;

p.left = null;

}

//自顶向下，使所有键等于key的SkipListEntry对象上下两个方向的引用置空

while(p.down != null) {

SkipListEntry temp = p.down;

p.down = null;

temp.up = null;

p = temp;

}

* 删除元素后，如果顶层的链表只有head和tail两个元素，则删除顶层。

* 删除顶层以后最新的顶层如果依然只有head和tail两个元素，则也要被删除，以此类推。

while(head.right.key == tail.key && height > 0) {

SkipListEntry p1, p2;

p1 = head.down;

p2 = tail.down;

head.right = null;

head.down = null;

tail.left = null;

tail.down = null;

p1.up = null;

p2.up = null;

head = p1;

tail = p2;

height = height - 1;

}

//成功移除一个元素，大小减1

size = size - 1;

System.out.println("-----删除[" + key + "]后的跳跃表是:-----");

printHorizontal();

}

/**

* 打印出跳表的图示结构(水平方向)

* @author xxx 2017年2月14日下午10:35:36

* @since v1.0

public void printHorizontal()

{

String s = "";

int i;

SkipListEntry p;

p = head;

while (p.down != null)

{

p = p.down;

}

i = 0;

while (p != null)

{

p.pos = i++;

p = p.right;

}

p = head;

while (p != null)

{

s = getOneRow(p);

System.out.println(s);

p = p.down;

}

private String getOneRow(SkipListEntry p)

{

String s;

int a, b, i;

a = 0;

s = "" + p.key;

p = p.right;

while (p != null)

{

SkipListEntry q;

q = p;

while (q.down != null)

q = q.down;

b = q.pos;

s = s + " <-";

for (i = a + 1; i < b; i++)

s = s + "--------";

s = s + "> " + p.key;

a = b;

p = p.right;

}

return s;

}

/**

* 打印出跳表的图示结构(垂直方向)

* @author xxx 2017年2月14日下午10:35:36

* @since v1.0

public void printVertical()

{

String s = "";

SkipListEntry p;

p = head;

while (p.down != null)

p = p.down;

while (p != null)

{

s = getOneColumn(p);

System.out.println(s);

p = p.right;

}

private String getOneColumn(SkipListEntry p)

{

String s = "";

while (p != null)

{

s = s + " " + p.key;

p = p.up;

}

return (s);

}

3 测试

public class Test

{

public static void main(String[] args)

{

SkipList s = new SkipList();

s.put("ABC", "");

s.put("DEF", "");

s.put("KLM", "");

s.put("HIJ", "");

s.put("GHJ", "");

s.put("AAA", "");

s.remove("ABC");

s.remove("DEF");

s.remove("KLM");

s.remove("HIJ");

s.remove("GHJ");

s.remove("AAA");

s.put("ABC", "");

s.put("DEF", "");

s.put("KLM", "");

s.put("HIJ", "");

s.put("GHJ", "");

s.put("AAA", "");

}

//运行测试后结果示例如下（注意：由于跳表的特性，每次运行结果都不一样）

-----插入[ABC]之前的跳跃表是:-----

-oo <-> +oo

-----插入[ABC]之后的跳跃表是:-----

-oo <-> ABC <-> +oo

-----插入[DEF]之前的跳跃表是:-----

-oo <-> ABC <-> +oo

-----插入[DEF]之后的跳跃表是:-----

-oo <---------> DEF <-> +oo

-oo <-> ABC <-> DEF <-> +oo

-----插入[KLM]之前的跳跃表是:-----

-oo <---------> DEF <-> +oo

-oo <-> ABC <-> DEF <-> +oo

-----插入[KLM]之后的跳跃表是:-----

-oo <---------> DEF <-> KLM <-> +oo

-oo <-> ABC <-> DEF <-> KLM <-> +oo

-----插入[HIJ]之前的跳跃表是:-----

-oo <---------> DEF <-> KLM <-> +oo

-oo <-> ABC <-> DEF <-> KLM <-> +oo

-----插入[HIJ]之后的跳跃表是:-----

-oo <---------> DEF <---------> KLM <-> +oo

-oo <-> ABC <-> DEF <---------> KLM <-> +oo

-oo <-> ABC <-> DEF <-> HIJ <-> KLM <-> +oo

-----插入[GHJ]之前的跳跃表是:-----

-oo <---------> DEF <---------> KLM <-> +oo

-oo <-> ABC <-> DEF <---------> KLM <-> +oo

-oo <-> ABC <-> DEF <-> HIJ <-> KLM <-> +oo

-----插入[GHJ]之后的跳跃表是:-----

-oo <-----------------> GHJ <-----------------> +oo

-oo <---------> DEF <-> GHJ <---------> KLM <-> +oo

-oo <-> ABC <-> DEF <-> GHJ <---------> KLM <-> +oo

-oo <-> ABC <-> DEF <-> GHJ <-> HIJ <-> KLM <-> +oo

-----插入[AAA]之前的跳跃表是:-----

-oo <-----------------> GHJ <-----------------> +oo

-oo <---------> DEF <-> GHJ <---------> KLM <-> +oQUxNqo

-oo <-> ABC <-> DEF <-> GHJ <---------> KLM <-> +oo

-oo <-> ABC <-> DEF <-> GHJ <-> HIJ <-> KLM <-> +oo

-----插入[AAA]之后的跳跃表是:-----

-oo <-------------------------> GHJ <-----------------> +oo

-oo <-> AAA <-----------------> GHJ <-----------------> +oo

-oo <-> AAA <---------> DEF <-> GHJ <---------> KLM <-> +oo

-oo <-> AAA <-> ABC <-> DEF <-> GHJ <---------> KLM <-> +oo

-oo <-> AAA <-> ABC <-> DEF <-> GHJ <-> HIJ <-> KLM <-> +oo

-----删除[ABC]后的跳跃表是:-----

-oo <-----------------> GHJ <-----------------> +oo

-oo <-> AAA <---------> GHJ <-----------------> +oo

-oo <-> AAA <-> DEF <-> GHJ <---------> KLM <-> +oo

-oo <-> AAA <-> DEF <-> GHJ <-> HIJ <-> KLM <-> +oo

-----删除[DEF]后的跳跃表是:-----

-oo <---------> GHJ <-----------------> +oo

-oo <-> AAA <-> GHJ <-----------------> +oo

-oo <-> AAA <-> GHJ <---------> KLM <-> +oo

-oo <-> AAA <-> GHJ <-> HIJ <-> KLM <-> +oo

-----删除[KLM]后的跳跃表是:-----

-oo <---------> GHJ <---------> +oo

-oo <-> AAA <-> GHJ <---------> +oo

-oo <-> AAA <-> GHJ <-> HIJ <-> +oo

-----删除[HIJ]后的跳跃表是:-----

-oo <---------> GHJ <-> +oo

-oo <-> AAA <-> GHJ <-> +oo

-----删除[GHJ]后的跳跃表是:-----

-oo <-> AAA <-> +oo

-----删除[AAA]后的跳跃表是:-----

-oo <-> +oo

-----插入[ABC]之前的跳跃表是:-----

-oo <-> +oo

-----插入[ABC]之后的跳跃表是:-----

-oo <-> ABC <-> +oo

-----插入[DEF]之前的跳跃表是:-----

-oo <-> ABC <-> +oo

-----插入[DEF]之后的跳跃表是:-----

-oo <---------> DEF <-> +oo

-oo <-> ABC <-> DEF <-> +oo

-----插入[KLM]之前的跳跃表是:-----

-oo <---------> DEF <-> +oo

-oo <-> ABC <-> DEF <-> +oo

-----插入[KLM]之后的跳跃表是:-----

-oo <---------> DEF <---------> +oo

-oo <-> ABC <-> DEF <-> KLM <-> +oo

-----插入[HIJ]之前的跳跃表是:-----

-oo <---------> DEF <---------> +oo

-oo <-> ABC <-> DEF <-> KLM <-> +oo

-----插入[HIJ]之后的跳跃表是:-----

-oo <---------> DEF <-----------------> +oo

-oo <---------> DEF <-> HIJ <---------> +oo

-oo <-> ABC <-> DEF <-> HIJ <-> KLM <-> +oo

-----插入[GHJ]之前的跳跃表是:-----

-oo <---------> DEF <-----------------> +oo

-oo <---------> DEF <-> HIJ <---------> +oo

-oo <-> ABC <-> DEF <-> HIJ <-> KLM <-> +oo

-----插入[GHJ]之后的跳跃表是:-----

-oo <---------> DEF <-------------------------> +oo

-oo <---------> DEF <---------> HIJ <---------> +oo

-oo <-> ABC <-> DEF <-> GHJ <-> HIJ <-> KLM <-> +oo

-----插入[AAA]之前的跳跃表是:-----

-oo <---------> DEF <-------------------------> +oo

-oo <---------> DEF <---------> HIJ <---------> +oo

-oo <-> ABC <-> DEF <-> GHJ <-> HIJ <-> KLM <-> +oo

-----插入[AAA]之后的跳跃表是:-----

-oo <-----------------> DEF <-------------------------> +oo

-oo <-----------------> DEF <---------> HIJ <---------> +oo

-oo <-> AAA <-> ABC <-> DEF <-> GHJ <-> HIJ <-> KLM <-> +oo

总结

以上所述就是本文关于Java编程实现一个简单的跳跃表的实现方法实例，希望对大家有所帮助，感谢大家对本站的支持！

Iterator与LIstIterator接口在java中的区别有哪些

282 2023-04-03

Java实现跳跃表(skiplist)的简单实例

Flask接口签名sign原理与实例代码浅析

java中的接口是类吗

Iterator与LIstIterator接口在java中的区别有哪些

推荐文章

接口调用是什么意思？几种常用接口调用方式

接口设计原则

8款在线 API 接口文档管理工具

api管理系统是什么？

什么是接口调试？接口调试的步骤有哪些？

api 接口管理系统有哪些？

接口测试有几种测试方法

API文档生成工具有哪些？

微服务和api网关区别

交换机配置步骤

最近发表

热评文章

在线接口文档管理工具推荐，支持在线测试，HTTP接口

开源的在线接口文档wiki工具Mindoc的介绍与使

如何优雅的进行接口设计？接口设计的六大原则是什么？

什么是API测试,api检测公司

软件接口设计怎么做？前后端分离软件接口设计思路

接口管理平台推荐，几大接口管理平台总有一款适合你！