为什么最好将hashset转换为treeset然后直接使用treeset

Question

在包括太阳网站在内的网络的许多地方,出现以下句子:

通常更快地执行操作hashSet然后转换 hashset为treeset.

好吧,我有点困惑,那hashset是正确的添加元素是o(1)在treeset(黑色和红色树)添加对象是o(logn)但当我将hashset转换为树集我需要对我的数据进行排序,这就是o(nlogn)为什么它更快使用hashset然后将其转换为treeset？我知道如果你预先形成删除或现有元素,所以哈希和树之间存在差异,但我不认为这是太阳所指的因素(至少我希望如此,因为它看起来像一个非常小的东西)另一件事是hashcode方法可以不那么好,然后添加元素到哈希将不会o(1)或hashcode方法可能是复杂的.所以一般我不明白这句话.谁能帮我？

Answer 1

它取决于在将元素复制到排序树结构之前在哈希表中发生的操作数.如果你所做的只是在哈希表中插入n个不同的元素,那么不,这样做不会更快,然后将它们复制到树上:)

散列的一组项目可以通过以下任一方式转换为已排序的树:使用常规排序,然后从中构建树,或者一次一个地将项目插入树中.前者意味着额外的复制/遍历; 后者意味着维护平衡树的额外开销(尽管如果你迭代一个哈希表,你会得到有效随机顺序的项目,这意味着你可以避免大多数重新平衡).

对于受到良好支持的操作(插入/修改/删除),哈希表通常比搜索树更快,但在实际测量整个应用程序的性能并且可以期望有价值的整体加速之前,它绝对不值得做Sun推荐的事情.从可能会有轻微的改善.

当密钥比较昂贵时(如字符串),哈希表确实比排序树具有更大的优势,因为对于大型集合,与搜索树深度相比,更少的项目将发生哈希冲突,并且因为可以缓存哈希值已经在集合中的密钥的代码,跳过除了匹配结果之外的所有(可能)的昂贵比较.