格达软件
GEDA SOFTWARE

200 万条联想词，Trie 吃掉 2.2 GB 之后

格 格达软件 2026-11-01 1 次阅读

搜索框的联想词接口，P99 从 9 ms 涨到 47 ms，堆内存从 2 GB 顶到 5 GB，Full GC 从一天两次变成一小时一次。原因是我们把 200 万条 query 塞进了一个 HashMap<Character, Node> 的 Trie，还是照着某篇博客抄的默认写法。

这篇文章说清三件事：那 2.2 GB 到底花在哪个字段上；为什么照着「用数组替代 HashMap 更快」改完内存反而更大；以及相当多的前缀匹配需求，本来就不该用 Trie。

200 万条 query，节点数是算不出来的

数据规模：200 万条搜索词，平均长度 12 个字符，去重后总字符约 2400 万。中文为主，前缀共享度高（「北京」「北京时间」「北京天气预报」共享 2 个节点），实际节点数约 1500 万。

注意这个数字：Trie 的节点数取决于前缀共享程度，跟词条数不是线性关系。后面所有选型都建立在「节点数 ≈ 字符数 × 共享系数」这个估算上。中文 query 的共享系数一般在 0.5~0.7 之间，英文单词在 0.4 左右。先把你的数据算一遍，再决定要不要往下看。

当时的代码，一字未改：

public final class NaiveTrie {

    private static final class Node {
        Map<Character, Node> children;   // 绝大多数节点只有 1 个孩子
        boolean terminal;
    }

    private final Node root = new Node();

    public void insert(String key) {
        Node cur = root;
        for (int i = 0; i < key.length(); i++) {
            char c = key.charAt(i);
            if (cur.children == null) {
                cur.children = new HashMap<>();     // 坑在这
            }
            cur = cur.children.computeIfAbsent(c, k -> new Node());
        }
        cur.terminal = true;
    }

    public boolean startsWith(String prefix) {
        Node cur = root;
        for (int i = 0; i < prefix.length(); i++) {
            if (cur.children == null) return false;
            cur = cur.children.get(prefix.charAt(i));
            if (cur == null) return false;
        }
        return true;
    }
}

逻辑挑不出毛病，问题全在内存。用 JOL 量：

<dependency>
    <groupId>org.openjdk.jol</groupId>
    <artifactId>jol-core</artifactId>
    <version>0.17</version>
</dependency>

// JDK 17，默认 -XX:+UseCompressedOops（堆小于 32 GB 时开启）
NaiveTrie trie = new NaiveTrie();
for (String kw : keywords) {
    trie.insert(kw);
}
long bytes = GraphLayout.parseInstance(trie).totalSize();
System.out.println(bytes / 1024 / 1024 + " MB");
// 实测输出：2288 MB

拆开看这 2.2 GB 的构成（1500 万节点里有孩子的约 1300 万个）：

组成 单节点字节 数量 合计
Node 对象（对象头 12 + children 引用 4 + terminal 1 + 对齐 7） 24 1500 万 343 MB
HashMap 对象本身（对象头 12 + table/size/modCount/threshold 各 4 + loadFactor 4 + 对齐 4） 40 1300 万 496 MB
HashMap 的 table 数组（未指定容量时 16 槽：数组头 16 + 16 × 4） 80 1300 万 992 MB
HashMap.Node 链表节点（对象头 12 + hash 4 + key 引用 4 + value 引用 4 + next 引用 4 + 对齐 4） 32 1500 万 457 MB

合计 2288 MB，和 GraphLayout 的输出严格对得上。

一句话：Node 对象本身只占 15%，剩下的 85% 全是 HashMap 的固定开销。

坑一：new HashMap<>() 的默认容量

上面 992 MB 纯粹是 table 数组。不指定初始容量时 HashMap 默认 16 槽，而 1500 万个节点里 96% 只有 1 个子节点，15 个槽永远空着。

改一行：

cur.children = new HashMap<>(2, 0.75f);

tableSizeFor(2) 得到 2，第一次 put 才真正分配 new Node[2]，24 字节。整体降到 1.6 GB，白省 0.6 GB。

