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)Fail-Fast Iterator:TreeSet返回的迭代器,LinkedHashSet和HashSet是故障快速迭代器.即如果Iterator在创建之后通过除Iterators remove()方法以外的任何方式进行修改,它将尽力抛出ConcurrentModificationException.在此处阅读有关故障快速与故障安全迭代器的更多信息

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

性能和速度:它们之间的第一个区别在于速度.HashSet是最快的,LinkedHashSet在性能上排名第二或几乎与HashSet类似,但TreeSet因为每次插入时需要执行的排序操作而有点慢.TreeSet为常见操作(如add,remove和contains)提供了保证的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

Answer 2

这张图片可以帮到你......

图片来源:http://javaconceptoftheday.com/hashset-vs-linkedhashset-vs-treeset-in-java/