3、词典构建：哈希表实现词典、Trie树实现词典、双数组Trie树（DAT）的原理与实现

词典，说白了就是倒排索引的“门牌号系统”。你想想看，用户搜一个词，你得先知道这个词在不在你的词典里，在的话，它对应的倒排列表在哪。这个查找速度，直接决定了搜索引擎的响应时间。我个人习惯把词典构建看作是整个索引系统的“咽喉”，这里卡住了，后面再优化都白搭。

今天咱们就聊聊三种主流的词典实现方式：哈希表、Trie树，还有双数组Trie树（DAT）。我会结合我踩过的坑，把它们的原理和实现细节掰开揉碎了讲。

3.1 哈希表实现词典：简单粗暴，但有代价

哈希表实现词典，是最直观的思路。把每个词条通过哈希函数映射到一个固定大小的数组里，查找时间复杂度是O(1)。听起来很完美，对吧？

原理其实很简单：

  • 你有一个词条，比如“搜索引擎”。
  • 用一个哈希函数（比如BKDRHash）算出它的哈希值。
  • 哈希值对数组长度取模，得到存储位置。
  • 如果位置被占了（哈希冲突），就用链地址法或者开放地址法解决。

我在项目中遇到过一个问题：词典里存了上千万个词条，哈希表的内存占用直接飙到了几个GB。为什么会这样？因为哈希表为了保证查找效率，负载因子通常控制在0.75以下，这意味着有25%以上的内存是闲置的。

核心痛点：哈希表无法支持前缀匹配。用户输入“人工”，你想提示“人工智能”、“人工神经网络”，哈希表就无能为力了。它只能做精确匹配。

下面是一个简单的哈希表实现示例：

#include <string>
#include <vector>
#include <list>

class HashDict {
private:
    static const int TABLE_SIZE = 1000000;
    std::vector<std::list<std::pair<std::string, int>>> table;

    size_t hash(const std::string& key) {
        size_t h = 0;
        for (char c : key) {
            h = h * 131 + c;  // BKDRHash
        }
        return h % TABLE_SIZE;
    }

public:
    HashDict() : table(TABLE_SIZE) {}

    void insert(const std::string& word, int postings_offset) {
        size_t idx = hash(word);
        table[idx].push_back({word, postings_offset});
    }

    int lookup(const std::string& word) {
        size_t idx = hash(word);
        for (auto& pair : table[idx]) {
            if (pair.first == word) {
                return pair.second;
            }
        }
        return -1;  // 没找到
    }
};

我的建议：如果词典规模在百万级以下，且不需要前缀查询，哈希表是够用的。但一旦上了千万级，或者需要自动补全功能，你就得考虑其他方案了。

3.2 Trie树实现词典：空间换时间，前缀查询利器

Trie树，也叫字典树，是解决前缀匹配问题的经典方案。它的核心思想是：利用字符串的公共前缀来减少查询时间。

原理是这样的：

  • 每个节点代表一个字符。
  • 从根节点到某个节点的路径，拼接起来就是一个词条。
  • 查找“人工”时，你只需要沿着根→人→工的路径走，时间复杂度是O(L)，L是词条长度。

我记得第一次用Trie树做词典时，觉得它太优雅了。但很快我就发现了问题——内存爆炸。每个节点都要存26个（或更多）子节点指针，如果词典包含中文，每个节点可能要存几千个可能的字符，这谁受得了？

避坑指南：我曾经在一个中文分词项目里用Trie树存了50万个词条，结果内存占用超过了2GB。后来我改用双数组Trie树，内存直接降到了200MB以下。所以，纯Trie树只适合小规模词典，或者字符集很小的场景（比如英文小写字母）。

下面是一个简化的Trie树实现：

class TrieNode {
public:
    TrieNode* children[26];  // 假设只有小写字母
    bool is_end;
    int postings_offset;

    TrieNode() : is_end(false), postings_offset(-1) {
        for (int i = 0; i < 26; i++) {
            children[i] = nullptr;
        }
    }
};

class TrieDict {
private:
    TrieNode* root;

public:
    TrieDict() {
        root = new TrieNode();
    }

    void insert(const std::string& word, int offset) {
        TrieNode* cur = root;
        for (char c : word) {
            int idx = c - 'a';
            if (!cur->children[idx]) {
                cur->children[idx] = new TrieNode();
            }
            cur = cur->children[idx];
        }
        cur->is_end = true;
        cur->postings_offset = offset;
    }

    int lookup(const std::string& word) {
        TrieNode* cur = root;
        for (char c : word) {
            int idx = c - 'a';
            if (!cur->children[idx]) {
                return -1;
            }
            cur = cur->children[idx];
        }
        return cur->is_end ? cur->postings_offset : -1;
    }
};

