哈希表为什么比字典树更好？

Question

6

通过trie map，我指的是一种关联数组，其中负载存储在trie中而不是哈希表中。

当我使用哈希映射/表时，我使用的键通常是字符串。使用哈希映射相比于使用一些基于trie的映射有什么优势？我已经阅读过哈希映射更快的文章，但在我的看来，一致的哈希函数必须检查(char)数组的每个元素以获取最终哈希值-只需遍历一次数组。在trie中，您同样需要遍历一次数组。

对我来说，这似乎会在编码小对象时使用更多内存（即使您仅允许在键中使用小写字母字符，也是每个节点26个指针，通常每个键都有多个节点），但好处是您永远不必担心调整大小。为什么哈希映射如此常见，但我从未见过trie map呢？

- Ramfjord

2个回答

9

哈希表比字典树更常用，因为它们更通用：可以让哈希表在任何可哈希的对象上工作，而字典树只能在序列上运行。在一般的实现中，哈希表也具有更好的局部引用性能，因为它们将元素紧密地存储在一起。

（严格来说，每个对象都是一个位序列，但是一个通用的字典树需要用户在将其存储在字典树之前对其进行序列化。与定义自定义哈希函数相比，这非常不方便。）

- Fred Foo

实际上，构建树的 tries 也是完全可能的。 - dfeuer

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Dan · Accepted Answer

如果您是Scala程序员，那么TrieMap就是“哈希数组映射trie的并发线程安全无锁实现”。目前Java标准库中没有这种实现。