基于添加重复值的HashSet vs TreeSet vs LinkedHashSet
我正在学习核心 java 的核心，即 Collections.我想知道当我们在 HashSet、TreeSet、LinkedHashSet 中添加重复元素时内部会发生什么.
I am learning heart of core java i.e. Collections. I would like to know what happens internally when we add duplicate element in HashSet, TreeSet, LinkedHashSet.
条目是否被替换、忽略或抛出异常并终止程序.一个子问题是，哪个操作的所有操作具有相同或平均的时间复杂度
我们将不胜感激.
推荐答案
Java 中的TreeSet、LinkedHashSet 和HashSet 是集合框架中的三个Set 实现，与许多其他集合一样，它们也用于存储对象.TreeSet 的主要特点是排序，LinkedHashSet 是插入顺序，HashSet 只是用于存储对象的通用集合.HashSet 是使用 Java 中的 HashMap 实现的，而 TreeSet 是使用 TreeMap 实现的.TreeSet 是一个 SortedSet 实现，它允许它按照 Comparable 或 Comparator 接口定义的排序顺序保持元素.Comparable 用于自然顺序排序， Comparator 用于对象的自定义顺序排序，可以在创建 TreeSet 实例时提供.无论如何，在看到 TreeSet、LinkedHashSet 和 HashSet 之间的区别之前，让我们看看它们之间的一些相似之处:
TreeSet, LinkedHashSet and HashSet in Java are three Set implementation in collection framework and like many others they are also used to store objects. Main feature of TreeSet is sorting, LinkedHashSet is insertion order and HashSet is just general purpose collection for storing object. HashSet is implemented using HashMap in Java while TreeSet is implemented using TreeMap. TreeSet is a SortedSet implementation which allows it to keep elements in the sorted order defined by either Comparable or Comparator interface. Comparable is used for natural order sorting and Comparator for custom order sorting of objects, which can be provided while creating instance of TreeSet. Anyway before seeing difference between TreeSet, LinkedHashSet and HashSet, let's see some similarities between them:
1) Duplicates : 所有三个实现 Set 接口意味着它们不允许存储重复.
1) Duplicates : All three implements Set interface means they are not allowed to store duplicates.
2) 线程安全:HashSet、TreeSet 和 LinkedHashSet 不是线程安全的，如果你在至少有一个线程修改 Set 的多线程环境中使用它们，你需要在外部同步它们.
2) Thread safety : HashSet, TreeSet and LinkedHashSet are not thread-safe, if you use them in multi-threading environment where at least one Thread modifies Set you need to externally synchronize them.
3) Fail-Fast Iterator:TreeSet、LinkedHashSet和HashSet返回的Iterator都是fail-fast Iterator.即，如果 Iterator 在创建后通过 Iterators remove() 方法以外的任何方式被修改，它将尽最大努力抛出 ConcurrentModificationException.在此处阅读有关快速故障与故障安全迭代器的更多信息
3) Fail-Fast Iterator : Iterator returned by TreeSet, LinkedHashSet and HashSet are fail-fast Iterator. i.e. If Iterator is modified after its creation by any way other than Iterators remove() method, it will throw ConcurrentModificationException with best of effort. read more about fail-fast vs fail-safe Iterator here
现在让我们看看 Java 中 HashSet、LinkedHashSet 和 TreeSet 的区别:
Now let’s see difference between HashSet, LinkedHashSet and TreeSet in Java :
性能和速度:它们之间的第一个区别在于速度.HashSet 最快，LinkedHashSet 在性能上排名第二或几乎与 HashSet 相似，但 TreeSet 稍慢，因为它需要在每次插入时执行排序操作.TreeSet 为添加、删除和包含等常见操作提供有保证的 O(log(n)) 时间，而 HashSet 和 LinkedHashSet 提供恒定时间性能，例如给定哈希函数的添加、包含和删除 O(1) 将元素均匀分布在桶中.
Performance and Speed : First difference between them comes in terms of speed. HashSet is fastest, LinkedHashSet is second on performance or almost similar to HashSet but TreeSet is bit slower because of sorting operation it needs to perform on each insertion. TreeSet provides guaranteed O(log(n)) time for common operations like add, remove and contains, while HashSet and LinkedHashSet offer constant time performance e.g. O(1) for add, contains and remove given hash function uniformly distribute elements in bucket.
Ordering : HashSet 不维护任何顺序，而 LinkedHashSet 维护元素的插入顺序，类似于 List 接口，TreeSet 维护排序或元素的顺序.
Ordering : HashSet does not maintain any order while LinkedHashSet maintains insertion order of elements much like List interface and TreeSet maintains sorting order or elements.
内部实现:HashSet 由 HashMap 实例支持，LinkedHashSet 使用 HashSet 和 LinkedList 实现，而 TreeSet 由 Java 中的 NavigableMap 支持，默认使用 TreeMap.
Internal Implementation : HashSet is backed by an HashMap instance, LinkedHashSet is implemented using HashSet and LinkedList while TreeSet is backed up by NavigableMap in Java and by default it uses TreeMap.
null : HashSet 和 LinkedHashSet 都允许 null 但 TreeSet 不允许 null 并在将 null 插入 TreeSet 时抛出 java.lang.NullPointerException.由于 TreeSet 使用各个元素的 compareTo() 方法来比较它们，在与 null 比较时抛出 NullPointerException，这里是一个例子:
null : Both HashSet and LinkedHashSet allows null but TreeSet doesn't allow null and throw java.lang.NullPointerException when you will insert null into TreeSet. Since TreeSet uses compareTo() method of respective elements to compare them which throws NullPointerException while comparing with null, here is an example:
TreeSet cities
Exception in thread "main" java.lang.NullPointerException
at java.lang.String.compareTo(String.java:1167)
at java.lang.String.compareTo(String.java:92)
at java.util.TreeMap.put(TreeMap.java:545)
at java.util.TreeSet.add(TreeSet.java:238)
Comparison : HashSet 和 LinkedHashSet 在 Java 中使用 equals() 方法进行比较，但 TreeSet 使用 compareTo() 方法来维护排序.这就是为什么 compareTo() 应该与 Java 中的 equals 一致.否则会破坏 Set 接口的一般联系，即它可以允许重复.
Comparison : HashSet and LinkedHashSet uses equals() method in Java for comparison but TreeSet uses compareTo() method for maintaining ordering. That's why compareTo() should be consistent to equals in Java. failing to do so break general contact of Set interface i.e. it can permit duplicates.
使用可以使用下面的链接查看内部实现http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/HashSet.java#HashSet.add%28java.lang.Object%29
Use can use below link to see internal implementation http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/HashSet.java#HashSet.add%28java.lang.Object%29
From the source code
Hashset hases Hashmap to store the data and LinkedHashSet extends Hashset and hence uses same add method of Hashset But TreeSet uses NavigableMap to store the data
来源:http://javarevisited.blogspot.com/2012/11/difference-between-treeset-hashset-vs-linkedhashset-java.html#ixzz2lGo6Y9mm
相关文章