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

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

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

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

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

1> David Schlos..：

---

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

---

看起来Google-Collections已被Guava取代https://code.google.com/p/guava-libraries/,不幸的是我无法在任何地方看到Trie课程.Patricia Trie现在似乎有自己的项目页面:https://code.google.com/p/patricia-trie/

2> erickson..：

---

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

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

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

3> Alex Beardsl..：

---

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

---

截至2014年,这应该是公认的答案.看起来像是维护良好,经过良好测试,并发执行的尝试.