一尘不染

Java中有Trie吗?

java

我想在Java中使用Trie,有没有可以使用的实现?(我尝试寻找一个,但没有找到)。


阅读 218

收藏
2020-12-03

共1个答案

一尘不染

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

这可能是因为尝试通常被设计为存储字符串,而Java数据结构更通用,通常包含任何字符串Object(定义相等性和哈希操作),尽管有时它们限于
Comparable对象(定义顺序)。尽管CharSequence适用于字符串,但没有通用的“符号序列”抽象,我想您可以Iterable为其他类型的符号做些事情。

这是要考虑的另一点:当尝试在Java中实现传统的trie时,您很快就会遇到Java支持Unicode的事实。为了获得某种形式的空间效率,您必须将Trie中的字符串限制为某些符号子集,或者放弃将符号节点索引的数组中存储子节点的常规方法。这可能是为什么尝试被认为不够通用而无法包含在核心库中的另一个原因,并且是您实施自己的库或使用第三方库时要提防的地方。

2020-12-03