publicSkipList(double probability, int maxLevel){ P = probability; MAX_LEVEL = maxLevel;
listLevel = 1; listHead = new Node<T>(Integer.MIN_VALUE, null, maxLevel); NIL = new Node<T>(Integer.MAX_VALUE, null, maxLevel); for (int i = listHead.forward.length - 1; i >= 0; i--) { listHead.forward[i] = NIL; } }
下面是randomLevel的实现:
1 2 3 4 5 6 7
privateintrandomLevel(){ int level = 1; while (level < MAX_LEVEL && Math.random() < P) { level++; } return level; }
快速查找
经过上面对跳表结构和查找算法的分析,查找的代码其实已经比较清楚了,下面是论文中给出的查找伪代码:
1 2 3 4 5 6 7 8 9 10
Search(list, searchKey) x := list→header -- loop invariant: x→key < searchKey for i := list→level downto 1 do while x→forward[i]→key < searchKey do x := x→forward[i] -- x→key < searchKey ≤ x→forward[1]→key x := x→forward[1] if x→key = searchKey then return x→value else return failure
publicvoidinsert(int searchKey, T newValue){ // update数组为层级索引,用以存储新节点所有层数上,各自的前一个节点的信息 Node<T>[] update = new Node[MAX_LEVEL]; Node<T> curNode = listHead;
// record every level largest value which smaller than insert value in update[] // 在update中纪录每一层中小于searchKey值的最大节点 for (int i = listLevel - 1; i >= 0; i--) { while (curNode.forward[i].key < searchKey) { curNode = curNode.forward[i]; } // use update save node in search path update[i] = curNode; }
// in search path node next node become new node forwords(next) // 插入newNode 串联每一个层级的索引 curNode = curNode.forward[0];
if (curNode.key == searchKey) { curNode.value = newValue; } else { int lvl = randomLevel();
// 随机的层数有可能会大于当前跳表的层数,那么多余的那部分层数对应的update[i]置为sl->head,后面用来初始化 if (listLevel < lvl) { for (int i = listLevel; i < lvl; i++) { update[i] = listHead; } listLevel = lvl; }
Node<T> newNode = new Node<T>(searchKey, newValue, lvl);
// 逐层更新节点的指针(这里的层指的是随机的层,比如当前有4层,然后随机的层为2,则只会将新节点插入下面的两层) // 如果当前跳表层是4,随机的为6,则会把5、6层也赋值,用到update[i] = sl->head;这里的结果。 for (int i = 0; i < lvl; i++) { // 这里就是说随机几层,就用到update中的那几层,插入到update[i]对应的节点之后 newNode.forward[i] = update[i].forward[i]; update[i].forward[i] = newNode; } } }