哪个是实现 trie 节点的子节点的更好实现 - 数组或哈希图？

Question

我正在阅读有关特里数据结构的内容，并找到了两个实现来实现特里节点中的子节点。以下是两种实现的详细信息：-

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

2) HashMap 已被用于存储以字符为键、以 Trie 节点为值的 trie 节点的子节点。

请让我知道哪种实现更好，为什么？

Answer 1

这取决于内存和速度之间的通常权衡。

如果您的字符串很短并且没有内存问题，那么当然可以选择数组。这样您的搜索速度就会更快。如果你的字母均匀分布在单词中也很好。

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

数组比 HashMap 更快，但可能会消耗更多内存 - 但这不是必需的。想象一下，你的词袋包含所有可能的 26^N 个长度为 N 的单词，这些单词可以由 26 个字母组成。那么 HashMap 会更慢并且消耗更多的内存。