当节点数量足够多时，这种方式得到的跳跃表形态可以逼近理想的跳表的。很惭愧我不知道怎么证明，学过概率统计的同学一定很容易理解。它的时间复杂度就是近似为 O(logN) 。当然也有不理想的情况，当跳表中每一个节点随机得到的层高度都是 1 时，跳表就是一个普通双向链表，时间复杂度为 O(N) 。因此，时间复杂度平均O(logN)、最坏O(N)，这种说法是比较严谨的。
节点的分值这个分值 score 很容易与节点的“跨度”混淆。跨度其实就是节点在跳表中的排位，或者说序号。而分值是一个节点属性。节点按照分值大小由小到大排列，不同节点的分值可以相等。如果分值相等，对象较大的会排在后面(靠近表尾方向)。
在实际API应用中，需要以分值和obj成员对象作为target进行查询、插入等操作。
跳跃表的插入-代码实现流程如下：
按照幂次定律获取随机数，作为索引层的高度levelHeight，实例化新节点target；
设置一个SkipListNode类型的数组，update[]（记录所有需要进行调整的前置位节点，包括需要调整forword、或者只需要修改span值的节点），update[]的大小为max(levelHeight,maxLevelHeight);
设置int数组rank[]，记录update[]数组中各个对应节点的排位
遍历 update[] 进行插入和更新操作；根据update[]获取插入位置节点，进行插入；根据rank[]来辅助更新跨度值span。
实际代码比上述流程要复杂很多，levelHeight与maxLevelHeight的大小关系不能确定，根据不同的情况要对update[]进行不同的处理。
跳跃表插入的代码如下所示：
注意：是依据score大小和obj的大小来决定插入顺序
public SkipListNode slInsert(double score, T obj) { int levelHeight = getRandomHeight(); SkipListNode<T> target = new SkipListNode<>(obj, levelHeight, score); // update[i] 记录所有需要进行调整的前置位节点 SkipListNode[] update = new SkipListNode[Math.max(levelHeight, maxLevel)]; int[] rank = new int[update.length];//记录每一个update节点的排位 int i = update.length - 1; if (levelHeight > maxLevel) { for (; i >= maxLevel; --i) { update[i] = header; rank[i] = 0; } maxLevel = levelHeight; } for (; i >= 0; --i) { SkipListNode<T> node = header; SkipListNode<T> next = node.getLevel()[i].getForward(); rank[i] = 0; //遍历得到与target最接近的节点(左侧) while (next != null && (score > next.getScore() || score == next.getScore() && next.getObj().compareTo(obj) < 0)) { rank[i] += node.getLevel()[i].getSpan(); node = next; next = node.getLevel()[i].getForward(); } update[i] = node; } //当maxLevel>levelHeight，前面部分节点的span值加1，因为该节点与forword指向节点之间将要 多出来一个新节点 for (i = update.length - 1; i >= levelHeight; --i) { int span = update[i].getLevel()[i].getSpan(); update[i].getLevel()[i].setSpan(++span); } //遍历 update[] 进行插入和更新操作 for (; i >= 0; --i) { SkipListLevel pre = update[i].getLevel()[i]; //将target节点插入update[i]和temp之间 SkipListNode<T> temp = pre.getForward(); int span = pre.getSpan(); pre.setForward(target); pre.setSpan(rank[0] + 1 - rank[i]); target.getLevel()[i].setSpan(span > 0 ? (span - rank[0] + rank[i]) : 0); target.getLevel()[i].setForward(temp); //设置后退指针 if (temp == null) { target.setBackword(header); } else { target.setBackword(temp.getBackword()); temp.setBackword(target); } } if (tail.getLevel()[0].getForward() != null) { tail = target; } length++; return target; }本篇博客介绍了跳跃表基本原理，并使用java完成了基本数据结构的封装，实现了节点插入操作。后续博客会陆续记录“删除”、“搜索”等功能的实现。