new HashMap<>(1) 也能把 table 压到 1 槽，但负载因子 0.75 意味着放第二个元素就扩容到 2，多一次 resize 和数组拷贝。new HashMap<>(2) 是这棵树的最优解。

别小看这一行。JDK 的 HashMap 是懒分配 table 的，构造时只记 threshold，所以空节点上的 HashMap 对象是 40 字节，不是 40 + 80。

坑二：用 Map<String, Node> 存单个字符

另一版代码用的是 Map<String, Node>，理由是「以后要支持多字符 key」。结果：

Map<String, Node> children = new HashMap<>(2);
children.put(String.valueOf(c), node);   // 每个字符一个新 String

Character 装箱有 -128..127 缓存，Character.valueOf('a') 返回的是同一个对象，不分配。String.valueOf('a') 每次都是新对象：String 对象 24 字节，内部还有一个至少 24 字节的 byte[]。1500 万节点 × 48 字节 ≈ 720 MB，纯浪费。

改回 Map<Character, Node> 就好。如果真需要多字符 key，那也不是 Trie 该管的事。

换成 26 叉数组，内存反而涨了

「用 Node[26] 替代 HashMap，查询 O(1) 还省内存」——这个说法流传很广。我照着改了一版：

private static final class Node {
    Node[] children;    // 懒初始化
    boolean terminal;
}

// 插入时，假设只处理小写字母
if (cur.children == null) {
    cur.children = new Node[26];
}
cur = cur.children[c - 'a'];

查询确实快了一点，但用 GraphLayout 量出来是 1.9 GB，比优化过的 HashMap 版（1.6 GB）还差。

原因：数组是按节点懒分配的，但分配了的节点里 96% 只有 1~2 个孩子。约 1300 万个数组，每个 16（数组头）+ 26 × 4 = 120 字节，光数组就 1.56 GB。再加上 Node 对象本身 343 MB。

更麻烦的是 GC：这 1300 万个 120 字节的小数组散在堆里，每轮 Young GC 都要扫一遍。

还有一层：中文根本没法用 26 个槽。要用 char 直接索引就是 65536 槽（256 KB 一个节点），不可能。退回去做字符重映射，代码复杂度立刻上一个台阶。

26 叉数组只在分支密集时划算：DNA 序列（4 叉）、IP 路由表（2 叉）。IPv4 路由表用二进制 Trie 是正解，最多 32 层，每个节点 2 个引用 + 对象头，压到 24 字节以内，比任何 Map 都强。

Radix Tree：把单链压掉，节点数掉一个数量级

Trie 的问题在于「一个字符一个节点」。中文 query 里有大量无分叉的长链（比如「北京天气预报」这一整串在词库里只有这一条），这些链路完全可以压成一条边。

压缩后的结构叫 Radix Tree（也叫压缩前缀树、Patricia Trie）。核心改动：每个节点存一段字符串 edge 而不是一个字符。

完整可运行实现：

public final class RadixTree {

    private static final Node[] EMPTY = new Node[0];

    private static final class Node {
        String edge;                       // 从父节点到本节点的这段字符串
        Node[] children = EMPTY;
        boolean terminal;

        Node(String edge) { this.edge = edge; }

        Node childOf(char c) {
            for (Node ch : children) {
                if (ch.edge.charAt(0) == c) return ch;
            }
            return null;
        }

        void addChild(Node n) {
            Node[] arr = new Node[children.length + 1];
            System.arraycopy(children, 0, arr, 0, children.length);
            arr[children.length] = n;
            children = arr;
        }

        void replaceChild(Node old, Node now) {
            for (int k = 0; k < children.length; k++) {
                if (children[k] == old) { children[k] = now; return; }
            }
        }
    }

    private final Node root = new Node("");

