实现Trie节点的子节点，使用数组还是哈希表哪个更好？

Question

我正在阅读有关trie数据结构的内容，发现两种实现方法可以用来实现trie节点中的子项。以下是这两种实现方法的详细信息：

1) 使用长度为26的trie节点数组来存储trie节点的子项。

2) 使用HashMap来存储trie节点的子项，其中字符作为键，trie节点作为值。

请告诉我哪种实现方法更好，为什么？

- ashisahu

---

我建议您实现它们并进行比较。 - wildplasser

注意：unordered_map所需的内存是array的5倍，而map所需的内存是array的6（至8）倍。请参见-https://dev59.com/iUIEtIcB2Jgan1znlxpN - Manohar Reddy Poreddy

Answer 1

这取决于内存和速度之间的通常权衡。如果您的字符串很短且没有内存问题，那么当然应该选择数组。这样可以使搜索更快。如果字母在单词中平均分布，则也很好。如果您的字符串很大并且有一些字母很少出现，则应选择哈希映射。这样您就不会占用太多未使用的内存。如果您的字母表比26个字母要大得多，则这也更好。数组比HashMap更快，但可能消耗更多的内存 - 但不是必需的。想象一下，您的单词袋包含所有可能的长度为N、由26个字母组成的26^N个单词。那么HashMap会比数组更慢，同时消耗更多的内存。

- dreamzor

---

以下是模糊的描述：“假设您的词袋包含所有可能的长度为 N 且由 26 个字母组成的 26^N 个单词。那么 HashMap 的速度会更慢，而且会消耗更多的内存。”请问这种情况的最好和最坏的情况分别是什么？在实践中，您真正发现的相对可比缓慢和内存成本是多少？ - Manohar Reddy Poreddy

Answer 2

用于Trie节点的两种结构非常常见：

CharNode
    char letter
    CharNode[26] children

CharNode
    char letter
    Dictionary<char, CharNode> children

这些方法可以很好地工作，但它们浪费了大量的内存，因为子节点列表非常稀疏。在我看来，两种方法都没有提供性能上的优势来抵消内存成本。我更喜欢使用：

CharNode
    char letter
    CharNode[] children

或者

CharNode
    char letter
    CharNode* firstChild
    CharNode* sibling

在第一种情况下，children数组的大小是可变的，只需容纳实际使用的孩子数量，并且孩子按最常用的字母排序。顺序搜索找到所需的子项。

在第二种情况下，您有一个儿童的链表，每个孩子都有一个兄弟指针。同样，孩子们根据频率在列表中排列。

我更喜欢第二种方法，因为在许多运行时环境中，分配数组的成本非常高。例如，在.NET中，数组分配开销大约为50个字节。考虑到Trie节点通常少于五个孩子，数组分配开销大于数组保存的数据。采用链接列表排列，不会浪费任何内存。

小孩子列表的顺序搜索非常快，因为要搜索的子节点列表通常非常短，字母频率的分布通常非常倾斜。也就是说，前两个孩子通常比其他孩子使用得更频繁。因此，平均而言，您只需要搜索两个或三个子节点。

这些方法都能节省大量内存，从而使程序更快。我的测试没有显示出采用这些备选结构会带来明显的性能损失。

- Jim Mischel

---

我不确定你使用的是哪种语言/实现方式，但为什么字典会浪费内存呢？它不是只有在添加新条目时才会填满吗？在您提出的方案中，不清楚如何跟踪最常用的字母。您是否需要额外的数据结构或附加字段来跟踪此信息？ - Lorenz Forvang

@LorenzForvang 字典的开销很大。例如，在 C# 中，字典中的每个键/值对都具有至少 16 个字节的开销。当你开始谈论数亿个节点时，这就变得昂贵了。最常用的字母在构建 trie 时被计算。我通常使用 trie 来构建静态 trie。但是你也可以在运行时执行它：你只需要跟踪字符频率即可。 - Jim Mischel

@JimMischel请分享一个“但是您也可以在运行时执行：您只需要跟踪字符频率”的实现。 - Manohar Reddy Poreddy

Answer 3

数组是经典的教科书实现，在默认选择中使用。

哈希表在字母表很大且实际使用的键的数量相对较小时，占用的内存较少。但哈希表本身的结构比数组占用更多的内存。因此这是一种权衡，并取决于实际trie的键。

每个子链接的访问速度几乎相同，为O(1)。

- leo leo