字典树（Trie）

一提到字符串相关的问题，尤其是涉及前缀匹配的，很多人的第一反应可能是哈希表，或者直接用字符串的 startsWith 方法循环遍历。这些方法当然可以，但一旦数据量上来，或者查询变得频繁，性能问题就暴露无遗了。今天，我们就从这个痛点出发，一步步揭开字典树的神秘面纱，看看它是如何优雅地解决这类问题的。

故事的开始：一个简单的需求

我们先来看一个具体的需求。假设我们正在开发一个搜索框的输入提示功能。我们需要实现这么几个 API：

1. insert(String word): 添加一个新的词到我们的词库里。

2. search(String word): 查询一个词是否完整地存在于词库中。

3. startsWith(String prefix): 查询词库中是否有以某个前缀开头的词。

比如，我们先 insert("apple")，然后 search("apple") 应该返回 true，但 search("app") 应该返回 false。而 startsWith("app") 应该返回 true，因为 "apple" 就是以 "app" 开头的。

解法一：头脑最直观的暴力解法 (HashSet)

遇到这种存和查的问题，我的第一反应通常是——上哈希！用一个 HashSet<String> 来存储我们所有的词。这个思路非常直接。

• insert(word): 直接 set.add(word)。时间复杂度 roughly a O(L)，L 是单词长度，因为要计算哈希值。

• search(word): 直接 set.contains(word)。时间复杂度也差不多是 O(L)。

• startsWith(prefix): 这个就尴尬了。HashSet 没办法高效处理前缀查询。唯一的办法就是把 Set 里的所有词都遍历一遍，对每个词都调用 word.startsWith(prefix) 方法。如果 Set 中有 N 个单词，平均长度为 L，前缀长度为 P，那么这个操作的时间复杂度就是 O(N * P)。

当 N 非常大时，这个 startsWith 的性能是灾难性的。显然，这个结构虽然简单，但并不是为前缀查询而生的。它把 "apple" 和 "apply" 当成了两个毫无关联的东西，浪费了它们共享前缀 "app" 这一重要信息。

解法二：正统的字典树（数组实现）

既然暴力解法的痛点在于没有利用好字符串的公共前缀，那我们就专门设计一个数据结构来解决这个问题。这就是字典树，也叫前缀树（Prefix Tree）。

它的核心思想是用空间换时间，把字符串的公共前缀合并到一条共享的路径上。

我们先来设计一下字典树的节点 Node。每个节点代表一个字符，它需要包含什么信息呢？

1. 指向下一个节点的指针: 一个字符后面可能跟很多种不同的字符。比如 'a' 后面可以是 'p'，也可以是 'b'。如果只考虑小写字母，那么一个节点最多有 26 个分支。我们可以用一个Node[] nexts = new Node[26]的数组来存储这些分支。nexts[0] 代表 'a'，nexts[1] 代表 'b'，以此类推。

2. 标识信息: 光有路径还不行。我们需要知道，当一个路径走完时，它到底是不是一个完整的单词。比如我们插入了 "apple"，路径 a->p->p->l->e 走完了，但 "app" 对应的路径也存在，我们怎么区分 "app" 不是一个独立的单词，而 "apple" 是呢？

   • 可以用一个 boolean isEnd 来标记。但这不够，如果我 insert("apple") 两次呢？search 应该还是 true。所以用一个整型 int end 来记录以这个节点结尾的单词数量更合适。

   • 另外，为了方便实现 startsWith，我们再加一个int pass。这个变量记录有多少个单词经过了这个节点。

所以，我们的节点结构就出来了：

class Node {
    public int pass; // 有多少个单词经过了这个节点
    public int end;  // 有多少个单词以这个节点结尾
    public Node[] nexts;

    public Node() {
        pass = 0;
        end = 0;
        // 假设只有小写字母 'a' - 'z'
        nexts = new Node[26];
    }
}

现在我们基于这个 Node 结构来实现我们的 API。

public class Trie1_Array {

    private Node root;

    public Trie1_Array() {
        root = new Node();
    }

    // 插入字符串
    public void insert(String word) {
        if (word == null) {
            return;
        }
        char[] chars = word.toCharArray();
        Node node = root;
        node.pass++; // 根节点的 pass 也增加
        for (char ch : chars) {
            int path = ch - 'a';
            if (node.nexts[path] == null) {
                node.nexts[path] = new Node();
            }
            node = node.nexts[path];
            node.pass++;
        }
        node.end++;
    }

