我有一个文本文件,其中包含一个排序的单词列表作为我的字典。
我想使用TreeMap
以便将log(n)作为平均成本,当我必须查看单词是否属于字典时(即containsKey
)。
我已经读过在Qazxswpoi幕后的Black-Read树,所以它是自我平衡的。
我的问题是:哪个是用字列表提供TreeMap
的最好方法?
我的意思是:用一个排序列表喂它应该是二叉树的最坏情况,因为它必须平衡几乎所有其他单词,不是吗?
单词列表的数量可以从7K到150K不等。
TreeMap
隐藏了它的实现细节,因为良好的OO设计规定,所以真正优化你的用例可能会很难。
但是,如果在将所有项目添加到TreeMap
之前将其读入数组/列表是一个选项,则可以将其添加到“out out”中:列表的中间元素将成为根,因此首先添加它,然后以相同的方式递归地添加前半部分和后半部分。事实上,这是TreeMap
构造函数遵循的策略。
如果不是读取所有项目的选项,我认为除了简单地将条目连续地放入地图,或者编写自己的树实现以便您可以更好地控制如何生成它之外别无选择。如果您至少事先知道项目数,那么您应该能够生成平衡树而无需重新平衡。
如果你不需要TreeMap(SortedMap)
的额外功能,你也可以考虑使用TreeMap
,它(给你的键具有良好的哈希函数)甚至可以访问O(1)。