publicintgetLevelRandomly(){ int level = 1; //Math.random() < probability 跨越一层的概率为p while (Math.random() < probability && level < maxLevel) { level++; }
return level; }
影响层级的是两个因素:
概率p
最大层数maxLevel
分析参数与性能
产生层级越高的节点,概率越低
节点层级为1是100%,层级恰好为1的概率是(1-p)
节点层级恰好是2的概率 p(跨越第一层) * p(但没有跨越到第三层) = p * (1 - p )
SkipListNode next = newNode.getPointers()[0].getNext(); if (next != null) { next.setPrev(newNode); } else { tail = newNode; }
length++; return newNode; }
publicintgetLevelRandomly(){ int level = 1; //Math.random() < probability 跨越一层的概率为p while (Math.random() < probability && level < maxLevel) { level++; }
span += curNodePointer.getSpan(); curNode = next; next = curNode.getPointers()[i].getNext(); }
//已经找到了本身该节点 if (dictObj.equals(new Dict(curNode.getDictName(), curNode.getScore()))) { return span; } }
return0; } /** * 查找在排名范围内的字典数据 * * @param low * @param high * @return */ public List<String> zrange(int low, int high){ //1. 从最高层往第0层遍历累加span(rank),找到rank等于low的节点target, //2. 遍历第0层的target往后的 high - low
SkipListNode curNode = this.head; SkipListNode next; int rank = 0;
for (int i = level; i >= 0; i--) {
next = curNode.getPointers()[i].getNext(); while (next != null && (rank + curNode.getPointers()[i].getSpan()) <= low) { rank += curNode.getPointers()[i].getSpan(); curNode = next; next = curNode.getPointers()[i].getNext(); }
if (rank == low) { break; } }
List<String> res = new ArrayList<>(); res.add(curNode.getDictName()); for (int i = low; i < high; i++) { SkipListNode next1 = curNode.getPointers()[0].getNext(); if (next1 == null) { break; }