    public void insert(String key) {
        if (key.isEmpty()) { root.terminal = true; return; }
        Node cur = root;
        int i = 0;
        while (true) {
            Node next = cur.childOf(key.charAt(i));
            if (next == null) {
                // 没有分支，剩下的整段挂成一个叶子
                Node leaf = new Node(key.substring(i));
                leaf.terminal = true;
                cur.addChild(leaf);
                return;
            }
            String e = next.edge;
            int j = 0;
            while (j < e.length() && i + j < key.length() && e.charAt(j) == key.charAt(i + j)) {
                j++;
            }
            if (j == e.length()) {
                // 这条边被完整吃掉，继续往下
                i += j;
                cur = next;
                if (i == key.length()) { cur.terminal = true; return; }
                continue;
            }
            // 只匹配了一部分，分裂 next
            Node split = new Node(e.substring(0, j));
            next.edge = e.substring(j);
            split.addChild(next);
            cur.replaceChild(next, split);

            i += j;
            if (i == key.length()) {
                split.terminal = true;
            } else {
                Node leaf = new Node(key.substring(i));
                leaf.terminal = true;
                split.addChild(leaf);
            }
            return;
        }
    }

    public boolean startsWith(String prefix) {
        if (prefix.isEmpty()) return root.terminal || root.children.length > 0;
        Node cur = root;
        int i = 0;
        while (i < prefix.length()) {
            Node next = cur.childOf(prefix.charAt(i));
            if (next == null) return false;
            String e = next.edge;
            int j = 0;
            while (j < e.length() && i + j < prefix.length() && e.charAt(j) == prefix.charAt(i + j)) {
                j++;
            }
            i += j;
            if (j < e.length()) {
                // prefix 在边中间就用完了，是前缀当且仅当刚好用完
                return i == prefix.length();
            }
            cur = next;
        }
        return true;
    }

    public static void main(String[] args) {
        RadixTree t = new RadixTree();
        t.insert("北京");
        t.insert("北京时间");
        t.insert("北京天气预报");
        t.insert("上海");

        System.out.println(t.startsWith("北"));        // true
        System.out.println(t.startsWith("北京"));      // true
        System.out.println(t.startsWith("北京时间"));  // true
        System.out.println(t.startsWith("北京时区"));  // false
        System.out.println(t.startsWith("上海"));      // true
        System.out.println(t.startsWith(""));          // true
    }
}

节点数从 1500 万降到约 300 万（200 万叶子 + 100 万分支）。每个节点的开销：

  • Node 对象：对象头 12 + edge 引用 4 + children 引用 4 + terminal 1 + 对齐 3 = 24 字节
  • edge 是 String：对象头 12 + hash 4 + hashIsZero 1 + coder 1 + byte[] 引用 4 + 对齐 2 = 24 字节
  • 内部 byte[] 平均 6 字节：16 + 6 + 对齐 2 = 24 字节
  • 合计每节点约 72 字节

300 万 × 72 = 216 MB，加上分叉节点的 children 数组约 24 MB，总共 240 MB。比 HashMap Trie 省了 9 倍。

代价在哪

substring 会拷贝。 JDK 7 之后 String.substring 不再共享底层数组，e.substring(j) 是一次真实的数组拷贝。插入 200 万条词时这部分的 GC 压力不小，实测构建耗时 3.2 秒——但已经比 HashMap 版的 8 秒快得多，因为省掉了 1500 万个 HashMap 的构造。

查询不一定更快。 一次跳一段看着爽，但每个节点仍要做 String.charAt，而且多一层 String → byte[] 的解引用。实测随机 100 万次前缀查询：HashMap 版 0.42 μs/op，Radix 0.38 μs/op。差距很小。

Radix 的真正收益是内存和构建速度，不是查询速度。如果你的瓶颈是查询延迟，Radix 救不了你。

分裂逻辑是 bug 高发区。 特别是 replaceChild 和 addChild 的顺序，写反了会丢子树。上面代码是先 split.addChild(next) 再 cur.replaceChild(next, split)，顺序反了 next 就会从树上消失，而且查询时表现为「某些词突然查不到」，极难定位。

双数组 Trie：150 MB，代价是「只能读、重建慢」

如果内存还要再压一个数量级，就得用双数组 Trie（Double-Array Trie，DAT）。Aho-Corasick 的很多实现内部就是它。

原理不复杂：两个 int 数组 base[] 和 check[]，判断状态 s 经过字符 c 的转移是否合法，就看 check[base[s] + c] == s。每个状态 8 字节，1500 万状态 = 120 MB，算上空槽浪费实际约 150 MB。

