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

2023-09-24 14:37:47 171

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

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

实现原理：

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

第一次知道跳表这种数据结构的时间大概是在一年前（说这句话时候可能就被无数同胞鄙视了），但自己却不知道如何实现。当时印象最深的就是一篇跳跃表(SkipList)-实现(Java)的文章，因为这篇文章中的SkipList的实现方式最让人容易理解，我最初也是通过这篇文章对跳表有了更进一步的认识，所以，真的要在这里感谢这篇文章的主人。一年之后，我发现自己对跳表的认识又模糊不清了，所以最先想到的也是这篇文章。今天再次拜读此文，同时实现了其中未给出的删除方法。并增加了泛型，但泛型也只是对value采用了泛型，对Key依然采用原文中的String类型。所以依然比较简单和局限。之所以贴出来，是为了增进自己对SkipList的理解和作为备忘。原文的链接如之前所述，原文具体作者其实我也不知道是谁，只想在此默默的说声感谢。当然了，若原文作者觉得我有什么冒犯或侵权的行为，我会立马删帖。

关于跳表的定义和介绍，读者可以参考原文。这里就直接给出原码了，这里的原码与原文的唯一的一点区别就是，我这里给出了原文没给出的删除方法（原文其实参考的是一篇英文文章，英文文章给出了删除方法，我直到后来才发现，不过自己的实现和英文文章想比，代码略显多余，此处贴出来的是我自己实现的删除方法）。可能实现上比较糟糕，所以也恳请大家批评指正！！！

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

publicclassSkipListEntry
{
publicStringkey;
publicVvalue;
publicintpos;//主要为了打印链表用
publicSkipListEntryup,down,left,right;//上下左右四个指针
publicstaticStringnegInf=newString("-oo");//负无穷
publicstaticStringposInf=newString("+oo");//正无穷
publicSkipListEntry(Stringk,Vv)
{
key=k;
value=v;
up=down=left=right=null;
}
publicVgetValue()
{
returnvalue;
}
publicStringgetKey()
{
returnkey;
}
publicVsetValue(Vval)
{
VoldValue=value;
value=val;
returnoldValue;
}
@SuppressWarnings("unchecked")
publicbooleanequals(Objecto)
{
SkipListEntryentry;
try
{
entry=(SkipListEntry)o;//检测类型
}catch(ClassCastExceptionex)
{
returnfalse;
}
return(entry.getKey()==key)&&(entry.getValue().equals(value));
}
publicStringtoString()
{
return"("+key+","+value+")";
}
}

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

