迭代遍历TreeSet比迭代Java中的HashSet要慢吗？ [英] Is iterating through a TreeSet slower than iterating through a HashSet in Java?

问题描述

我正在运行一些基准测试。我的一个测试取决于顺序，所以我正在使用TreeSet。我的第二个测试没有，所以我正在使用HashSet。

I'm running some benchmarks. One of my tests depends on order, so I'm using a TreeSet for that. My second test doesn't, so I'm using a HashSet for it.

我知道TreeSet的插入速度较慢。但是迭代所有元素呢？

I know that insertion is slower for the TreeSet. But what about iterating through all elements?

推荐答案

TreeSets 内部使用 TreeMaps 这是红黑树（特殊类型 BST ） 。

TreeSets internally uses TreeMaps which are Red Black Trees (special type of BST) .

BST Inorder Traversal O（n）

BST Inorder Traversal is O(n)

HashSets 内部使用 HashMaps 使用 array 用于保存Entry对象。

HashSets internally uses HashMaps which use an array for holding Entry objects.

此处遍历应为 O（n）。

除非你写一个基准，否则很难证明哪个更快。

Unless you write a benchmark it is going to be difficult to prove which is faster.

这篇关于迭代遍历TreeSet比迭代Java中的HashSet要慢吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！