太刺激了，面试官让我手写跳表，而我用两种实现方式吊打了TA！
|
因为，正好要改造HashMap，所以，关于彤哥的独家实现，我会与HashMap的改造一起来讲解，新的HashMap，我们称之为SkiplistHashMap(前者)，它不同于JDK中现有的ConcurrentSkipListMap(后者)，前者是一个HashMap，时间复杂度为O(1)，后者其实不是HashMap，它只是跳表实现的一种Map，时间复杂度为O(log n)。 另外，我将Skip和List两个单词合成一个了，这是为了后面造一个新单词——Skiplistify，跳表化，-ify词缀结尾，什么化，比如，treeify树化、heapify堆化。 好了，开始SkiplistHashMap的实现，Come On! 数据结构 让我们分析一下SkiplistHashMap，首先，它有一个数组，其次，出现冲突的时候先使用链表来存储冲突的节点，然后，达到一定的阈值时，将链表转换成跳表，所以，它至少需要以下两大种节点类型： 普通节点，单链表结构，存储key、value、hash、next等，结构简单，直接给出代码： /** * 链表节点，平凡无奇 * @param * @param */ static class Node, V> { int hash; K key; V value; Node<K, V> next; public Node(int hash, K key, V value, Node<K, V> next) { this.hash = hash; this.key = key; this.value = value; this.next = next; } } 跳表节点，在通用实现中跳表节点分成了三大类：头索引节点、索引节点、普通节点，让我们仔细分析一下。 继续下面的内容，请先忘掉上面的三种节点，否则你是很难看懂的，trust me! 还是先拿一张图来对照着来：
首先，我们把这张图压扁，是不是就只有一个一个的节点连成一条线了，也就是单链表结构： static class SkiplistNode, V> { int hash; K key; V value; Node<K, V> next; } 然后，随便找一个节点，把它拉起来，比如3这个元素，首先，它有一个高度，这里它的高度为2，并且，每一层的这个3都有一个向右的指针(忘掉之前的三种节点类型)，对不对，所以，这里把next废弃掉，变成nexts，记录每一层的这个3的下一个元素是谁： static class SkiplistNode, V> { int hash; K key; V value; int maxLevel; Node<K, V>[] nexts; } OK，不知道你理解了没有，我们试着按这种数据结构重画上面的图：
通过这种方式，就把上面三种类型的节点成功地变成了一个大节点，这个节点是有层高的，且每层都有一个向右的指针。 让我们模拟一下查找的过程，比如，要查询8这个元素，只需要从头节点的最高层，往右到6这个节点，6在2层向右为空了，所以转到1层，向右到7这个节点，7再向右看一下，是9，比8大，所以7向下到0层，再向右，找到8，所以，整个走过的路径为：h(2)->6(2)->6(1)->7(1)->7(0)->8(0)。 好了，原理讲完了，让我们看实现，先来个简单的。 跳表的查询元素 不再区分索引节点和普通节点后，一切都将变得简单，无脑向右，再向下，再向右即可，代码也变得非常简单。 public V findValue(K key) { int level = this.maxLevel; SkiplistNode<K, V> q = this; int c; // i--控制向下 for (int i = (level - 1); i >= 0; i--) { while (q.nexts[i] != null && (c = q.nexts[i].key.compareTo(key)) <= 0) { if (c == 0) { // 找到了返回 return q.nexts[i].value; } // 控制向右 q = q.nexts[i]; } } return null; } 跳表的添加元素 添加元素，同样变得要简单很多，一切尽在注释中，不过，彤哥写这篇文章的时候才发现下面的代码中有个小bug，看看你能不能发现^^ （编辑：应用网_阳江站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
