【JAVA】TreeSet, LinkedHashSet 和 HashSet 差异对比
TreeSet、LinkedHashSet、HashSet均实现了Set接口，具有Set特点，如都不允许包含相同元素。虽然三者具有很多相似之处，他们依旧存在很多差异之处，而理解这三者的差异之处有助于根据自己选择合适实现功能的Set。而且这三者差异是JAVA常见的面试题之一。
本文重点从元素顺序、性能、是否允许null元素等方面介绍TreeSet，LinkedHashSet和HashSet的差异点，另外也会简单介绍何时使用TreeSet、LinkedHashSet和HashSet。
TreeSet, LinkedHashSet和HashSet是JAVA Collection框架中实现Set接口的3大类，与许多其他Collection一样它们也用于存放对象。TreeSet的主要特点是排序；LinkedHashSet的主要特点是元素顺序遵循插入顺序；HashSet则是存放对象的普通集合。
HashSet使用HashMap来实现，而TreeSet使用TreeMap来实现。TreeSet实现了SortedSet，以便可以保证元素按照定义的Comparable或Comparator接口来排序。
相似点
在对比三者差异之前，我们先来看看三者的相似之处：
1） 不存在重复元素。
2） 非线程安全。多线程编程时需要额外对三者进行同步。
3） Fail-Fast迭代器。迭代器创建后发生变化的原因不是因为迭代器的remove方法，会抛出ConcurrentModificationException 异常，对于删除元素可以使用迭代器的remove方法。
不同点
下面详细介绍TreeSet，LinkedHashSet和HashSet的差异点。
1、性能
HashSet处理速度最快，其次是LinkedHashSet（其处理速度几乎与HashSet相同），TreeSet由于插入元素时需要排序，因此，TreeSet处理速度稍慢。
HashSet > LinkedHashSet > TreeSet
下表是关于增、删、判断元素是否存在三个方法的时间复杂度比较。HashSet、LinkedHashSet由于利用hash函数将元素均匀分布到bucket，其复杂度维持在O(1)；而TreeSet的复杂度维持在O(log(n))。
add remove contains
TreeSet O（log(n)） O（log(n)） O（log(n)）
HashSet O（1） O（1） O（1）
LinkedHashSet O（1） O（1） O（1）
2、元素顺序
HashSet 不维持元素顺序。
LinkedHashSet 元素顺序遵循插入顺序。
TreeSet 元素顺序遵循排序顺序。
3、内部实现
HashSet 基于HashMap。
LinkedHashSet 基于HashSet和LinkedList。
TreeSet 基于NavigableMap，JAVA中默认为TreeMap。
4、是否允许null元素
HashSet和LinkedHashSet都允许null元素，但TreeSet不允许null元素，而且当向TreeSet插入null元素时，TreeSet使用compareTo方法与null元素进行比较，将会出现 java.lang.NullPointerException。如下示例：
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)
5、比较
HashSet和LinkedHashSet使用equals方法来进行比较；而TreeSet使用compareTo方法进行比较来维持元素顺序。这就是为什么compareTo方法需要与equals方法实现保持一致的原因。当compareTo方法与equals方法实现不一致时，这违反了实现Set的特点（不允许元素重复）。
使用HashSet, LinkedHashSet和TreeSet的时机
当元素不允许重复同时有需要排序时，使用TreeSet。
HashSet是Set最基本的实现，当需要一个快速、不允许元素重复的集合时，使用HashSet。
LinkedHashSet是HashSet的子类，其使用场景有两个：
1）当元素需要维持插入顺序时，使用LinkedHashSet。
2）创建一份已有Set的副本。由于LinkedHashSet维持了元素插入顺序，使用LinkedHashSet将会返回一份元素顺序与原集合一致的副本。
参考资料
Fail-Fast迭代器 vs Fail-Safe迭代器
Difference between TreeSet, LinkedHashSet and HashSet
ArrayList VS Vector
https://javarevisited.blogspot.com/2011/09/difference-vector-vs-arraylist-in-java.html#axzz6dkUePc6v
HashMap VS Hashtable
https://javarevisited.blogspot.com/2010/10/difference-between-hashmap-and.html#axzz6dkUePc6v
版权声明: 本文为 InfoQ 作者【莫问】的原创文章。
原文链接:【http://xie.infoq.cn/article/e1b42f77c465f501ba3727c1d】。未经作者许可，禁止转载。
站在现在看未来，站在未来看现在 2019.11.20 加入
居安思危，先忧后乐
评论