百大专升本

　　上一节，我们一起学习了关于跳表的理论知识，相信通过上一节的学习，你一定可以给面试官完完整整地讲清楚跳表的来龙去脉，甚至能够边讲边画图。

　　第一种方式为跳表的通用实现，第二种方式为彤哥自己发明的实现，并运用到HashMap的改写中。

　　普通节点，处于0层的节点，存储数据，典型的单链表结构，包括h0 索引节点，包含着对普通节点的引用，同时增加向右、向下的指针 头索引节点，继承自索引节点，同时，增加所在的层级

　　查找元素，是通过头节点，先尽最大努力往右，再往下，再往右，每一层都要尽最大努力往右，直到右边的索引比目标值大为止，到达0层的时候再按照链表的方式来遍历，用图来表示如下：

　　然后，考虑建立索引，如果需要建立索引，又分成两步：一步是建立竖线(down)，一步是建立横线(right);

　　首先，找到6的位置，走过的路径为 h1->3->3->4，发现应该插入到4和7之间，插入之：

　　然后，建立竖线，即向下的指针，一共有三层，因为超过了当前最高层级，所以，头节点也要相应地往上增加一层，如下：

　　最后，修正横向的指针，即 h2->6、3->6、6->7，修正完成则表示插入元素成功：

　　然后，修正向右的索引，修正了向右的索引，向下的索引就不用管了，相当于从整个跳表中把向下的那一坨都删除了，等着垃圾回收即可。

　　首先，寻找删除的元素的路径：h2->6->6，到这里的时候，正好看到右边有个7，把它干掉：

　　OK，到这里，跳表的通用实现就完事了，其实，你也可以发现，这里还是有一些可以优化的点的，比如right和next指针为什么不能合二为一呢?向下的指针能不能跟指向Node的指针合并呢?

　　为了尝试解决这些问题，彤哥又自己研究了一种实现，这种实现不再区分头索引节点、索引节点、普通节点，把它们全部合并成一个，大家都是一样的，并且，我将它运用到了HashMap的改造中，来看看吧。

　　因为，正好要改造HashMap，所以，关于彤哥的独家实现，我会与HashMap的改造一起来讲解，新的HashMap，我们称之为SkiplistHashMap(前者)，它不同于JDK中现有的ConcurrentSkipListMap(后者)，前者是一个HashMap，时间复杂度为O(1)，后者其实不是HashMap，它只是跳表实现的一种Map，时间复杂度为O(log n)。

　　让我们分析一下SkiplistHashMap，首先，它有一个数组，其次，出现冲突的时候先使用链表来存储冲突的节点，然后，达到一定的阈值时，将链表转换成跳表，所以，它至少需要以下两大种节点类型：

　　普通节点，单链表结构，存储key、value、hash、next等，结构简单，直接给出代码：

　　跳表节点，在通用实现中跳表节点分成了三大类：头索引节点、索引节点、普通节点，让我们仔细分析一下。

　　然后，随便找一个节点，把它拉起来，比如3这个元素，首先，它有一个高度，这里它的高度为2，并且，每一层的这个3都有一个向右的指针(忘掉之前的三种节点类型)，对不对，所以，这里把next废弃掉，变成nexts，记录每一层的这个3的下一个元素是谁：

　　通过这种方式，就把上面三种类型的节点成功地变成了一个大节点，这个节点是有层高的，且每层都有一个向右的指针。

　　让我们模拟一下查找的过程，比如，要查询8这个元素，只需要从头节点的最高层，往右到6这个节点，6在2层向右为空了，所以转到1层，向右到7这个节点，7再向右看一下，是9，比8大，所以7向下到0层，再向右，找到8，所以，整个走过的路径为：h(2)->6(2)->6(1)->7(1)->7(0)->8(0)。

　　不再区分索引节点和普通节点后，一切都将变得简单，无脑向右，再向下，瑞安市天晟包装机械有限公司，再向右即可，代码也变得非常简单。

　　添加元素，同样变得要简单很多，一切尽在注释中，不过，彤哥写这篇文章的时候才发现下面的代码中有个小bug，看看你能不能发现^^

　　好了，关于SkiplistHashMap中跳表的部分我们就讲这么多，需要完整源码的同学可以关注个人公众号彤哥读源码，回复skiplist领取哈。

　　如果是SkipListNode类型，按跳表类型插入元素 如果该位置元素的key值正好与要插入的元素的key值相等，说明是重复元素，替换后直接返回 否则，按链表类型插入元素，且插入元素后判断是否要转换成跳表

　　这里有一个跳表化的过程，我使用的是最简单的方式实现的，即新建一个跳表头节点，然后把元素都put进去：

　　不管从原理还是实现过程，跳表都要比红黑树要简单不少，为什么JDK中不使用跳表而是使用红黑树来实现HashMap呢?

　　稳定度，跳表的随机性太大了，要实现O(log n)的时间复杂度，随机算法要做得很好才行，这方面可以对比看看ConcurrentSkipListMap和redis中zset的实现，而红黑树还算比较稳定; 范围查找，HashMap更多地是运用在查找单个元素，并没有范围查找这种需求，帕金斯谈“乔丹在当今场均60分”言论，所以，使用跳表的必要性不大; 成熟度，红黑树是经过很多实践检验的，比如linux内核、epoll等，而跳表很少，目前已知的好像只有redis的zset使用了跳表; 空间占用，红黑树不管层高多少，每个节点稳定增加左右两个指针和颜色字段，而跳表不一样，随着层高的不断增加，每个元素需要增加的指针也会增加很多，比如，最高为16层，则head和最高的节点需要维护16个向右的指针，这个空间占用是很大的，所以，实现跳表一般也要指定最高只能达到多少层; 流程化，跳表实现可以多种多样，每个人写出来的跳表可能都不一样，但红黑树不一样，流程固化，每个人写出来的差异性不大; 可测试性，跳表很难测试，因为多次运行的结果肯定不一样，而红黑树不一样，只要元素顺序不变，运行的结果肯定是固定的，可测试性好很多;

　　本节，我们一起用两种方式实现了跳表，并将其运用到了HashMap的改写中，相信通过本节的学习你一定可以自信地告诉面试官我可以手写跳表了。