Class SkipList<K,V>

java.lang.Object
cloud.opencode.base.collections.tree.SkipList<K,V>
Type Parameters:
K - key type | 键类型
V - value type | 值类型
All Implemented Interfaces:
Serializable, Iterable<SkipList.Entry<K,V>>
public final class SkipList<K,V> extends Object implements Iterable<SkipList.Entry<K,V>>, Serializable
SkipList - Skip List Implementation SkipList - 跳表实现

A probabilistic data structure providing O(log n) search, insert, and delete.

提供 O(log n) 搜索、插入和删除的概率数据结构。

Features | 主要功能:

  • O(log n) operations - O(log n) 操作
  • Sorted order - 排序顺序
  • Range queries - 范围查询
  • Simpler than balanced trees - 比平衡树简单

Usage Examples | 使用示例:

SkipList<Integer, String> skipList = SkipList.create();
skipList.put(1, "one");
skipList.put(5, "five");
skipList.put(3, "three");

String value = skipList.get(3);  // "three"

// Iteration in sorted order - 按排序顺序迭代
for (SkipList.Entry<Integer, String> entry : skipList) {
    System.out.println(entry.getKey() + ": " + entry.getValue());
}

Performance | 性能特性:

  • put: O(log n) average - put: O(log n) 平均
  • get: O(log n) average - get: O(log n) 平均
  • remove: O(log n) average - remove: O(log n) 平均

Security | 安全性:

  • Thread-safe: No - 否
  • Null-safe: No (key must not be null) - 否（键不能为null）
Since:
JDK 25, opencode-base-collections V1.0.0
Author:
Leon Soo www.LeonSoo.com
See Also:

  • Method Details

    • create

      public static <K extends Comparable<? super K>, V> SkipList<K,V> create()
      Create an empty SkipList with natural ordering. 创建自然排序的空 SkipList。
      Type Parameters:
      K - key type | 键类型
      V - value type | 值类型
      Returns:
      new empty SkipList | 新空 SkipList

    • create

      public static <K,V> SkipList<K,V> create(Comparator<? super K> comparator)
      Create an empty SkipList with custom comparator. 创建自定义比较器的空 SkipList。
      Type Parameters:
      K - key type | 键类型
      V - value type | 值类型
      Parameters:
      comparator - the comparator | 比较器
      Returns:
      new empty SkipList | 新空 SkipList

    • put

      public V put(K key, V value)
      Put a key-value pair. 放入键值对。
      Parameters:
      key - the key | 键
      value - the value | 值
      Returns:
      the old value or null | 旧值或 null

    • get

      public V get(K key)
      Get the value for a key. 获取键对应的值。
      Parameters:
      key - the key | 键
      Returns:
      the value or null | 值或 null

    • containsKey

      public boolean containsKey(K key)
      Check if the key exists. 检查键是否存在。
      Parameters:
      key - the key | 键
      Returns:
      true if exists | 如果存在则返回 true

    • remove

      public V remove(K key)
      Remove a key. 移除键。
      Parameters:
      key - the key | 键
      Returns:
      the old value or null | 旧值或 null

    • size

      public int size()
      Return the size of this skip list. 返回此跳表的大小。
      Returns:
      the size | 大小

    • isEmpty

      public boolean isEmpty()
      Check if this skip list is empty. 检查此跳表是否为空。
      Returns:
      true if empty | 如果为空则返回 true

    • clear

      public void clear()
      Clear this skip list. 清空此跳表。

    • firstKey

      public K firstKey()
      Get the first (smallest) key. 获取第一个（最小）键。
      Returns:
      the first key | 第一个键

    • lastKey

      public K lastKey()
      Get the last (largest) key. 获取最后一个（最大）键。
      Returns:
      the last key | 最后一个键

    • iterator

      public Iterator<SkipList.Entry<K,V>> iterator()
      Specified by:
      iterator in interface Iterable<K>