3.3 双数组Trie树（DAT）：工业级的选择

双数组Trie树，说白了就是用两个数组来模拟Trie树的结构。它解决了Trie树内存占用过大的问题，同时保留了前缀查询的能力。这是目前搜索引擎和分词系统里最常用的词典实现方式。

核心原理：

  • 用两个数组：base[] 和 check[]。
  • base[i] 表示从状态i出发，经过某个字符转移到的状态基址。
  • check[i] 表示状态i的前驱状态，用来验证转移是否合法。
  • 转移公式：next_state = base[current_state] + code[char]，如果 check[next_state] == current_state，说明转移合法。

嗯，这里要注意：双数组Trie树的构建过程其实挺麻烦的。你需要给每个状态分配一个base值，保证所有子节点的转移不冲突。这本质上是一个子集覆盖问题，处理不好就会产生大量冲突。

我个人习惯：在构建DAT时，先对词条按首字母排序，然后逐层分配base值。这样可以减少冲突的概率。如果遇到冲突，就尝试调整base值，直到所有子节点都能找到空位。

下面是一个简化的DAT实现：

#include <vector>
#include <string>
#include <algorithm>

class DoubleArrayTrie {
private:
    std::vector<int> base;
    std::vector<int> check;
    std::vector<int> postings_offset;  // 存储倒排列表偏移量

    int allocate_base(const std::vector<int>& children) {
        // 找一个base值，使得所有子节点都不冲突
        int b = 1;
        while (true) {
            bool ok = true;
            for (int child : children) {
                int next = b + child;
                if (next >= (int)base.size()) {
                    base.resize(next + 1, 0);
                    check.resize(next + 1, -1);
                    postings_offset.resize(next + 1, -1);
                }
                if (check[next] != -1) {
                    ok = false;
                    break;
                }
            }
            if (ok) break;
            b++;
        }
        return b;
    }

public:
    DoubleArrayTrie() {
        base.push_back(0);
        check.push_back(-1);
        postings_offset.push_back(-1);
    }

    void insert(const std::string& word, int offset) {
        int state = 0;
        for (int i = 0; i < (int)word.size(); i++) {
            int code = word[i] - 'a' + 1;  // 字符编码从1开始
            int next = base[state] + code;
            
            if (next >= (int)base.size()) {
                base.resize(next + 1, 0);
                check.resize(next + 1, -1);
                postings_offset.resize(next + 1, -1);
            }

            if (check[next] == -1) {
                // 新节点，需要分配base值
                check[next] = state;
                // 如果是最后一个字符，设置偏移量
                if (i == (int)word.size() - 1) {
                    postings_offset[next] = offset;
                } else {
                    // 预分配一个简单的base值
                    base[next] = 1;
                }
            }
            state = next;
        }
    }

    int lookup(const std::string& word) {
        int state = 0;
        for (int i = 0; i < (int)word.size(); i++) {
            int code = word[i] - 'a' + 1;
            int next = base[state] + code;
            
            if (next >= (int)base.size() || check[next] != state) {
                return -1;  // 没找到
            }
            state = next;
        }
        return postings_offset[state];
    }
};

我的经验：DAT的构建速度比查询速度慢得多。在实际项目中，我通常会把构建好的DAT序列化到磁盘，下次启动时直接加载，避免重复构建。另外，DAT对中文支持很好，因为中文字符的Unicode编码范围很大，但DAT的数组索引是连续的，所以内存利用率很高。

3.4 三种方案的对比与选择

说了这么多，到底该选哪种？我整理了一个对比表，方便你决策：

特性 哈希表 Trie树 双数组Trie树
查找时间复杂度 O(1) 平均 O(L) O(L)
内存占用 中等（有闲置槽位） 高（指针开销大） 低（紧凑数组）
前缀查询 不支持 支持 支持
构建速度 快 快 慢（需要冲突处理）
适用场景 小规模词典，精确匹配 小规模词典，前缀匹配 大规模词典，工业级应用

最后提醒一句：不要盲目追求“最先进”的方案。如果你的词典只有几千个词条，哈希表完全够用，没必要上DAT。我见过有人用DAT存了100个停用词，那纯粹是杀鸡用牛刀。选方案之前，先搞清楚你的数据规模和业务需求。

好了，词典构建这块就聊到这儿。下一章咱们会讲倒排列表的压缩与存储优化，到时候再聊聊怎么把几亿个文档ID塞进有限的内存里。

← 上一章 📖 返回目录 下一章 →