HashSet vs TreeSet vs LinkedHashSet基于添加重复值 [英] HashSet vs TreeSet vs LinkedHashSet on basis of adding duplicate value
问题描述
我正在学习核心java的核心，即集合。我想知道在 HashSet中添加重复元素时内部会发生什么， TreeSet ， LinkedHashSet 。
I am learning heart of core java i.e. Collections.I would like to know that what happens internally when we add duplicate element in HashSet, TreeSet, LinkedHashSet.
天气条目被替换，忽略或抛出异常并且程序终止。一个子问题是，哪一个操作具有相同或平均时间复杂度
我们将非常感谢您的回复。
Your response will be greatly appreciated.
推荐答案
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）重复：所有三个实现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在创建之后通过除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为诸如add，remove和contains之类的常见操作提供了保证的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.
排序：当LinkedHashSet维护元素的插入顺序时，HashSet不维护任何顺序像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并且当你需要时抛出java.lang.NullPointerException将null插入TreeSet。由于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)
比较：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
这篇关于HashSet vs TreeSet vs LinkedHashSet基于添加重复值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
