by shihang.mai
1. 代码
package skpilist;
import java.util.Random;
public class SkipList {
// number of entries in the Skip List
public int n;
// height
public int h;
// 表头
private SkipListEntry head;
// 表尾
private SkipListEntry tail;
// 生成randomLevel用到的概率值
private Random r;
public SkipList() {
head = new SkipListEntry(Integer.MIN_VALUE, Integer.MIN_VALUE);
tail = new SkipListEntry(Integer.MAX_VALUE, Integer.MAX_VALUE);
head.right =tail;
tail.left = head;
n = 0;
h = 0;
r = new Random();
}
/**
* 查找
* @param
* @return
*/
public SkipListEntry findEntry(Integer key) {
SkipListEntry p;
/* -----------------
Start at "head"
----------------- */
p = head;
while ( true ) {
/* --------------------------------------------
Search RIGHT until you find a LARGER entry
E.g.: k = 34
10 ---> 20 ---> 30 ---> 40
^
|
p stops here
p.right.key = 40
-------------------------------------------- */
while ( p.right.key != Integer.MAX_VALUE && p.right.key< key ) {
p = p.right;
// System.out.println(">>>> " + p.key);
}
/* ---------------------------------
Go down one level if you can...
--------------------------------- */
if ( p.down != null ) {
p = p.down;
// System.out.println("vvvv " + p.key);
} else{
//加入判断by shihang.mai==============原博主代码需要在这加入判断
if(p.right.key== key){
p = p.right;
}
break; // We reached the LOWEST level... Exit...
}
}
return(p); // p.key <= k
}
public Integer get(int key) {
SkipListEntry p;
p = findEntry(key);
if(p.key ==key) {
return p.value;
} else {
return null;
}
}
public Integer insert(int key, int value) {
SkipListEntry p, q;
int i = 0;
// 查找适合插入的位子
p = findEntry(key);
// 如果跳跃表中存在含有key值的节点，则进行value的修改操作即可完成
if(p.key ==key) {
Integer oldValue = p.value;
p.value = value;
return oldValue;
}
// 如果跳跃表中不存在含有key值的节点，则进行新增操作
q = new SkipListEntry(key, value);
/* --------------------------------------------------------------
Insert q into the lowest level after SkipListEntry p:
p put q here p q
| | | |
V V V V V
Lower level: [ ] <------> [ ] ==> [ ] <--> [ ] <--> [ ]
--------------------------------------------------------------- */
q.left = p;
q.right = p.right;
p.right.left = q;
p.right = q;
//本层操作完毕，看更高层操作
//抛硬币随机决定是否上层插入
while ( r.nextDouble() < 0.5 /* Coin toss */ ) {
if ( i >= h ) // We reached the top level !!!
{
//Create a new empty TOP layer
addEmptyLevel();
}
/* ------------------------------------
Find first element with an UP-link
------------------------------------ */
while ( p.up == null )
{
p = p.left;
}
/* --------------------------------
Make p point to this UP element
-------------------------------- */
p = p.up;
/* ---------------------------------------------------
Add one more (k,*) to the column
Schema for making the linkage:
p <--> e(k,*) <--> p.right
^
|
v
q
---------------------------------------------------- */
SkipListEntry e;
// 这里需要注意的是除底层节点之外的节点对象是不需要value值的
e = new SkipListEntry(key, null);
/* ---------------------------------------
Initialize links of e
--------------------------------------- */
e.left = p;
e.right = p.right;
e.down = q;
/* ---------------------------------------
Change the neighboring links..
--------------------------------------- */
p.right.left = e;
p.right = e;
q.up = e;
//把q执行新插入的节点：
q = e;
// level增加
i = i + 1;
}
n = n+1; //更新链表长度
return null;
}
private void addEmptyLevel() {
SkipListEntry p1, p2;
p1 = new SkipListEntry(Integer.MIN_VALUE, null);
p2 = new SkipListEntry(Integer.MAX_VALUE, null);
p1.right = p2;
p1.down = head;
p2.left = p1;
p2.down = tail;
head.up = p1;
tail.up = p2;
head = p1;
tail = p2;
h = h + 1;
}
public Integer remove(int key) {
SkipListEntry p, q;
p = findEntry(key);
if(!p.key.equals(key)) {
return null;
}
Integer oldValue = p.value;
while(p != null) {
q = p.up;
p.left.right = p.right;
p.right.left = p.left;
p = q;
}
return oldValue;
}
public void printHorizontal()
{
String s = "";
int I;
SkipListEntry p;
/* ----------------------------------
Record the position of each entry
---------------------------------- */
p = head;
while ( p.down != null )
{
p = p.down;
}
i = 0;
while ( p != null )
{
p.pos = I++;
p = p.right;
}
/* -------------------
Print...
------------------- */
p = head;
while ( p != null )
{
s = getOneRow( p );
System.out.println(s);
p = p.down;
}
}
public 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);
}
public static void main(String[] args) {
SkipList l = new SkipList();
Random r = new Random();
for (int i = 0; i < 10; i++ )
{
int tmp = r.nextInt(100);
System.out.println("add:"+tmp);
l.insert( tmp, tmp );
l.printHorizontal();
}
System.out.println("add:18");
l.insert( 18, 18 );
l.printHorizontal();
System.out.println("remove:"+l.remove(18));;
l.printHorizontal();
//System.out.println("over");
}
}
class SkipListEntry {
Integer key;
Integer value;
skpilist.SkipListEntry right;
skpilist.SkipListEntry left;
skpilist.SkipListEntry down;
skpilist.SkipListEntry up;
public SkipListEntry(Integer key, Integer value) {
this.key = key;
this.value = value;
}
public String toString()
{
return "(" + key + "," + value + ")";
}
public int pos;//与数据结构无关，只为输出方便
}
2. 解析
redis的sortSet用的跳表,用空间换时间
节点属性包括:key、value、上下左右节点
class SkipListEntry {
Integer key;
Integer value;
SkipListEntry right;
SkipListEntry left;
SkipListEntry down;
SkipListEntry up;
public SkipListEntry(Integer key, Integer value) {
this.key = key;
this.value = value;
}
public String toString()
{
return "(" + key + "," + value + ")";
}
public int pos;//与数据结构无关，只为输出方便
}
跳表属性包括:有多少个元素、跳表高度、head和tail节点、还有一个抛硬币的随机数(用来决定要不要构建上一层索引的)
public class SkipList<T {
// number of entries in the Skip List
public int n;
// height
public int h;
// 表头
private SkipListEntry head;
// 表尾
private SkipListEntry tail;
// 生成randomLevel用到的概率值
private Random r;
查找
对于查找,例如查找50
- 从head出发查找，因为head指向最顶层链表的开始节点，相当于从顶层开始查找；
- 移动到当前节点的右指针（right）指向的节点，直到右节点的key值大于要查找的key值时停止在当前节点；
- 如果还有更低层次的链表，则移动到当前节点的下一层节点,继续2的过程
- 重复第2步 和 第3步，直到查找到key值所在的节点，或者不存在而退出查找
对于插入,例如插入42
-
先通过查找42，如果找到，那么直接替换值
-
如果没找到返回比它少的一个，即39，那么用一个变量P=39
-
插入的变量Q=42，那么插入到39和44之间，并维护前后指针。这时抛硬币，如果需要向上层晋升，那么
-
将P变量找到最近一个有上层节点的节点，即38，将变量A向上移动一层，创建变量Z(key=42,value=null),插入到上层节点，并维护前后指针。如此往复，如果一直晋升，那么结果如下图
过程图
晋升
对于删除，就把所有层级删掉，并维护前后指针，这个没什么好说的
网友评论