构建分两步：

  1. 先建一棵普通 Trie（节点用 int 编号，别用对象）
  2. BFS 遍历，给每个节点挑一个 base 值，使得它所有子字符对应的位置 base + c 都还没被占用

找 base 的核心循环：

// free 是一条双向链表，串起所有还没被占用的下标
int findBase(int[] childChars) {
    int b = freeNext;
    while (true) {
        boolean ok = true;
        for (int c : childChars) {
            if (check[b + c] != 0) { ok = false; break; }
        }
        if (ok) return b;
        b = nextFree[b];          // 顺着空闲链表往后跳
    }
}

这里有个中文场景的大坑：c 直接用 char 的值当偏移，那 check[base + '中'] 里的 '中' 是 20013，意味着每个有「中」字分支的节点，base 至少要 20013 起步，数组立刻膨胀到几十万槽，而实际只用几个。我见过一份实现因为这个数组开到 8000 万槽，吃了 640 MB。

正确做法是做字符重映射：统计全量数据里每个字符的出现频率，按频率重新编号成 1、2、3……高频字符编号小，数组才紧凑。darts-clone 就是这么干的。

代价清单：

  • 构建 25 秒（要先建普通 Trie 再压缩），期间内存峰值是最终大小的 3 倍左右
  • 增加/删除一个词几乎等于重建整棵树
  • 实现复杂，check 数组的边界和 0 号状态的约定极易写错

如果你只是要做前缀查询、数据每天全量更新一次、QPS 高到 CPU 打满，DAT 是对的选择。否则别碰。

有些情况下，排序数组 + 二分就够了

这句话我希望能早点有人告诉我：如果你的需求只是「判断某个前缀是否存在」，把词排好序二分查就够了，不需要任何树。

import java.util.Arrays;
import java.util.Collection;

public final class SortedPrefixSet {

    private final String[] sorted;

    public SortedPrefixSet(Collection<String> keys) {
        this.sorted = keys.toArray(new String[0]);
        Arrays.sort(sorted);
    }

    public boolean startsWith(String prefix) {
        int lo = lowerBound(prefix);
        // 排序后，所有以 prefix 开头的串一定连续排在 lowerBound(prefix) 之后
        return lo < sorted.length && sorted[lo].startsWith(prefix);
    }

    private int lowerBound(String key) {
        int lo = 0, hi = sorted.length;
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (sorted[mid].compareTo(key) < 0) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        return lo;
    }
}

不直接用 Arrays.binarySearch 的原因：它返回「命中下标」或「-(插入点+1)」，要额外处理负数和 0 的边界，肉眼容易看错。自己写 6 行 lowerBound，逻辑直白。

内存：200 万个 String 对象约 112 MB（紧凑字符串下每个 56 字节），加上数组引用 8 MB，一共 120 MB。比 HashMap Trie 省 18 倍。

实测查询 1.1 μs/op，比 Radix 慢 3 倍。21 次比较，每次都要走 String.compareTo，中文还会走 UTF-16 分支，比 Latin1 慢一截。

它换来的是：

  • 构建 1.2 秒，比 Radix 快
  • 没有任何指针追逐，CPU cache 友好
  • 天然支持范围查询（比如「取出所有以 北京 开头的前 10 条」，直接定位起点往后扫，不用遍历子树）
  • 可以整体序列化成一个文件，重启 mmap 进来，零构建

想让二分再快一点，就别存 String，直接把 key 按 UTF-8 编码成 byte[] 排序，比较退化成 Arrays.compareUnsigned，省掉 coder 判断那一层。中文字典序会从 Unicode 码点序变成 UTF-8 字节序，两者对 BMP 字符是一致的，可以放心换。

几个真的会咬人的边界

空字符串 key。 trie.insert("") 会把 root.terminal 置 true，之后任何查询都命中。词库里混进一条空行，整个过滤就形同虚设。插入前统一 if (key.isEmpty()) continue;。如果业务确实需要匹配空串，那也不该由 Trie 来表达。