    // 查询 word 是否存在
    public boolean search(String word) {
        if (word == null) {
            return false;
        }
        char[] chars = word.toCharArray();
        Node node = root;
        for (char ch : chars) {
            int path = ch - 'a';
            if (node.nexts[path] == null) {
                return false; // 路径不存在，肯定没有这个词
            }
            node = node.nexts[path];
        }
        return node.end > 0; // 必须是一个单词的结尾
    }

    // 查询是否有以 prefix 开头的词
    public boolean startsWith(String prefix) {
         if (prefix == null) {
            return false;
        }
        char[] chars = prefix.toCharArray();
        Node node = root;
        for (char ch : chars) {
            int path = ch - 'a';
            if (node.nexts[path] == null) {
                return false;
            }
            node = node.nexts[path];
        }
        // 只要路径存在即可，不要求是单词结尾
        // 甚至可以返回 pass 的值，表示有多少个单词以它为前缀
        return node.pass > 0;
    }

    // 我们再加一个删除操作，这是精髓
    public void delete(String word) {
        // 先确认这个词存在
        if (!search(word)) {
            return;
        }
        char[] chars = word.toCharArray();
        Node node = root;
        node.pass--;
        for (char ch : chars) {
            int path = ch - 'a';
            // 在向下走之前，先判断下一个节点的 pass 值
            // 如果减一后为0，说明没有其他单词共享这个分支了
            // 我们可以直接把这个分支砍掉，释放内存 (虽然Java有GC，但这是个好习惯)
            if (--node.nexts[path].pass == 0) {
                node.nexts[path] = null;
                return; // 后面的路径都不需要管了
            }
            node = node.nexts[path];
        }
        node.end--;
    }
}

分析一下： 这种实现方式，所有操作（插入、查询、前缀查询、删除）的时间复杂度都只跟要操作的字符串长度 L 相关，为 O(L)。这和暴力解法中 startsWith 的 O(N * P) 相比，是质的飞跃。

缺点也很明显：Node[] nexts = new Node[26] 这个数组写死了，只能处理小写字母。如果字符集很大，比如是全部 Unicode 字符，那这个数组就会非常巨大，而且大部分空间都是 null，造成巨大的浪费。

解法三：更通用的字典树（哈希表实现）

为了解决解法二的局限性，我们可以把固定大小的数组换成更灵活的数据结构，比如哈希表（HashMap）。

思路完全一样，只是节点的数据结构变了。

// 节点结构变化
class Node {
    public int pass;
    public int end;
    public HashMap<Character, Node> nexts; // 从数组变成了 HashMap

    public Node() {
        pass = 0;
        end = 0;
        nexts = new HashMap<>();
    }
}

public class Trie2_HashMap {

    private Node root;

    public Trie2_HashMap() {
        root = new Node();
    }

    public void insert(String word) {
        if (word == null) {
            return;
        }
        char[] chars = word.toCharArray();
        Node node = root;
        node.pass++;
        for (char ch : chars) {
            if (!node.nexts.containsKey(ch)) {
                node.nexts.put(ch, new Node());
            }
            node = node.nexts.get(ch);
            node.pass++;
        }
        node.end++;
    }

    // search 和 startsWith 的逻辑几乎一样，就是把数组索引变成 map.get
    public boolean search(String word) {
        if (word == null) {
            return false;
        }
        char[] chars = word.toCharArray();
        Node node = root;
        for (char ch : chars) {
            if (!node.nexts.containsKey(ch)) {
                return false;
            }
            node = node.nexts.get(ch);
        }
        return node.end > 0;
    }

    // ... 其他方法类似，只是把数组操作换成 HashMap 操作
}

分析一下：

• 优点：非常灵活。可以处理任何字符，不再局限于小写字母。当字符集很大但实际用到的分支很稀疏时，极大地节省了空间。

• 缺点：相比数组，HashMap 的常数时间会大一些（有哈希计算和可能的冲突处理），并且每个节点本身也会因为 HashMap 对象而占用更多的内存。

总结一下

今天我们从一个实际的前缀匹配需求出发，体验了三种不同的解题思路：

1. 暴力 HashSet：简单直观，适用于不需要前缀查询的场景。一旦涉及前缀，性能就成了瓶颈。

2. 数组实现的字典树：性能的王者。对于字符集固定且不大的情况（比如小写字母、数字），这是最优选择。用空间换来了极致的查询速度。

3. 哈希表实现的字典树：灵活性的代表。牺牲了一点点性能和节点内存，换来了对任意字符集的普适性。