更多 Java 集合类方面的文章，请参见文集《Java 集合类》
共同点：
- 都不能包含重复元素，用 equals 方法判断
- 都是线程不安全的
- Fail-fast behavior
基本区别：
-
迭代顺序：
- HashSet ：遍历时没有特定的顺序，从前到后遍历链表散列（数组 + 链表）。
- LinkedHashSet ：遍历时按照插入的顺序或者访问的顺序。
- TreeSet ：遍历时按照元素升序（通过元素的 compareTo 方法进行比较）。
-
put/remove/get 时间复杂度
- HashSet ：O(1)
- LinkedHashSet ：O(1)
- TreeSet ：O(lgN)
-
是否允许空的元素
- HashSet ：允许空的元素，因为 HashSet 基于 HashMap 实现，HashMap 允许空的 key
- LinkedHashSet ：允许空的元素，因为 LinkedHashSet 基于 LinkedHashMap 实现，LinkedHashMap 允许空的 key
- TreeSet ：元素不能为空，因为 TreeSet 基于 TreeMap 实现，HashMap 不允许空的 key，否则会产生运行时异常。
-
实现方式
- HashSet ：基于 HashMap
- LinkedHashSet ：基于 LinkedHashMap
- TreeSet ：基于 TreeMap
HashSet 的实现原理
构造
public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable
{
static final long serialVersionUID = -5024744406713321676L;
private transient HashMap<E,Object> map;
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
/**
* Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
* default initial capacity (16) and load factor (0.75).
*/
public HashSet() {
map = new HashMap<>();
}
可以看出，对于 HashSet 而言，它是基于 HashMap 实现的，HashSet 底层使用 HashMap 来保存所有元素。
因此 HashSet 的实现比较简单，相关 HashSet 的操作，基本上都是直接调用底层 HashMap 的相关方法来完成，我们应该为保存到 HashSet 中的对象覆盖 hashCode() 和 equals()。
添加元素
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
要添加的元素 e 作为 key，构造一个键值对 <e, PRESENT>，然后调用 HashMap 的 put 方法。（PRESENT 为一个对象，在上面的构造方法中可以看出）
如果此 set 中尚未包含指定元素，则添加指定元素。更确切地讲，如果此 set 没有包含满足(e==null ? e2==null : e.equals(e2)) 的元素 e2，则向此 set 添加指定的元素 e。如果此 set 已包含该元素，则该调用不更改 set 并返回 false。但底层实际将将该元素作为 key 放入 HashMap。
LinkedHashSet 的实现原理
构造
public class LinkedHashSet<E>
extends HashSet<E>
implements Set<E>, Cloneable, java.io.Serializable {
private static final long serialVersionUID = -2851667679971038690L;
/**
* Constructs a new, empty linked hash set with the specified initial
* capacity and load factor.
*
* @param initialCapacity the initial capacity of the linked hash set
* @param loadFactor the load factor of the linked hash set
* @throws IllegalArgumentException if the initial capacity is less
* than zero, or if the load factor is nonpositive
*/
public LinkedHashSet(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor, true);
}
可以看出：
- LinkedHashMap 继承了 HashMap
- LinkedHashSet 继承了 HashSet，实际上是创建了一个 LinkedHashMap：
在 LinkedHashSet 构造方法中调用了父类 HashSet 的构造方法super(initialCapacity, loadFactor, true);
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
因此 LinkedHashSet 的实现原理可以参考 LinkedHashMap的实现原理
TreeSet 的实现原理
构造
可以看出 TreeSet 在构造方法中实际上创建了一个 TreeMap。
public class TreeSet<E> extends AbstractSet<E>
implements NavigableSet<E>, Cloneable, java.io.Serializable
{
/**
* The backing map.
*/
private transient NavigableMap<E,Object> m;
// Dummy value to associate with an Object in the backing Map
private static final Object PRESENT = new Object();
/**
* Constructs a set backed by the specified navigable map.
*/
TreeSet(NavigableMap<E,Object> m) {
this.m = m;
}
/**
* Constructs a new, empty tree set, sorted according to the
* natural ordering of its elements. All elements inserted into
* the set must implement the {@link Comparable} interface.
* Furthermore, all such elements must be <i>mutually
* comparable</i>: {@code e1.compareTo(e2)} must not throw a
* {@code ClassCastException} for any elements {@code e1} and
* {@code e2} in the set. If the user attempts to add an element
* to the set that violates this constraint (for example, the user
* attempts to add a string element to a set whose elements are
* integers), the {@code add} call will throw a
* {@code ClassCastException}.
*/
public TreeSet() {
this(new TreeMap<E,Object>());
}