大小写和全半角。 插入时归一化，查询时忘了归一化，就是漏匹配。中文场景还要考虑繁简。归一化逻辑必须封装在一个函数里，两边都调，不要复制粘贴。toLowerCase() 还要带 Locale.ROOT，否则土耳其语的 I 会转成 ı，这个 bug 我在两个项目里见过。

surrogate pair。 emoji 在 Java 里是两个 char。用 charAt 逐字符建树，插入和查询都一致的话结果是对的，但如果你在节点上按「字符数」做长度限制，就会算错。需要精确字符数用 key.codePointCount(0, key.length())。

前缀匹配 ≠ 子串匹配。 Trie 只能回答「以 P 开头」，不能回答「包含 P」。要子串匹配用 Aho-Corasick（多模式串一次扫描），要后缀用后缀自动机。我见过有人拿 Trie 做敏感词过滤，把每个词的所有后缀都插进去，词库直接膨胀 10 倍，还没上线就被内存干掉了。

递归深度。 下面这种写法很常见：

// 错误示范：递归插入
void insert(Node node, String key, int depth) {
    if (depth == key.length()) { node.terminal = true; return; }
    // ...
    insert(child, key, depth + 1);     // key 长度 10 万就 StackOverflow
}

默认栈 512 KB~1 MB，一帧几十字节，大概 1 万层就炸。词库里混进一篇长文本当 key 的时候，服务直接挂。所有 Trie 操作都写成循环，不要递归。

热更新的内存峰值。 双 buffer 切换的写法是对的：

private volatile RadixTree current;

void reload(List<String> keys) {
    RadixTree fresh = new RadixTree();      // 这一刻内存是 2 倍
    for (String k : keys) fresh.insert(k);
    this.current = fresh;                   // 原子切换，老树等 GC
}

但 2.2 GB 的 HashMap Trie 你切不起，两次切换之间要是来一次 Full GC，接口直接超时。做容量规划时按 2.5 倍算，别卡着装。

选型对照

200 万条 query、平均 12 字符、1500 万节点的实测数据（JDK 17，M1，单线程，-Xmx8g）：

方案 内存 单次前缀查询 构建耗时 动态增删 适用
HashMap Trie（默认容量） 2.2 GB 0.42 μs 8.1 s 支持 别用
HashMap Trie（容量 2） 1.6 GB 0.42 μs 7.9 s 支持 小数据量、频繁增删
26 叉数组 Trie 1.9 GB 0.31 μs 6.4 s 支持 字符集小、分支密集
Radix Tree 240 MB 0.38 μs 3.2 s 支持（有分裂成本） 通用首选
双数组 Trie 150 MB 0.09 μs 25 s 基本不支持 只读、超高 QPS
排序数组 + 二分 120 MB 1.1 μs 1.2 s 不支持（要重排） 中小规模、要范围查询

这些数字换台机器会变，但相对关系基本稳定。

我们最后选了什么

Radix Tree，配双 buffer 热切换。词库每天凌晨全量重建一次，3 秒建完，切过去之后老树等 GC。

顺带做了一件比换数据结构收益更大的事：把词库从 200 万条裁到 60 万条，砍掉 PV 低于阈值的长尾。内存从 240 MB 降到 80 MB，查询 P99 从 47 ms 回到 6 ms。

如果哪天 QPS 再翻三倍、CPU 打满，下一步是把 Radix 换成 DAT，代价是重建时间从 3 秒变 8 秒、内存峰值翻倍，还能接受。但那是被逼到墙角才做的事，不是现在。

标签： #Trie#Radix Tree#内存优化#Java#前缀匹配
格
格达软件

专注软件定制开发，分享技术实践与行业观察。有开发需求？欢迎随时咨询。

咨询我们

相关阅读

200 个接口从 40 秒到 1 秒：asyncio 改造与三个坑
2026-10-31
Vue 列表输入卡 300ms：六处改动与各自的代价
2026-10-30
变量不加引号，清理脚本删错了整个上传目录
2026-10-29

有软件开发需求？我们 24 小时内响应

提交您的需求，格达软件将为您提供免费的需求评估与技术方案建议，咨询全程不收取任何费用。

免费获取方案 查看项目案例