我一直很喜欢树,O(n*log(n))和它们的整洁。然而,我所认识的每个软件工程师都尖锐地问过我为什么要使用TreeSet。从CS的背景来看,我不认为你使用什么很重要,我也不关心在哈希函数和桶(在Java的情况下)上搞得一团糟。
在哪些情况下,我应该在树集上使用HashSet ?
我一直很喜欢树,O(n*log(n))和它们的整洁。然而,我所认识的每个软件工程师都尖锐地问过我为什么要使用TreeSet。从CS的背景来看,我不认为你使用什么很重要,我也不关心在哈希函数和桶(在Java的情况下)上搞得一团糟。
在哪些情况下,我应该在树集上使用HashSet ?
当前回答
当然,HashSet实现要快得多——开销更少,因为没有排序。http://java.sun.com/docs/books/tutorial/collections/implementations/set.html提供了Java中各种Set实现的很好的分析。
这里的讨论还指出了一种有趣的“中间地带”方法来解决树与哈希的问题。Java提供了一个LinkedHashSet,它是一个HashSet,其中运行着一个“面向插入”的链表,也就是说,链表中的最后一个元素也是最近插入到哈希中的元素。这允许您避免无序散列的无序性,而不会增加TreeSet的成本。
其他回答
TreeSet的一个尚未被提及的优点是它有更大的“局部性”,这是以下说法的简写:(1)如果两个条目在顺序上是相邻的,TreeSet将它们放在数据结构中彼此相邻的地方,因此在内存中也是如此;并且(2)这种布局利用了局部性原则,该原则说类似的数据通常被一个应用程序以相似的频率访问。
这与HashSet相反,HashSet将条目分布在内存中,而不管它们的键是什么。
当从硬盘读取的延迟成本是从缓存或RAM读取的延迟成本的数千倍,并且当数据确实是通过局部性访问时,TreeSet可能是更好的选择。
HashSet是O(1)来访问元素,所以这当然很重要。但是保持集合中对象的顺序是不可能的。
如果维护顺序(根据值而不是插入顺序)对您很重要,TreeSet是有用的。但是,正如您所注意到的,您正在以顺序换取访问元素的更慢时间:基本操作为O(log n)。
来自TreeSet的javadocs:
该实现为基本操作(添加、删除和包含)提供了log(n)的时间成本。
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));
}
}
A lot of answers have been given, based on technical considerations, especially around performance. According to me, choice between TreeSet and HashSet matters. But I would rather say the choice should be driven by conceptual considerations first. If, for the objects your need to manipulate, a natural ordering does not make sense, then do not use TreeSet. It is a sorted set, since it implements SortedSet. So it means you need to override function compareTo, which should be consistent with what returns function equals. For example if you have a set of objects of a class called Student, then I do not think a TreeSet would make sense, since there is no natural ordering between students. You can order them by their average grade, okay, but this is not a "natural ordering". Function compareTo would return 0 not only when two objects represent the same student, but also when two different students have the same grade. For the second case, equals would return false (unless you decide to make the latter return true when two different students have the same grade, which would make equals function have a misleading meaning, not to say a wrong meaning.) Please note this consistency between equals and compareTo is optional, but strongly recommended. Otherwise the contract of interface Set is broken, making your code misleading to other people, thus also possibly leading to unexpected behavior.
这个链接可能是关于这个问题的一个很好的信息来源。
即使在11年后,也没有人想到提到一个非常重要的区别。
你认为如果HashSet等于TreeSet,那么反过来也成立吗?看看这段代码:
TreeSet<String> treeSet = new TreeSet<>(String.CASE_INSENSITIVE_ORDER);
HashSet<String> hashSet = new HashSet<>();
treeSet.add("a");
hashSet.add("A");
System.out.println(hashSet.equals(treeSet));
System.out.println(treeSet.equals(hashSet));
尝试猜测输出,然后徘徊在代码片段下面,看看真正的输出是什么。准备好了吗?给你:
假 真正的
没错,如果比较器与等号不一致,它们就不具有等价关系。原因是TreeSet使用比较器来确定等价性,而HashSet使用等号。在内部,它们使用HashMap和TreeMap,所以你应该预料到上述map也会有这种行为。
最初的回答