我一直在阅读这个主题，与我对添加、删除和搜索操作的理解相去甚远，HashSet在O(1)时间复杂性方面更快，而TreeSet在相同操作中获得O(logn)。当遍历元素时，HashSet和TreeSet都具有O(n)的时间复杂度。
那么，当TreeSet比HashSet快时，用例是什么呢？
通常，您可以通过查看Java容器类实现的接口来最好地比较它们的功能。检查HashSetjavadoc，您会发现它有Iterable<E>, Collection<E>, Set<E>。TreeSet具有Iterable<E>, Collection<E>, NavigableSet<E>, Set<E>, SortedSet<E>。
所以差为SortedSet和NavigableSet。这些是TreeSet提供的方法，而HashSet没有。如果你反过来查找他们的javadoc，你会发现一系列行为被组织起来利用TreeSet中元素的顺序。HashSets没有元素排序的概念。这是主要区别。如果你想对元素强加一个顺序，你通常只限于对它们进行单独排序，而按自然顺序遍历TreeSet是每个项目分摊的恒定时间。(遍历的各个步骤可能需要时间比例对数。)
在实践中，对于它们共同的方法，HashSet性能的O(1)预期摊销时间和TreeSet的O(log n)保证时间之间的差异并不重要。记住，log_2(n)几乎在所有实际用途中都小于40。在调用算法的性能中，执行几条指令40次往往是噪声。
当差异很重要时，您仍然需要考虑哈希性能的预期摊销性质，因为任何给定的add()都可能需要O(n)时间来扩展内部存储桶数组并重新散列所有内容。在某些应用程序中，这是一个杀手。例如，你的游戏通常像闪电一样运行，但偶尔会出现停顿，而10Mb的哈希集会增长到20Mb。类似地，如果您的数据恰好与HashMap的哈希函数不兼容(或者数据可能来自故意破坏它的恶意用户)，那么性能可能更像O(n)而不是O(1)。
TreeSet的表演没有如此宏大的表演怪癖。例如，重组一棵红黑树可能只需要与log_(n)成比例的时间，这是罕见的。也就是说，后来版本的HashSet实际上使用树集作为bucket，以避免被坏人利用。
TreeSet在某些排序与正在执行的任务相关的用例中比HashSet更快。
例如，如果我有一组字符串，并且我想找到该集中最小的(根据排序)字符串，该字符串大于或等于给定字符串。
- 使用
HashSet，我必须迭代整个集合才能找到字符串。。。在给定字符串不在集合中的情况下。那就是O(N) - 对于使用所需排序的
TreeSet，我可以使用ceiling在O(logN)中查找所需的字符串
另一个例子，如果我想按的顺序迭代字符串集，那就是TreeSet的O(N)。对于HashSet，我必须将字符串提取到数组中，对数组进行排序，然后迭代。总之，这就是O(NlogN)。
注意事项：
-
复杂性和性能不是一回事。例如，当
N相对较小时，O(N)解决方案可能比O(NlogN)解决方案更快。 -
当集合大小超过231时，Java
HashSet操作不再是O(1)，因为标准HashSet实现使用Java数组作为哈希数组，并且不能调整大小超过该值。
在TreeSet和HashSet上定义的实际方法中，没有一个在TreeSet上可靠地更快。TreeSet上还有其他方法不能在HashSet上有效地实现，所以它们不是——比如floor和ceiling。
TreeSet的附加值不是数据结构的复杂性，而是数据结构的类型。在任何情况下，哈希集的复杂性都比树集好，除非在迭代的情况下，它们具有相同的复杂性。
HashSet:add、remove和contains方法具有恒定的时间复杂度O(1)。
树集：add、remove和contains方法的时间复杂度为O(log(n))。
TreeSet提供了hashset没有的几种方法，例如处理有序集，如first()、last()，headset()、tailset()。
因此，为了解决一些问题，TreeSet更合适，因此您的程序性能将比使用HashSet时更好。
从技术上讲，这两者不能进行公平的比较。HashSet实现Set，而TreeSet实现NavigableSet，它具有基于元素概念的额外功能(尽管不要求实现实际排序)。
对于所有Set方法，HashSet比TreeSet更快(O(1)vs O(logn)。
TreeSet提供NavigableSet方法(例如，ceiling()为O(logn)，这些方法"更快"，只是因为它们不存在于Set中，所以这不是竞争。
TreeSet也会在O(n)时间内按Comparable顺序迭代其元素，而HashSet则无法做到这一点；您必须对Set进行迭代，以收集列表中的元素，然后对列表进行排序——有效时间复杂性为O(nlogn)。