HashSet vs TreeSet vs LinkedHashSet在添加重复值的基础上

Question

我正在学习核心Java的心脏，即Collections。我想知道，当我们在添加重复元素什么内部发生HashSet，TreeSet，LinkedHashSet。

无论条目被替换，忽略还是引发异常，程序都将终止 。一个子问题是， 哪个 问题 的所有操作都具有相同或平均的时间复杂度

您的答复将不胜感激。

Answer 1

Java中的TreeSet，LinkedHashSet和HashSet是集合框架中的三个Set实现，与许多其他对象一样，它们也用于存储对象。TreeSet的主要功能是排序，LinkedHashSet是插入顺序，HashSet只是用于存储对象的通用集合。HashSet是使用Java中的HashMap实现的，而TreeSet是使用TreeMap实现的。TreeSet是SortedSet实现，允许它按Comparable或Comparator接口定义的排序顺序保留元素。Comparable用于自然顺序排序，而Comparator用于对象的自定义顺序排序，可在创建TreeSet实例时提供。无论如何，在看到TreeSet，LinkedHashSet和HashSet之间的区别之前，让我们看看它们之间的一些相似之处：

1）重复项：这三个工具都有Set接口，表示它们不允许存储重复项。

2）线程安全性：HashSet，TreeSet和LinkedHashSet不是线程安全的，如果您在多线程环境中使用它们（至少一个线程修改了Set），则需要从外部对其进行同步。

3）失败快速迭代器：TreeSet，LinkedHashSet和HashSet返回的迭代器是失败快速迭代器。即，如果Iterator在创建之后通过Iterators
remove（）方法以外的任何其他方式进行了修改，则将尽最大努力抛出ConcurrentModificationException。在这里阅读更多关于快速失败与安全失败迭代器的信息

现在，让我们看看Java中的HashSet，LinkedHashSet和TreeSet之间的区别：

性能和速度：它们之间的首要区别在于速度。HashSet最快，LinkedHashSet在性能上排名第二，或几乎与HashSet相似，但是TreeSet稍慢一些，因为它需要在每次插入时执行排序操作。TreeSet为添加，删除和包含之类的常见操作提供了保证的O（log（n））时间，而HashSet和LinkedHashSet提供了恒定的时间性能，例如，给定，包含和删除给定哈希函数的O（1）将元素均匀分布在存储桶中。

排序：HashSet不维护任何顺序，而LinkedHashSet维护元素的插入顺序，就像List接口，而TreeSet维护排序顺序或元素。

内部实现：HashSet由HashMap实例支持，LinkedHashSet使用HashSet和LinkedList实现，而TreeSet由Java中的NavigableMap备份，并且默认情况下使用TreeMap。

null：HashSet和LinkedHashSet都允许null，但是TreeSet不允许null，并且在将null插入TreeSet时抛出java.lang.NullPointerException。由于TreeSet使用各个元素的compareTo（）方法进行比较，因此与null进行比较时会抛出NullPointerException，这是一个示例：

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接口的一般联系，即它可能允许重复。

使用可以使用下面的链接查看内部实现
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