太刺激了，面试官让我手写跳表，而我用两种实现方式吊打了TA！

// 往跳表中添加一个元素（只有头节点可调用此方法） private V putValue(int hash, K key, V value) {     // 1. 算出层数     int level = randomLevel();     // 2. 如果层数高出头节点层数，则增加头节点层数     if (level > maxLevel) {         level = ++maxLevel;         SkiplistNode<K, V>[] oldNexts = this.nexts;         SkiplistNode<K, V>[] newNexts = new SkiplistNode[level];         for (int i = 0; i < oldNexts.length; i++) {             newNexts[i] = oldNexts[i];         }         this.nexts = newNexts;     }     SkiplistNode<K, V> newNode = new SkiplistNode<>(hash, key, value, level);     // 3. 修正向右的索引     // 记录每一层最右能到达哪里，从头开始     SkiplistNode<K, V> q = this; //      int c;     // 好好想想这个双层循环，先向右找到比新节点小的最大节点，修正之，再向下，再向右     for (int i = (maxLevel - 1); i >= 0; i--) {         while (q.nexts[i] != null && (c = q.nexts[i].key.compareTo(key)) <= 0) {             if (c == 0) {                 V old = q.nexts[i].value;                 q.nexts[i].value = value;                 return old;             }             q = q.nexts[i];         }         if (i < level) {             newNode.nexts[i] = q.nexts[i];             q.nexts[i] = newNode;         }     }     return null; }  private int randomLevel() {     int level = 1;     int random = ThreadLocalRandom.current().nextInt();     while (((random>>>=1) & 1) !=0) {         level++;     }     return level; } 

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

下面我们再来看看SkiplistHashMap中的查询元素和添加元素。

SkiplistHashMap查询元素

其实，跳表的部分搞定了，SkiplistHashMap的部分就非常简单了，直接上代码：

public V get(K key) {     int hash = hash(key);     int i = (hash & (table.length - 1));     Node<K, V> p = table[i];     if (p == null) {         return null;     } else {         if (p instanceof SkiplistNode) {             return (V) ((SkiplistNode)p).findValue(key);         } else {             do {                 if (p.key.equals(key)) {                     return p.value;                 }             } while ((p=p.next) != null);         }     }     return null; } 

SkiplistHashMap添加元素

添加元素参考HashMap的写法，将添加过程分成以下几种情况：

1.始化，先初始化;

2.数组对应位置无元素，直接放入;

3.数组对应位置有元素，又分成三种情况：

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

4.插入元素后，判断是否需要扩容

上代码如下：

（编辑：应用网_阳江站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!