哪一个更好的实现来实现一个trie节点的子节点 - 数组或hashmap？

Question

我正在阅读有关trie数据结构，并找到两个实现来实现trie节点中的子节点。以下是两个实现的细节： -

1）长度为26的Trie节点数组已被用于存储trie节点的子节点。

2）HashMap已被用于存储trie节点的子节点，其中字符作为键，Trie节点作为值。

请让我知道哪个实施更好，为什么？

Answer 1

这取决于 - 内存和速度之间的平常折衷。

如果你的字符串很短，并且没有内存问题，那么当然就是数组。这样您可以更快地进行搜索。如果你的信件均匀分布在单词中，这也很好。

如果你的字符串可能很大，并且有一些字母很少出现，那么去哈希映射。这样你就不会占用太多未使用的内存。如果你的字母比26个字母大得多，这也会更好。

数组速度更快，但可能会消耗比HashMap更多的内存 - 但不是必需的。想象一下，你的单词包含了所有可能由26个字母组成的长度为N的26^N个单词。然后HashMap会变得更慢并消耗更多的内存。

Answer 2

有用于索引树节点的两个非常常见的结构：

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节点通常少于5个子节点，数组分配开销比数组保持的数据大。通过链表安排，您不会浪费任何内存。

顺序搜索小孩子列表的速度非常快，因为要搜索的孩子的列表通常非常短，而且字母频率的分布通常很偏斜。也就是说，前两个孩子通常比其他孩子使用得更频繁。所以平均来说，你只需要搜索两个或三个子节点。

其中任何一个都可以节省大量的内存，这可以使程序更快。我的测试没有显示出与这些替代结构相比的明显性能。