Class Trie<V>

java.lang.Object
cloud.opencode.base.collections.tree.Trie<V>
Type Parameters:
V - value type | 值类型
All Implemented Interfaces:
Serializable
public final class Trie<V> extends Object implements Serializable
Trie - Prefix Tree Implementation Trie - 前缀树实现

A trie (prefix tree) for efficient string operations.

用于高效字符串操作的字典树（前缀树）。

Features | 主要功能:

  • Fast prefix matching - 快速前缀匹配
  • Autocomplete support - 自动完成支持
  • Memory efficient for common prefixes - 共同前缀的内存高效

Usage Examples | 使用示例:

Trie<Integer> trie = Trie.create();
trie.put("hello", 1);
trie.put("help", 2);
trie.put("world", 3);

Integer value = trie.get("hello");  // 1
boolean hasPrefix = trie.hasPrefix("hel");  // true
List<String> words = trie.keysWithPrefix("hel");  // ["hello", "help"]

Performance | 性能特性:

  • put: O(m) where m is key length - put: O(m) 其中 m 是键长度
  • get: O(m) - get: O(m)
  • hasPrefix: O(m) - hasPrefix: O(m)

Security | 安全性:

  • Thread-safe: No - 线程安全: 否
  • Null-safe: Values can be null, keys cannot - 空值安全: 值可以为 null，键不能
Since:
JDK 25, opencode-base-collections V1.0.0
Author:
Leon Soo www.LeonSoo.com
See Also:

  • Method Details

    • create

      public static <V> Trie<V> create()
      Create an empty Trie. 创建空 Trie。
      Type Parameters:
      V - value type | 值类型
      Returns:
      new empty Trie | 新空 Trie

    • put

      public V put(String 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(String key)
      Get the value for a key. 获取键对应的值。
      Parameters:
      key - the key | 键
      Returns:
      the value or null | 值或 null

    • containsKey

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

    • remove

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

    • hasPrefix

      public boolean hasPrefix(String prefix)
      Check if any key starts with the prefix. 检查是否有键以该前缀开头。
      Parameters:
      prefix - the prefix | 前缀
      Returns:
      true if has prefix | 如果有前缀则返回 true

    • keysWithPrefix

      public List<String> keysWithPrefix(String prefix)
      Get all keys with the prefix. 获取所有具有该前缀的键。
      Parameters:
      prefix - the prefix | 前缀
      Returns:
      list of keys | 键列表

    • keys

      public List<String> keys()
      Get all keys. 获取所有键。
      Returns:
      list of keys | 键列表

    • longestPrefixOf

      public String longestPrefixOf(String input)
      Get the longest prefix of the input that is in the trie. 获取输入中在字典树中的最长前缀。
      Parameters:
      input - the input string | 输入字符串
      Returns:
      the longest prefix | 最长前缀

    • size

      public int size()
      Return the size of this trie. 返回此字典树的大小。
      Returns:
      the size | 大小

    • isEmpty

      public boolean isEmpty()
      Check if this trie is empty. 检查此字典树是否为空。
      Returns:
      true if empty | 如果为空则返回 true

    • clear

      public void clear()
      Clear this trie. 清空此字典树。