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

/**   * 添加元素：   * 1. 未初始化，则初始化   * 2. 数组位置无元素，直接放入   * 3. 数组位置有元素：   *  1）如果是SkipListNode类型，按跳表类型插入元素   *  2）如果该位置元素的key值正好与要插入的元素的key值相等，说明是重复元素，替换后直接返回   *  3）如果是Node类型，按链表类型插入元素，且插入元素后判断是否要转换成跳表   * 4. 插入元素后，判断是否需要扩容   *   * @param key   * @param value   * @return   */ public V put(K key, V value) {     if (key == null || value == null) {         throw new NullPointerException();     }     int hash = hash(key);     Node<K, V>[] table = this.table;     if (table == null) {         table = resize();     }     int len = table.length;     int i = hash & (len - 1);     Node<K, V> h = table[i];     if (h == null) {         table[i] = new Node<>(hash, key, value, null);     } else {         // 出现了hash冲突         V old = null;         if (h instanceof SkiplistNode) {             old = (V) ((SkiplistNode)h).putValue(hash, key, value);         } else {             // 如果链表头节点正好等于要查找的元素             if (h.hash == hash && h.key.equals(key)) {                 old = h.value;                 h.value = value;             } else {                 // 遍历链表找到位置                 Node<K, V> q = h;                 Node<K, V> n;                 int binCount = 1;                 for(;;) {                     n = q.next;                     // 没找到元素                     if (n == null) {                         q.next = new Node<>(hash, key, value, null);                         if (++binCount>= SKIPLISTIFY_THRESHOLD) {                             skiplistify(table, hash);                         }                         break;                     }                      // 找到了元素                     if (n.hash == hash && n.key.equals(key)) {                         old = n.value;                         n.value = value;                         break;                     }                      // 后移                     q = n;                     ++binCount;                 }             }         }          if (old != null) {             return old;         }     }      // 需要扩容了     if (++size > threshold) {         resize();     }      return null; } 

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

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

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