java - 字典数据结构+快速复杂度方法

我正在尝试从头开始构建一个能够容纳大量字典(单词/字符)的数据结构。

“单词”可以由任意多的字符组成。

字典需要标准方法，例如搜索、插入、删除。

我需要这些方法的时间复杂度优于 O(log(n))，所以介于O(log(n)) 到 O(1)，例如 log(log(n))

其中 n = 字典大小(元素数量)

我研究了各种树结构，例如具有 log(n) 方法(不够快)的 b 树以及似乎最适合字典的 trie，但是由于单词可以任意大，它的复杂度似乎不会比 log(n) 快。

如果可以，请提供任何解释

最佳答案

trie 对内存有很大的要求，但访问时间通常比 O(log n) 快。

如果我没记错的话，访问时间取决于单词的长度，而不是结构中单词的数量。

效率和内存消耗还取决于您选择使用的 trie 的具体实现。那里有一些非常有效的实现。

有关 Tries 的更多信息，请参阅:

关于java - 字典数据结构+快速复杂度方法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/30458801/

相关文章：

java - 从 map 中检索对象