Hashset vs Treeset

 

我一直都很喜欢树木，那个漂亮的O(n*lg(n))和它们的整洁。 然而，我所知道的每一位软件工程师都尖锐地问我为什么要使用TreeSet 。 从CS背景来看，我认为它并不重要，而且我不关心哈希函数和存储区（以Java ）。

在哪种情况下，我应该在TreeSet使用HashSet ？

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);

    • TreeSet尚未提及的一个优点是其具有更大的“局部性”，这是“（1）如果两个条目在顺序附近， TreeSet将它们放在数据结构中彼此靠近，因此在内存中; （2）这种布局利用了局部性的原理，该局部性说明类似的数据经常被具有相似频率的应用程序访问。

    这与HashSet相反， HashSet将条目遍布内存，而不管它们的密钥是什么。

    当从硬盘读取数据的延迟成本是从缓存或RAM中读取数千倍的成本时，以及真正用本地访问数据时， TreeSet可能是更好的选择。

    HashSet是O（1）来访问元素，所以它肯定很重要。 但是维持集合中对象的顺序是不可能的。

    如果维护订单（按照值而不是插入顺序），则TreeSet非常有用。 但是，正如您所指出的那样，您正在交易订单以获得访问元素的较慢时间：O（log n）用于基本操作。

    从TreeSet的javadocs：

    此实现为基本操作（ add ， remove和contains ）提供了有保证的log（n）时间成本。

    链接地址: http://www.djcxy.com/p/92185.html

    上一篇: Hashset vs Treeset

    下一篇: Firebase Performance of Hashmap versus TreeMap