哈希集与树集 [英] Hashset vs Treeset

问题描述

我一直很喜欢树木，它漂亮的 O(n*log(n)) 和它们的整洁.然而，我认识的每一位软件工程师都尖锐地问我为什么要使用 TreeSet.从 CS 背景来看，我认为你使用什么并不重要，我也不关心散列函数和存储桶(在 Java 的情况下).

在哪些情况下我应该在 TreeSet 上使用 HashSet?

解决方案

HashSet 比 TreeSet 快得多(对于添加、删除和包含等大多数操作，常量时间与日志时间)但不提供排序保证，例如树集.

HashSet

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

树集

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

要点:

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

所以使用的选择完全取决于你的需要，但我觉得即使你需要一个有序的集合，你仍然应该更喜欢 HashSet 来创建 Set 然后将它转换为 TreeSet.

• 例如SortedSets = new TreeSet(hashSet);

I've always loved trees, that nice O(n*log(n)) and the tidiness of them. However, every software engineer I've ever known has asked me pointedly why I would use a TreeSet. From a CS background, I don't think it matters all that much which you use, and I don't care to mess around with hash functions and buckets (in the case of Java).

In which cases should I use a HashSet over a TreeSet?

解决方案

HashSet is much faster than TreeSet (constant-time versus log-time for most operations like add, remove and contains) but offers no ordering guarantees like TreeSet.

HashSet

• the class offers constant time performance for the basic operations (add, remove, contains and size).
• it does not guarantee that the order of elements will remain constant over time
• iteration performance depends on the initial capacity and the load factor of the HashSet.
  • It's quite safe to accept default load factor but you may want to specify an initial capacity that's about twice the size to which you expect the set to grow.

TreeSet

• guarantees log(n) time cost for the basic operations (add, remove and contains)
• guarantees that elements of set will be sorted (ascending, natural, or the one specified by you via its constructor) (implements SortedSet)
• doesn't offer any tuning parameters for iteration performance
• offers a few handy methods to deal with the ordered set like first(), last(), headSet(), and tailSet() etc

Important points:

• Both guarantee duplicate-free collection of elements
• It is generally faster to add elements to the HashSet and then convert the collection to a TreeSet for a duplicate-free sorted traversal.
• None of these implementations are synchronized. That is if multiple threads access a set concurrently, and at least one of the threads modifies the set, it must be synchronized externally.
• LinkedHashSet is in some sense intermediate between HashSet and TreeSet. Implemented as a hash table with a linked list running through it, however,it provides insertion-ordered iteration which is not same as sorted traversal guaranteed by TreeSet.

So a choice of usage depends entirely on your needs but I feel that even if you need an ordered collection then you should still prefer HashSet to create the Set and then convert it into TreeSet.

• e.g. SortedSet<String> s = new TreeSet<String>(hashSet);

这篇关于哈希集与树集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！