java - 从排序的元素列表构建 Java TreeMap

Question

我有一个文本文件，其中包含一个排序的单词列表，作为我的字典。

我想使用 TreeMap 以便在我必须查看单词是否属于字典时将 log(n) 作为平均成本 (即 containsKey)。

我读过 Black-Read 树在 TreeMap 的幕后，所以它是 self 平衡的。

我的问题是:将单词列表提供给 TreeMap 的最佳方式是什么？

我的意思是:用排序列表喂养它应该是二叉树的最坏情况，因为它必须平衡几乎所有其他单词，不是吗？

单词列表的数量从 7K 到 150K 不等。

Answer 1

TreeMap 隐藏了它的实现细节，作为良好的 OO 设计规定，因此要真正针对您的用例进行优化可能会很困难。

但是，如果可以选择在将所有项添加到 TreeMap 之前将它们读入数组/列表，则可以“由内而外”添加它们:列表的中间元素将变为根，所以先加上它，然后用同样的方式递归地加上前半部分和后半部分。事实上，这就是 TreeMap(SortedMap) 构造函数遵循的策略。

如果读取所有项目不是一个选项，我认为您别无选择，只能简单地将您的条目连续放入 map ，或者编写您自己的树实现，以便您可以更好地控制如何生成它。如果您至少事先知道项目的数量，那么您应该能够生成一棵平衡树而无需重新平衡。

如果您不需要 TreeMap 的额外功能，您也可以考虑使用 HashMap，它(为您的键提供一个良好的哈希函数)甚至具有O(1) 访问。