我一直很喜欢树,O(n*log(n))和它们的整洁。然而,我所认识的每个软件工程师都尖锐地问过我为什么要使用TreeSet。从CS的背景来看,我不认为你使用什么很重要,我也不关心在哈希函数和桶(在Java的情况下)上搞得一团糟。
在哪些情况下,我应该在树集上使用HashSet ?
我一直很喜欢树,O(n*log(n))和它们的整洁。然而,我所认识的每个软件工程师都尖锐地问过我为什么要使用TreeSet。从CS的背景来看,我不认为你使用什么很重要,我也不关心在哈希函数和桶(在Java的情况下)上搞得一团糟。
在哪些情况下,我应该在树集上使用HashSet ?
当前回答
TreeSet的一个尚未被提及的优点是它有更大的“局部性”,这是以下说法的简写:(1)如果两个条目在顺序上是相邻的,TreeSet将它们放在数据结构中彼此相邻的地方,因此在内存中也是如此;并且(2)这种布局利用了局部性原则,该原则说类似的数据通常被一个应用程序以相似的频率访问。
这与HashSet相反,HashSet将条目分布在内存中,而不管它们的键是什么。
当从硬盘读取的延迟成本是从缓存或RAM读取的延迟成本的数千倍,并且当数据确实是通过局部性访问时,TreeSet可能是更好的选择。
其他回答
TreeSet的一个尚未被提及的优点是它有更大的“局部性”,这是以下说法的简写:(1)如果两个条目在顺序上是相邻的,TreeSet将它们放在数据结构中彼此相邻的地方,因此在内存中也是如此;并且(2)这种布局利用了局部性原则,该原则说类似的数据通常被一个应用程序以相似的频率访问。
这与HashSet相反,HashSet将条目分布在内存中,而不管它们的键是什么。
当从硬盘读取的延迟成本是从缓存或RAM读取的延迟成本的数千倍,并且当数据确实是通过局部性访问时,TreeSet可能是更好的选择。
消息编辑(完全重写)当顺序无关紧要时,就是这样。两者都应该给出Log(n) -看看其中一个是否比另一个快5%以上是有用的。HashSet可以在循环中给出O(1)测试,应该可以揭示它是否正确。
大多数人使用HashSet的原因是操作(平均)是O(1)而不是O(log n)。如果集合包含标准项,你就不会像以前那样“乱搞哈希函数”。如果集合包含自定义类,则必须实现hashCode才能使用HashSet(尽管Effective Java演示了如何使用),但如果使用TreeSet,则必须使其具有可比性或提供比较器。如果类没有特定的顺序,这可能是一个问题。
我有时会使用TreeSet(或者实际上是TreeMap)用于非常小的集合/映射(< 10项),尽管我没有检查这样做是否有任何真正的好处。对于大型机组,差异可能相当大。
现在,如果您需要排序,那么TreeSet是合适的,尽管即使如此,如果更新频繁,对排序结果的需求并不频繁,有时将内容复制到列表或数组中并对它们排序会更快。
即使在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也会有这种行为。
最初的回答
基于@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 ║
╚══════════════╩═══════════════════════════════════════════════════════════════╝