2023-08-25 09:00:07

树对树

我一直很喜欢树,O(n*log(n))和它们的整洁。然而,我所认识的每个软件工程师都尖锐地问过我为什么要使用TreeSet。从CS的背景来看,我不认为你使用什么很重要,我也不关心在哈希函数和桶(在Java的情况下)上搞得一团糟。

在哪些情况下,我应该在树集上使用HashSet ?


当前回答

如果您没有插入足够多的元素导致频繁重散列(或冲突,如果您的HashSet不能调整大小),那么HashSet当然可以为您提供常量时间访问的好处。但是对于有大量增长或收缩的集合,使用Treesets实际上可能会获得更好的性能,这取决于实现。

如果我没记错的话,平摊时间可以接近于一个功能性红黑树的O(1)。冈崎的书会有比我更好的解释。(或参阅他的出版物列表)

其他回答

如果您没有插入足够多的元素导致频繁重散列(或冲突,如果您的HashSet不能调整大小),那么HashSet当然可以为您提供常量时间访问的好处。但是对于有大量增长或收缩的集合,使用Treesets实际上可能会获得更好的性能,这取决于实现。

如果我没记错的话,平摊时间可以接近于一个功能性红黑树的O(1)。冈崎的书会有比我更好的解释。(或参阅他的出版物列表)

明明可以吃橘子,为什么要吃苹果?

Seriously guys and gals - if your collection is large, read and written to gazillions of times, and you're paying for CPU cycles, then the choice of the collection is relevant ONLY if you NEED it to perform better. However, in most cases, this doesn't really matter - a few milliseconds here and there go unnoticed in human terms. If it really mattered that much, why aren't you writing code in assembler or C? [cue another discussion]. So the point is if you're happy using whatever collection you chose, and it solves your problem [even if it's not specifically the best type of collection for the task] knock yourself out. The software is malleable. Optimise your code where necessary. Uncle Bob says Premature Optimisation is the root of all evil. Uncle Bob says so

大多数人使用HashSet的原因是操作(平均)是O(1)而不是O(log n)。如果集合包含标准项,你就不会像以前那样“乱搞哈希函数”。如果集合包含自定义类,则必须实现hashCode才能使用HashSet(尽管Effective Java演示了如何使用),但如果使用TreeSet,则必须使其具有可比性或提供比较器。如果类没有特定的顺序,这可能是一个问题。

我有时会使用TreeSet(或者实际上是TreeMap)用于非常小的集合/映射(< 10项),尽管我没有检查这样做是否有任何真正的好处。对于大型机组,差异可能相当大。

现在,如果您需要排序,那么TreeSet是合适的,尽管即使如此,如果更新频繁,对排序结果的需求并不频繁,有时将内容复制到列表或数组中并对它们排序会更快。

基于@shevchyk在地图上可爱的视觉回答,以下是我的看法:

╔══════════════╦═════════════════════╦═══════════════════╦═════════════════════╗
║   Property   ║       HashSet       ║      TreeSet      ║     LinkedHashSet   ║
╠══════════════╬═════════════════════╬═══════════════════╬═════════════════════╣
║              ║  no guarantee order ║ sorted according  ║                     ║
║   Order      ║ will remain constant║ to the natural    ║    insertion-order  ║
║              ║      over time      ║    ordering       ║                     ║
╠══════════════╬═════════════════════╬═══════════════════╬═════════════════════╣
║ Add/remove   ║        O(1)         ║     O(log(n))     ║        O(1)         ║
╠══════════════╬═════════════════════╬═══════════════════╬═════════════════════╣
║              ║                     ║   NavigableSet    ║                     ║
║  Interfaces  ║         Set         ║       Set         ║         Set         ║
║              ║                     ║    SortedSet      ║                     ║
╠══════════════╬═════════════════════╬═══════════════════╬═════════════════════╣
║              ║                     ║    not allowed    ║                     ║
║  Null values ║       allowed       ║ 1st element only  ║      allowed        ║
║              ║                     ║     in Java 7     ║                     ║
╠══════════════╬═════════════════════╩═══════════════════╩═════════════════════╣
║              ║   Fail-fast behavior of an iterator cannot be guaranteed      ║
║   Fail-fast  ║ impossible to make any hard guarantees in the presence of     ║
║   behavior   ║           unsynchronized concurrent modification              ║
╠══════════════╬═══════════════════════════════════════════════════════════════╣
║      Is      ║                                                               ║
║ synchronized ║              implementation is not synchronized               ║
╚══════════════╩═══════════════════════════════════════════════════════════════╝

HashSet比TreeSet快得多(对于添加、删除和包含等大多数操作,HashSet是常量时间,而不是日志时间),但不像TreeSet那样提供排序保证。

HashSet

该类为基本操作(添加、删除、包含和大小)提供恒定的时间性能。 它不能保证元素的顺序随时间保持不变 迭代性能取决于初始容量和HashSet的负载因子。 接受默认的负载因子是相当安全的,但您可能希望指定的初始容量大约是您期望该集增长的两倍。

TreeSet

保证基本操作(添加、删除和包含)的时间成本为log(n) 确保set的元素将被排序(升序,自然或由你通过它的构造函数指定)(实现SortedSet) 不为迭代性能提供任何调优参数 提供了一些方便的方法来处理有序集,如first(), last(), headSet()和tailSet()等

重要的几点:

Both guarantee duplicate-free collection of elements It is generally faster to add elements to the HashSet and then convert the collection to a TreeSet for a duplicate-free sorted traversal. None of these implementations are synchronized. That is if multiple threads access a set concurrently, and at least one of the threads modifies the set, it must be synchronized externally. LinkedHashSet is in some sense intermediate between HashSet and TreeSet. Implemented as a hash table with a linked list running through it, however,it provides insertion-ordered iteration which is not same as sorted traversal guaranteed by TreeSet.

因此,使用方法的选择完全取决于您的需要,但我认为,即使您需要一个有序的集合,那么您仍然应该使用HashSet来创建Set,然后将其转换为TreeSet。

例如:SortedSet<String> s = new TreeSet<String>(hashSet);