Hashset与Treeset

Question

我一直喜欢树木,它们很好,O(n*log(n))而且它们整洁.然而,我所知道的每一位软件工程师都有针对性地问我为什么会使用TreeSet.从CS背景来看,我认为你所使用的并不重要,而且我不想乱用哈希函数和桶(在这种情况下Java).

在这情况下,我应该使用HashSet过TreeSet？

Answer 1

HashSet比TreeSet快得多(对于大多数操作,例如add,remove和contains,常量时间与日志时间相比),但不提供像TreeSet这样的排序保证.

HashSet的

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

TreeSet中

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

重点:

• 两者都保证元素的无重复收集
• 通常,将元素添加到HashSet然后将集合转换为TreeSet以进行无重复的排序遍历通常会更快.
• 这些实现都不是同步的.也就是说,如果多个线程同时访问一个集合,并且至少有一个线程修改了该集合,则必须在外部进行同步.
• LinkedHashSet在某种意义上介于HashSet和之间TreeSet.实现为具有贯穿其的链表的哈希表,但是,它提供了插入顺序迭代,这与TreeSet保证的排序遍历不同.

因此,使用选择完全取决于您的需求,但我觉得即使您需要有序集合,您仍然应该更喜欢HashSet来创建Set,然后将其转换为TreeSet.

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

Answer 2

尚未提及的一个优点TreeSet是它具有更大的"局部性",这是说(1)如果两个条目在序列中附近,则TreeSet它们在数据结构中彼此靠近,因此在存储器中; (2)这种放置利用了局部性原理,即相似频率的应用程序经常访问类似数据.

这与a形成对比,a HashSet无论键是什么,它都会将条目分布在整个内存中.

当从硬盘读取延迟成本数千次的从高速缓存或内存,当数据真正与当地访问时,阅读成本TreeSet可以是一个更好的选择.

Answer 3

HashSet是O(1)访问元素,所以它确实很重要.但是不可能保持集合中对象的顺序.

TreeSet如果维护订单(就价值而非订单顺序)对您很重要,则非常有用.但是,正如您已经注意到的那样,您正在交易订单,以便更慢地访问元素:O(log n)用于基本操作.

从javadocsTreeSet:

此实现提供了基本的操作保证的log(n)的时间成本(add,remove和contains).

Answer 4

1.HashSet允许空对象.

2.TreeSet不允许null对象.如果您尝试添加null值,它将抛出NullPointerException.

3.HashSet比TreeSet快得多.

例如

 TreeSet<String> ts = new TreeSet<String>();
 ts.add(null); // throws NullPointerException

 HashSet<String> hs = new HashSet<String>();
 hs.add(null); // runs fine

Answer 5

基于@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               ?
????????????????????????????????????????????????????????????????????????????????

Answer 6

大多数使用的原因HashSet是操作(平均)O(1)而不是O(log n).如果集合包含标准项目,那么您将不会"乱用哈希函数",因为已经为您完成了.如果集合包含自定义类,则必须实现hashCode使用HashSet(尽管Effective Java显示了如何使用),但如果使用a TreeSet,则必须创建Comparable或提供Comparator.如果班级没有特定的订单,这可能是一个问题.

我有时使用TreeSet(或实际TreeMap)非常小的集/地图(<10项),虽然我没有检查是否有任何实际的收益.对于大型套装,差异可能相当大.

现在,如果你需要排序,那么TreeSet是合适的,尽管即使这样,如果频繁更新并且对排序结果的需求很少,有时将内容复制到列表或数组并对它们进行排序可能会更快.

Answer 7

如果您没有插入足够的元素来导致频繁的重新散列(或者碰撞,如果您的HashSet无法调整大小),HashSet肯定会为您提供持续时间访问的好处.但是在具有大量增长或缩减的集合上,使用Treesets实际上可能会获得更好的性能,具体取决于实现.

如果记忆为我服务,摊销时间可以接近O(1),功能红黑树.Okasaki的书会有比我能说的更好的解释.(或者看他的出版物清单)

Answer 8

当然,HashSet实现要快得多 - 开销较少,因为没有排序.http://java.sun.com/docs/books/tutorial/collections/implementations/set.html提供了对Java中各种Set实现的良好分析.

那里的讨论还指出了树与哈希问题的一个有趣的"中间立场"方法.Java提供了一个LinkedHashSet,它是一个HashSet,其中有一个"面向插入"的链表,也就是说,链表中的最后一个元素也是最近插入Hash的.这使您可以避免无序散列的不正常,而不会导致TreeSet的成本增加.