6

通过 trie 映射，我的意思是关联数组，其中有效负载存储在trie而不是哈希表中。

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

在我看来，这在编码小对象时会使用更多的内存（即使你只允许键中的小写字母字符，它是每个节点 26 个指针，并且每个键通常是多个节点），但从好的方面来说，你永远不必担心调整大小。为什么哈希图如此普遍，但我从未见过特里图？

4

2 回答 2

12

以防万一您是 Scala 程序员，TrieMap 是“哈希数组映射 trie 的并发线程安全无锁实现”。目前 Java 标准库中没有。

于 2015-03-19T22:50:40.883 回答
9

哈希映射比 trie 映射更常见，因为它们更通用：它们可以用于任何可哈希的对象，而 trie 则适用于序列。哈希表在常见实现中也具有更好的引用局部性，因为它们将元素存储在一起。

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

于 2011-04-08T08:30:23.853 回答