我在哪里可以找到基于Trie的标准Map实现？

Question

我有一个Java程序,它存储了很多从Strings到各种对象的映射.

现在,我的选择是依赖哈希(通过HashMap)或二进制搜索(通过TreeMap).我想知道在流行的高质量馆藏图书馆中是否有一个高效且标准的基于trie的地图实施？

我过去曾写过自己的文章,但如果可以的话,我宁愿选择标准的东西.

快速说明:虽然我的问题很普遍,但在当前项目中,我处理的是大量数据,这些数据由完全限定的类名或方法签名索引.因此,有许多共享前缀.

Answer 1

您可能希望查看Limewire为 Google Guava 做出贡献的Trie实现.

Answer 2

核心Java库中没有trie数据结构.

这可能是因为尝试通常用于存储字符串,而Java数据结构更通用,通常包含任何Object(定义相等和散列操作),尽管它们有时仅限于 Comparable对象(定义顺序)."符号序列"没有共同的抽象,虽然CharSequence适用于字符串,但我想你可以Iterable为其他类型的符号做些什么.

这是另一个要考虑的问题:当尝试在Java中实现传统的trie时,很快就会面临Java支持Unicode的事实.要获得任何类型的空间效率,必须将trie中的字符串限制为符号的某个子集,或者放弃将子节点存储在由符号索引的数组中的传统方法.这可能是为什么尝试被认为不足以包含在核心库中的另一个原因,以及如果您实现自己的或使用第三方库需要注意的事项.

Answer 3

还要检查并发树.它们支持Radix和Suffix树,专为高并发环境而设计.

Answer 4

Apache Commons Collections v4.0 现在支持特里结构。

有关更多信息，请参阅org.apache.commons.collections4.trie包信息。特别是，检查PatriciaTrie类：

PATRICIA Trie（检索以字母数字编码的信息的实用算法）的实现。

PATRICIA Trie 是压缩的 Trie。PATRICIA 不是将所有数据存储在 Trie 的边缘（并且具有空的内部节点），而是将数据存储在每个节点中。这允许非常有效的遍历、插入、删除、前驱、后继、前缀、范围和选择（对象）操作。所有操作都在 O(K) 时间内执行，其中 K 是树中最大项的位数。实际上，操作实际上需要 O(A(K)) 时间，其中 A(K) 是树中所有项目的平均位数。