importjava.util.Random;
/**
*跳表的一种简单实现。key只能为字符串类型，value可以为任意对象类型
*@param
*@authorxxx2017年2月14日下午9:42:06
*@versionv1.0
*/
publicclassSkipList
{
publicSkipListEntryhead;//顶层的第一个元素
publicSkipListEntrytail;//顶层的最后一个元素
publicintsize;//跳跃表中的元素个数
publicintheight;//跳跃表的高度
publicRandomflag;//投掷硬币
/**
*默认构造函数
*@authorxxx2017年2月14日下午9:32:22
*@sincev1.0
*/
publicSkipList()
{
head=newSkipListEntry(SkipListEntry.negInf,null);
tail=newSkipListEntry(SkipListEntry.posInf,null);
head.right=tail;
tail.left=head;
size=0;
height=0;
flag=newRandom();
}
/**
*返回元素的个数
*@return
*@authorxxx2017年2月14日下午9:35:22
*@sincev1.0
*/
publicintsize()
{
returnsize;
}
/**
*判断跳表中的元素个数是否为零
*@return
*@authorxxx2017年2月14日下午9:35:52
*@sincev1.0
*/
publicbooleanisEmpty()
{
return(size==0);
}
/**
*从最顶层的第一个元素，也即head元素开始查找，直到找到第0层、要插入的位置前面的那个key
*@paramk
*@return
*@authorxxx2017年2月14日下午9:42:12
*@sincev1.0
*/
privateSkipListEntryfindEntry(Stringk)
{
SkipListEntryp=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;//到了最下面一层就停止查找
}
}
returnp;//p.key<=k
}
/**返回和key绑定的值*/
publicVget(Stringk)
{
SkipListEntryp=findEntry(k);

if(k.equals(p.getKey()))
{
returnp.value;
}else
{
returnnull;
}
}
/**
*往跳表中插入一个键值对，如果键已经存在，则覆盖相应的值并返回旧值
*@paramk
*@paramv
*@return
*@authorxxx2017年2月14日下午9:48:54
*@sincev1.0
*/
publicVput(Stringk,Vv)
{
System.out.println("-----插入["+k+"]之前的跳跃表是:-----");
printHorizontal();

SkipListEntryp,q;

p=findEntry(k);

if(k.equals(p.getKey()))
{
Vold=p.value;
p.value=v;
returnold;
}
q=newSkipListEntry(k,v);
q.left=p;
q.right=p.right;
p.right.left=q;
p.right=q;
intcurrentLevel=0;//当前层currentLevel=0
//随机值小于0.5，则插入的键值对对应的键需要在上一层建立关联，同时有可能增加跳表的高度
while(flag.nextDouble()<0.5)
{
//如果超出了高度，需要重新建一个顶层
if(currentLevel>=height)
{
SkipListEntryp1,p2;
height=height+1;
p1=newSkipListEntry(SkipListEntry.negInf,null);
p2=newSkipListEntry(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;

SkipListEntrye;
/*
*注意，本实现中只有第0层的链表持有键对应的值，1~height层中的SkipListEntry对象
*仅仅持有键的引用，值为空，以便节省空间。
*/
e=newSkipListEntry(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();
returnnull;
}
/**
*根据键删除键值对
*@paramkey
*@return
*@authorxxx2017年2月14日下午10:08:17
*@sincev1.0
*/
publicvoidremove(Stringkey)
{
SkipListEntryp=findEntry(key);

if(!p.getKey().equals(key)){
return;
}
//删除元素后重新关联，同时使被删除的对象游离，便于垃圾回收
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){
SkipListEntrytemp=p.down;
p.down=null;
temp.up=null;
p=temp;
}
/*
*删除元素后，如果顶层的链表只有head和tail两个元素，则删除顶层。
*删除顶层以后最新的顶层如果依然只有head和tail两个元素，则也要被删除，以此类推。
*/
while(head.right.key==tail.key&&height>0){
SkipListEntryp1,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();
}
/**
*打印出跳表的图示结构(水平方向)
*@authorxxx2017年2月14日下午10:35:36
*@sincev1.0
*/
publicvoidprintHorizontal()
{
Strings="";
inti;
SkipListEntryp;
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;
}
}
privateStringgetOneRow(SkipListEntryp)
{
Strings;
inta,b,i;
a=0;
s=""+p.key;
p=p.right;
while(p!=null)
{
SkipListEntryq;
q=p;
while(q.down!=null)
q=q.down;
b=q.pos;
s=s+"<-";
for(i=a+1;i"+p.key;
a=b;
p=p.right;
}
returns;
}
/**
*打印出跳表的图示结构(垂直方向)
*@authorxxx2017年2月14日下午10:35:36
*@sincev1.0
*/
publicvoidprintVertical()
{
Strings="";
SkipListEntryp;
p=head;
while(p.down!=null)
p=p.down;
while(p!=null)
{
s=getOneColumn(p);
System.out.println(s);
p=p.right;
}
}
privateStringgetOneColumn(SkipListEntryp)
{
Strings="";
while(p!=null)
{
s=s+""+p.key;
p=p.up;
}
return(s);
}
}

3测试

publicclassTest
{
publicstaticvoidmain(String[]args)
{
SkipLists=newSkipList();
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
-oo<->ABC<->+oo
-----插入[DEF]之前的跳跃表是:-----
-oo<->ABC<->+oo
-oo<->ABC<->+oo
-----插入[DEF]之后的跳跃表是:-----
-oo<--------->DEF<->+oo
-oo<->ABC<->DEF<->+oo
-oo<->ABC<->DEF<->+oo
-----插入[KLM]之前的跳跃表是:-----
-oo<--------->DEF<->+oo
-oo<->ABC<->DEF<->+oo
-oo<->ABC<->DEF<->+oo
-----插入[KLM]之后的跳跃表是:-----
-oo<--------->DEF<->KLM<->+oo
-oo<->ABC<->DEF<->KLM<->+oo
-oo<->ABC<->DEF<->KLM<->+oo
-----插入[HIJ]之前的跳跃表是:-----
-oo<--------->DEF<->KLM<->+oo
-oo<->ABC<->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<----------------->GHJ<----------------->+oo
-oo<----------------->GHJ<----------------->+oo
-oo<----------------->GHJ<----------------->+oo
-oo<----------------->GHJ<----------------->+oo
-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<----------------->GHJ<----------------->+oo
-oo<----------------->GHJ<----------------->+oo
-oo<----------------->GHJ<----------------->+oo
-oo<----------------->GHJ<----------------->+oo
-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<------------------------->GHJ<----------------->+oo
-oo<------------------------->GHJ<----------------->+oo
-oo<------------------------->GHJ<----------------->+oo
-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<----------------->GHJ<----------------->+oo
-oo<----------------->GHJ<----------------->+oo
-oo<----------------->GHJ<----------------->+oo
-oo<----------------->GHJ<----------------->+oo
-oo<->AAA<--------->GHJ<----------------->+oo
-oo<->AAA<->DEF<->GHJ<--------->KLM<->+oo
-oo<->AAA<->DEF<->GHJ<--------->KLM<->+oo
-oo<->AAA<->DEF<->GHJ<->HIJ<->KLM<->+oo
-----删除[DEF]后的跳跃表是:-----
-oo<--------->GHJ<----------------->+oo
-oo<--------->GHJ<----------------->+oo
-oo<--------->GHJ<----------------->+oo
-oo<--------->GHJ<----------------->+oo
-oo<--------->GHJ<----------------->+oo
-oo<->AAA<->GHJ<----------------->+oo
-oo<->AAA<->GHJ<--------->KLM<->+oo
-oo<->AAA<->GHJ<--------->KLM<->+oo
-oo<->AAA<->GHJ<->HIJ<->KLM<->+oo
-----删除[KLM]后的跳跃表是:-----
-oo<--------->GHJ<--------->+oo
-oo<--------->GHJ<--------->+oo
-oo<--------->GHJ<--------->+oo
-oo<--------->GHJ<--------->+oo
-oo<--------->GHJ<--------->+oo
-oo<->AAA<->GHJ<--------->+oo
-oo<->AAA<->GHJ<--------->+oo
-oo<->AAA<->GHJ<--------->+oo
-oo<->AAA<->GHJ<->HIJ<->+oo
-----删除[HIJ]后的跳跃表是:-----
-oo<--------->GHJ<->+oo
-oo<--------->GHJ<->+oo
-oo<--------->GHJ<->+oo
-oo<--------->GHJ<->+oo
-oo<--------->GHJ<->+oo
-oo<->AAA<->GHJ<->+oo
-oo<->AAA<->GHJ<->+oo
-oo<->AAA<->GHJ<->+oo
-oo<->AAA<->GHJ<->+oo
-----删除[GHJ]后的跳跃表是:-----
-oo<->AAA<->+oo
-oo<->AAA<->+oo
-oo<->AAA<->+oo
-oo<->AAA<->+oo
-----删除[AAA]后的跳跃表是:-----
-oo<->+oo
-----插入[ABC]之前的跳跃表是:-----
-oo<->+oo
-----插入[ABC]之后的跳跃表是:-----
-oo<->ABC<->+oo
-----插入[DEF]之前的跳跃表是:-----
-oo<->ABC<->+oo
-----插入[DEF]之后的跳跃表是:-----
-oo<--------->DEF<->+oo
-oo<--------->DEF<->+oo
-oo<--------->DEF<->+oo
-oo<--------->DEF<->+oo
-oo<->ABC<->DEF<->+oo
-----插入[KLM]之前的跳跃表是:-----
-oo<--------->DEF<->+oo
-oo<--------->DEF<->+oo
-oo<--------->DEF<->+oo
-oo<--------->DEF<->+oo
-oo<->ABC<->DEF<->+oo
-----插入[KLM]之后的跳跃表是:-----
-oo<--------->DEF<--------->+oo
-oo<--------->DEF<--------->+oo
-oo<--------->DEF<--------->+oo
-oo<--------->DEF<--------->+oo
-oo<->ABC<->DEF<->KLM<->+oo
-----插入[HIJ]之前的跳跃表是:-----
-oo<--------->DEF<--------->+oo
-oo<--------->DEF<--------->+oo
-oo<--------->DEF<--------->+oo
-oo<--------->DEF<--------->+oo
-oo<->ABC<->DEF<->KLM<->+oo
-----插入[HIJ]之后的跳跃表是:-----
-oo<--------->DEF<----------------->+oo
-oo<--------->DEF<----------------->+oo
-oo<--------->DEF<----------------->+oo
-oo<--------->DEF<->HIJ<--------->+oo
-oo<->ABC<->DEF<->HIJ<->KLM<->+oo
-----插入[GHJ]之前的跳跃表是:-----
-oo<--------->DEF<----------------->+oo
-oo<--------->DEF<----------------->+oo
-oo<--------->DEF<----------------->+oo
-oo<--------->DEF<->HIJ<--------->+oo
-oo<->ABC<->DEF<->HIJ<->KLM<->+oo
-----插入[GHJ]之后的跳跃表是:-----
-oo<--------->DEF<------------------------->+oo
-oo<--------->DEF<------------------------->+oo
-oo<--------->DEF<------------------------->+oo
-oo<--------->DEF<--------->HIJ<--------->+oo
-oo<->ABC<->DEF<->GHJ<->HIJ<->KLM<->+oo
-----插入[AAA]之前的跳跃表是:-----
-oo<--------->DEF<------------------------->+oo
-oo<--------->DEF<------------------------->+oo
-oo<--------->DEF<------------------------->+oo
-oo<--------->DEF<--------->HIJ<--------->+oo
-oo<->ABC<->DEF<->GHJ<->HIJ<->KLM<->+oo
-----插入[AAA]之后的跳跃表是:-----
-oo<----------------->DEF<------------------------->+oo
-oo<----------------->DEF<------------------------->+oo
-oo<----------------->DEF<------------------------->+oo
-oo<----------------->DEF<--------->HIJ<--------->+oo
-oo<->AAA<->ABC<->DEF<->GHJ<->HIJ<->KLM<->+oo

总结

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

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

热门推荐

随机推荐