我一直很喜欢树,O(n*log(n))和它们的整洁。然而,我所认识的每个软件工程师都尖锐地问过我为什么要使用TreeSet。从CS的背景来看,我不认为你使用什么很重要,我也不关心在哈希函数和桶(在Java的情况下)上搞得一团糟。
在哪些情况下,我应该在树集上使用HashSet ?
我一直很喜欢树,O(n*log(n))和它们的整洁。然而,我所认识的每个软件工程师都尖锐地问过我为什么要使用TreeSet。从CS的背景来看,我不认为你使用什么很重要,我也不关心在哈希函数和桶(在Java的情况下)上搞得一团糟。
在哪些情况下,我应该在树集上使用HashSet ?
当前回答
1.HashSet允许空对象。
2.树集不允许空对象。如果你试图添加空值,它将抛出一个NullPointerException。
3.HashSet比TreeSet快得多。
e.g.
TreeSet<String> ts = new TreeSet<String>();
ts.add(null); // throws NullPointerException
HashSet<String> hs = new HashSet<String>();
hs.add(null); // runs fine
其他回答
当然,HashSet实现要快得多——开销更少,因为没有排序。http://java.sun.com/docs/books/tutorial/collections/implementations/set.html提供了Java中各种Set实现的很好的分析。
这里的讨论还指出了一种有趣的“中间地带”方法来解决树与哈希的问题。Java提供了一个LinkedHashSet,它是一个HashSet,其中运行着一个“面向插入”的链表,也就是说,链表中的最后一个元素也是最近插入到哈希中的元素。这允许您避免无序散列的无序性,而不会增加TreeSet的成本。
大多数人使用HashSet的原因是操作(平均)是O(1)而不是O(log n)。如果集合包含标准项,你就不会像以前那样“乱搞哈希函数”。如果集合包含自定义类,则必须实现hashCode才能使用HashSet(尽管Effective Java演示了如何使用),但如果使用TreeSet,则必须使其具有可比性或提供比较器。如果类没有特定的顺序,这可能是一个问题。
我有时会使用TreeSet(或者实际上是TreeMap)用于非常小的集合/映射(< 10项),尽管我没有检查这样做是否有任何真正的好处。对于大型机组,差异可能相当大。
现在,如果您需要排序,那么TreeSet是合适的,尽管即使如此,如果更新频繁,对排序结果的需求并不频繁,有时将内容复制到列表或数组中并对它们排序会更快。
import java.util.HashSet;
import java.util.Set;
import java.util.TreeSet;
public class HashTreeSetCompare {
//It is generally faster to add elements to the HashSet and then
//convert the collection to a TreeSet for a duplicate-free sorted
//Traversal.
//really?
O(Hash + tree set) > O(tree set) ??
Really???? Why?
public static void main(String args[]) {
int size = 80000;
useHashThenTreeSet(size);
useTreeSetOnly(size);
}
private static void useTreeSetOnly(int size) {
System.out.println("useTreeSetOnly: ");
long start = System.currentTimeMillis();
Set<String> sortedSet = new TreeSet<String>();
for (int i = 0; i < size; i++) {
sortedSet.add(i + "");
}
//System.out.println(sortedSet);
long end = System.currentTimeMillis();
System.out.println("useTreeSetOnly: " + (end - start));
}
private static void useHashThenTreeSet(int size) {
System.out.println("useHashThenTreeSet: ");
long start = System.currentTimeMillis();
Set<String> set = new HashSet<String>();
for (int i = 0; i < size; i++) {
set.add(i + "");
}
Set<String> sortedSet = new TreeSet<String>(set);
//System.out.println(sortedSet);
long end = System.currentTimeMillis();
System.out.println("useHashThenTreeSet: " + (end - start));
}
}
TreeSet的一个尚未被提及的优点是它有更大的“局部性”,这是以下说法的简写:(1)如果两个条目在顺序上是相邻的,TreeSet将它们放在数据结构中彼此相邻的地方,因此在内存中也是如此;并且(2)这种布局利用了局部性原则,该原则说类似的数据通常被一个应用程序以相似的频率访问。
这与HashSet相反,HashSet将条目分布在内存中,而不管它们的键是什么。
当从硬盘读取的延迟成本是从缓存或RAM读取的延迟成本的数千倍,并且当数据确实是通过局部性访问时,TreeSet可能是更好的选择。
1.HashSet允许空对象。
2.树集不允许空对象。如果你试图添加空值,它将抛出一个NullPointerException。
3.HashSet比TreeSet快得多。
e.g.
TreeSet<String> ts = new TreeSet<String>();
ts.add(null); // throws NullPointerException
HashSet<String> hs = new HashSet<String>();
hs.add(null); // runs fine