本文转发自：https://blog.****.net/a724888/article/details/80295328

今天我们来探索一下HashSet，TreeSet与LinkedHashSet的基本原理与源码实现，由于这三个 Set 都是基于之前文章的三个 Map 进行实现的，所以推荐大家先看一下前面有关 Map 的文章，结合使用味道更佳。

【搞定Java基础-集合】第八篇：HashSet、TreeSet、LinkedHashSet

Collection 集合框架图

1、HashSet

在 HashMap JDK1.7 && JDK 1.8 中详细讲解了 HashMap 的实现过程，对于 HashSet 而言，它是基于 HashMap 来实现的，底层采用 HashMap 来保存元素。所以如果对 HashMap 比较熟悉，那么 HashSet 是 so easy !!!

public class HashSet<E>
	extends AbstractSet<E>
	implements Set<E>, Cloneable, java.io.Serializable

HashSet 继承 AbstractSet 类，实现 Set、Cloneable、Serializable 接口。其中 AbstractSet 提供 Set 接口的骨干实现，从而最大限度地减少了实现此接口所需的工作。Set 接口是一种不包括重复元素的 Collection，它维持它自己的内部排序，所以随机访问没有任何意义。

Set 接口源码

package java.util;
 
public interface Set<E> extends Collection<E> {
	
	int size();
 
	boolean isEmpty();
  
	boolean contains(Object o);
	
	Iterator<E> iterator();
	
	Object[] toArray();
	
	<T> T[] toArray(T[] a);
 
	boolean add(E e);
 
	boolean remove(Object o);
	
	boolean containsAll(Collection<?> c);
 
	boolean addAll(Collection<? extends E> c);
 
	boolean retainAll(Collection<?> c);
 
	boolean removeAll(Collection<?> c);
 
	void clear();
 
	boolean equals(Object o);
 
	int hashCode();
}

AbstractSet 类的源码


package java.util;
 
public abstract class AbstractSet<E> extends AbstractCollection<E> implements Set<E> {
 
	public boolean equals(Object o) {  // 省略实现... }
	
	public int hashCode() {  // 省略实现... }
	
	public boolean removeAll(Collection<?> c) {  // 省略实现... }
 
}

1.1 定义

1.1.1 基本属性：基于HashMap实现，底层使用HashMap保存所有元素，且定义一个Object对象作为HashMap的value

// 基于HashMap实现，底层使用HashMap保存所有元素
private transient HashMap<E,Object> map;
 
// 定义一个Object对象作为HashMap的value
private static final Object PRESENT = new Object();

1.1.2 构造函数

// 默认构造函数：初始化一个空的HashMap，并使用默认初始容量为16和加载因子0.75。
public HashSet() {
	map = new HashMap<>();
}
 
// 构造一个包含指定 collection 中的元素的新 set。
public HashSet(Collection<? extends E> c) {
	map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
	addAll(c);
}
 
// 构造一个新的空 set，其底层 HashMap 实例具有指定的初始容量和指定的加载因子
public HashSet(int initialCapacity, float loadFactor) {
	map = new HashMap<>(initialCapacity, loadFactor);
}
 
// 构造一个新的空 set，其底层 HashMap 实例具有指定的初始容量和默认的加载因子（0.75）。
public HashSet(int initialCapacity) {
   map = new HashMap<>(initialCapacity);
}
 
/**
 * 在API中我没有看到这个构造函数，今天看源码才发现（原来访问权限为包权限，不对外公开的）
 * 以指定的initialCapacity和loadFactor构造一个新的空链接哈希集合。
 * dummy 为标识 该构造函数主要作用是对LinkedHashSet起到一个支持作用
 */
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
   map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

从构造函数中可以看出 HashSet 所有的构造都是构造出一个新的 HashMap，其中最后一个构造函数，为包访问权限是不对外公开，仅仅只在使用 LinkedHashSet 时才会发生作用。

1.2 方法

既然 HashSet 是基于 HashMap，那么对于 HashSet 而言，其方法的实现过程是非常简单的。

iterator()

public Iterator<E> iterator() {
	return map.keySet().iterator();
}

iterator() 方法返回对此 set 中元素进行迭代的迭代器。返回元素的顺序并不是特定的。底层调用 HashMap 的 keySet 返回所有的 key，这点反应了 HashSet 中的所有元素都是保存在 HashMap 的 key 中，value 则是使用的 PRESENT 对象，该对象为 static final。

size()，isEmpty()

public int size() {
	return map.size();
}

public boolean isEmpty() {
	return map.isEmpty();
}

contains(Object o)：底层调用containsKey判断HashMap的key值是否为空。

// HashSet的contains方法
public boolean contains(Object o) {
	return map.containsKey(o);
}
 
// HashMap中的containsKey方法
public boolean containsKey(Object key) {
	return getNode(hash(key), key) != null;
}
 
// 最终调用该方法进行节点查找
final Node<K,V> getNode(int hash, Object key) {
	Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
	// 先检查桶的头结点是否存在
	if ((tab = table) != null && (n = tab.length) > 0 &&
		(first = tab[(n - 1) & hash]) != null) {
		if (first.hash == hash && // always check first node
			((k = first.key) == key || (key != null && key.equals(k))))
			return first;
			// 不是头结点，则遍历链表，如果是树节点则使用树节点的方法遍历，直到找到，或者为null
		if ((e = first.next) != null) {
			if (first instanceof TreeNode)
				return ((TreeNode<K,V>)first).getTreeNode(hash, key);
			do {
				if (e.hash == hash &&
					((k = e.key) == key || (key != null && key.equals(k))))
					return e;
			} while ((e = e.next) != null);
		}
	}
	return null;
}

contains()，判断某个元素是否存在于HashSet()中，存在返回true，否则返回false。更加确切的讲应该是要满足这种关系才能返回true：(o==null ? e==null : o.equals(e))。底层调用containsKey判断HashMap的key值是否为空。

add(E e)


// HashSet的add(E e)方法
public boolean add(E e) {
	return map.put(e, PRESENT)==null;
}
 
// HashMap的put方法
public V put(K key, V value) {
	return putVal(hash(key), key, value, false, true);
}
 
// HashMap的putVal方法：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
			   boolean evict) {
	Node<K,V>[] tab; Node<K,V> p; int n, i;
 
	// 确认初始化
	if ((tab = table) == null || (n = tab.length) == 0)
		n = (tab = resize()).length;
 
	// 如果桶为空，直接插入新元素，也就是entry
	if ((p = tab[i = (n - 1) & hash]) == null)
		tab[i] = newNode(hash, key, value, null);
	else {
		Node<K,V> e; K k;
		// 如果冲突，分为三种情况
		// key相等时让旧entry等于新entry即可
		if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
			e = p;
		// 红黑树情况
		else if (p instanceof TreeNode)
			e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
		else {
			// 如果key不相等，则连成链表
			for (int binCount = 0; ; ++binCount) {
				if ((e = p.next) == null) {
					p.next = newNode(hash, key, value, null);
					if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
						treeifyBin(tab, hash);
					break;
				}
				if (e.hash == hash &&
					((k = e.key) == key || (key != null && key.equals(k))))
					break;
				p = e;
			}
		}
		if (e != null) { // existing mapping for key
			V oldValue = e.value;
			if (!onlyIfAbsent || oldValue == null)
				e.value = value;
			afterNodeAccess(e);
			return oldValue;
		}
	}
	++modCount;
	if (++size > threshold)
		resize();
	afterNodeInsertion(evict);
	return null;
}

注意：

HashSet 只是不允许重复的元素加入，而不是不允许元素连成链表，因为只要 key 的 equals 方法判断为 true 时它们是相等的，此时会发生 value 的替换，因为所有 entry 的 value 一样，所以和没有插入时一样的。

而当两个 HashCode 相同但 key 不相等的 entry 插入时，仍然会连成一个链表，长度超过 8 时依然会和 HashMap 一样扩展成红黑树，看完源码之后笔者才明白自己之前理解错了。所以看源码还是蛮有好处的。HashSet 基本上就是使用 HashMap 的方法再次实现了一遍而已，只不过 value 全都是同一个 object，让你以为相同元素没有插入，事实上只是 value 替换成和原来相同的值而已。

当 add 方法发生冲突时，如果 key 相同，则替换 value，如果 key 不同，则连成链表。

add() 如果此 Set 中尚未包含指定元素，则添加指定元素。如果此 Set 没有包含满足(e == null ? e2 == null : e.equals(e2)) 的 e2 时，则将 e2 添加到 Set 中，否则不添加且返回 false。

由于底层使用 HashMap 的 put 方法将 key = e，value = PRESENT 构建成 key-value 键值对，当此 e 存在于HashMap 的 key 中，则 value 将会覆盖原有 value，但是 key 保持不变，所以如果将一个已经存在的 e 元素添加中 HashSet中，新添加的元素是不会保存到 HashMap 中，所以这就满足了 HashSet 中元素不会重复的特性。

remove(Object o)


public boolean remove(Object o) {
	return map.remove(o) == PRESENT;
}

clear 从此 Set 中移除所有元素。底层调用 HashMap 的 clear 方法清除所有的 Entry。

clone()

public Object clone() {
	try {
		HashSet<E> newSet = (HashSet<E>) super.clone();
		newSet.map = (HashMap<E, Object>) map.clone();
		return newSet;
	} catch (CloneNotSupportedException e) {
		throw new InternalError();
	}
}

clone 返回此 HashSet 实例的浅表副本：并没有复制这些元素本身。

后记：

由于 HashSet 底层使用了 HashMap 实现，使其的实现过程变得非常简单，如果你对 HashMap 比较了解，那么HashSet 简直是小菜一碟。有两个方法对 HashMap 和 HashSet 而言是非常重要的，下篇将详细讲解 hashCode 和 equals。

2、TreeSet：基于 TreeMap 实现的

本部分内容来自于：http://cmsblogs.com/?p=1162

与 HashSet 是基于 HashMap 实现一样，TreeSet 同样是基于 TreeMap 实现的。在上一篇文章：TreeMap 和红黑树中讲解了 TreeMap 的实现机制，如果你详情看了这篇博文或者多 TreeMap 有比较详细的了解，那么 TreeSet 的实现对您是喝口水那么简单。

2.1 TreeSet 定义

我们知道 TreeMap 是一个有序的二叉树，那么同理 TreeSet 同样也是一个有序的，它的作用是提供有序的 Set 集合。通过源码我们知道 TreeSet 基础 AbstractSet，实现 NavigableSet、Cloneable、Serializable 接口。其中 AbstractSet 提供 Set 接口的骨干实现，从而最大限度地减少了实现此接口所需的工作。NavigableSet 是扩展的 SortedSet，具有为给定搜索目标报告最接近匹配项的导航方法，这就意味着它支持一系列的导航方法。比如查找与指定目标最匹配项。Cloneable 支持克隆，Serializable 支持序列化。

public class TreeSet<E> extends AbstractSet<E>
                        implements NavigableSet<E>, Cloneable, java.io.Serializable

同时在 TreeSet 中定义了如下几个变量：

private transient NavigableMap<E,Object> m;
 
// PRESENT会被当做Map的value与key构建成键值对
private static final Object PRESENT = new Object();

其构造方法：

// 默认构造方法，根据其元素的自然顺序进行排序
public TreeSet() {
	this(new TreeMap<E,Object>());
}
 
// 构造一个包含指定 collection 元素的新 TreeSet，它按照其元素的自然顺序进行排序。
public TreeSet(Comparator<? super E> comparator) {
		this(new TreeMap<>(comparator));
}
 
// 构造一个新的空 TreeSet，它根据指定比较器进行排序。
public TreeSet(Collection<? extends E> c) {
	this();
	addAll(c);
}
 
// 构造一个与指定有序 set 具有相同映射关系和相同排序的新 TreeSet。
public TreeSet(SortedSet<E> s) {
	this(s.comparator());
	addAll(s);
}
 
TreeSet(NavigableMap<E,Object> m) {
	this.m = m;
}

2.2 TreeSet 的主要方法：不能加入null

1、add：将指定的元素添加到此 set（如果该元素尚未存在于 set 中）。


// TreeSet中的add方法
public boolean add(E e) {
    // 调用TreeMap中的put方法
	return m.put(e, PRESENT)==null;
}
 
// TreeMap中的put方法
public V put(K key, V value) {
	Entry<K,V> t = root;
	if (t == null) {
	        // 空树时，判断节点是否为空
		compare(key, key); // type (and possibly null) check
 
		root = new Entry<>(key, value, null);
		size = 1;
		modCount++;
		return null;
	}
	int cmp;
	Entry<K,V> parent;
	// split comparator and comparable paths
	Comparator<? super K> cpr = comparator;
	// 非空树，根据传入比较器进行节点的插入位置查找
	if (cpr != null) {
		do {
			parent = t;
			// 节点比根节点小，则找左子树，否则找右子树
			cmp = cpr.compare(key, t.key);
			if (cmp < 0)
				t = t.left;
			else if (cmp > 0)
				t = t.right;
				//如果key的比较返回值相等，直接更新值（一般compareto相等时equals方法也相等）
			else
				return t.setValue(value);
		} while (t != null);
	}
	else {
	        // 如果没有传入比较器，则按照自然排序
		if (key == null)
			throw new NullPointerException();
		@SuppressWarnings("unchecked")
			Comparable<? super K> k = (Comparable<? super K>) key;
		do {
			parent = t;
			cmp = k.compareTo(t.key);
			if (cmp < 0)
				t = t.left;
			else if (cmp > 0)
				t = t.right;
			else
				return t.setValue(value);
		} while (t != null);
	}
	// 查找的节点为空，直接插入，默认为红节点
	Entry<K,V> e = new Entry<>(key, value, parent);
	if (cmp < 0)
		parent.left = e;
	else
		parent.right = e;
        // 插入后进行红黑树调整
	fixAfterInsertion(e);
	size++;
	modCount++;
	return null;
}

2、get：获取元素

该方法与 put 的流程类似，只不过是把插入换成了查找。

public V get(Object key) {
    Entry<K,V> p = getEntry(key);
    return (p==null ? null : p.value);
}

3、ceiling：返回此 set 中大于等于给定元素的最小元素；如果不存在这样的元素，则返回 null。

public E ceiling(E e) {
	return m.ceilingKey(e);
}

4、clear：移除此 set 中的所有元素。

public void clear() {
	m.clear();
}

5、clone：返回 TreeSet 实例的浅表副本。属于浅拷贝。


public Object clone() {
	TreeSet<E> clone = null;
	try {
		clone = (TreeSet<E>) super.clone();
	} catch (CloneNotSupportedException e) {
		throw new InternalError();
	}
 
	clone.m = new TreeMap<>(m);
	return clone;
}

8、descendingIterator：返回在此 set 元素上按降序进行迭代的迭代器。

public Iterator<E> descendingIterator() {
	return m.descendingKeySet().iterator();
}

10、first：返回此 set 中当前第一个（最低）元素。

public E first() {
	return m.firstKey();
}

11、floor：返回此 set 中小于等于给定元素的最大元素；如果不存在这样的元素，则返回 null。

public E floor(E e) {
	return m.floorKey(e);
}

12、headSet：返回此 set 的部分视图，其元素严格小于 toElement。

public SortedSet<E> headSet(E toElement) {
	return headSet(toElement, false);
}

13、higher：返回此 set 中严格大于给定元素的最小元素；如果不存在这样的元素，则返回 null。

public E higher(E e) {
	return m.higherKey(e);
}

15、iterator：返回在此 set 中的元素上按升序进行迭代的迭代器。

public Iterator<E> iterator() {
	return m.navigableKeySet().iterator();
}

16、last：返回此 set 中当前最后一个（最高）元素。

public E last() {
	return m.lastKey();
}

17、lower：返回此 set 中严格小于给定元素的最大元素；如果不存在这样的元素，则返回 null。


public E lower(E e) {
	return m.lowerKey(e);
}

18、pollFirst：获取并移除第一个（最低）元素；如果此 set 为空，则返回 null。

public E pollFirst() {
	Map.Entry<E,?> e = m.pollFirstEntry();
	return (e == null) ? null : e.getKey();
}

19、pollLast：获取并移除最后一个（最高）元素；如果此 set 为空，则返回 null。

public E pollLast() {
	Map.Entry<E,?> e = m.pollLastEntry();
	return (e == null) ? null : e.getKey();

20、remove：将指定的元素从 set 中移除（如果该元素存在于此 set 中）。该方法与put类似，只不过把插入换成了删除，并且要进行删除后调整。

public boolean remove(Object o) {
	return m.remove(o)==PRESENT;
}

2.3 总结

由于 TreeSet 是基于 TreeMap 实现的，所以如果我们对 TreeMap 有了一定的了解，对 TreeSet 那是小菜一碟，我们从 TreeSet 中的源码可以看出，其实现过程非常简单，几乎所有的方法实现全部都是基于 TreeMap 的。

3、LinkedHashSet

3.1 LinkedHashSet 内部是如何工作的

LinkedHashSet 是 HashSet 的一个“扩展版本”，HashSet 并不管什么顺序，不同的是 LinkedHashSet 会维护“插入顺序”。HashSet 内部使用 HashMap 对象来存储它的元素，而 LinkedHashSet 内部使用 LinkedHashMap 对象来存储和处理它的元素。这部分内容，我们将会看到 LinkedHashSet 内部是如何运作的及如何维护插入顺序的。

LinkedHashSet 的源码

package java.util;
 
public class LinkedHashSet<E>
             extends HashSet<E>
             implements Set<E>, Cloneable, java.io.Serializable {
 
	private static final long serialVersionUID = -2851667679971038690L;
 
	// 构造函数1：自定义容量 & 加载因子
	public LinkedHashSet(int initialCapacity, float loadFactor) {
		super(initialCapacity, loadFactor, true);
	}
 
	// 构造函数2：自定义容量 & 默认加载因子0.75 
	public LinkedHashSet(int initialCapacity) {
		super(initialCapacity, .75f, true);
	}
 
	// 构造函数3：默认容量16 & 默认加载因子0.75 
	public LinkedHashSet() {
		super(16, .75f, true);
	}
 
	// 构造函数4：初始化为一个小集合
	public LinkedHashSet(Collection<? extends E> c) {
		super(Math.max(2*c.size(), 11), .75f, true);
		addAll(c);
	}
}

这里需要说明一个问题，从 LinkedHashSet 源码中我们并不能看到它是怎么用 LinkedHashMap 来存储和处理元素的。因为它的父类是 HashSet，而 HashSet 其实是用 HashMap 来存储和处理元素的。那怎么将 LinkedHashTree 和 LinkedHashSet 建立联系呢？

其实看下面的 LinkedHashSet 的源码中的构造函数，你不难发现它的构造函数都是调用它的父类 HashSet 中的构造函数来完成的，那么现在我们将 HashSet 中的构造函数的源码贴出来:

public class HashSet<E>
             extends AbstractSet<E>
             implements Set<E>, Cloneable, java.io.Serializable{
	
	private transient HashMap<E,Object> map;
 
	private static final Object PRESENT = new Object();
 
	// 构造函数1：通过调用HashMap的构造函数进行初始化
	public HashSet() {
		map = new HashMap<>();
	}
 
	// 构造函数2：通过调用HashMap的构造函数进行初始化
	public HashSet(Collection<? extends E> c) {
		map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
		addAll(c);
	}
 
	// 构造函数3：通过调用HashMap的构造函数进行初始化
	public HashSet(int initialCapacity, float loadFactor) {
		map = new HashMap<>(initialCapacity, loadFactor);
	}
 
	// 构造函数4：通过调用HashMap的构造函数进行初始化
	public HashSet(int initialCapacity) {
		map = new HashMap<>(initialCapacity);
	}
 
	// 构造函数5：通过调用LinkedHashMap的构造函数进行初始化
	// 第3个参数用于区别前面的构造函数
	HashSet(int initialCapacity, float loadFactor, boolean dummy) {
		map = new LinkedHashMap<>(initialCapacity, loadFactor);
	}
	
	// ...
}

我们通过 HashSet 中的第 5 个构造函数就能明白，虽然在 LinkedHashSet 中我们调用的是它父类 HashSet 的构造函数，但实际上是调用了 LinkedHashMap 的构造函数进行了初始化。也就意味着：LinkedHashSet 是 LinkedHashMap 来存储和处理元素的。

显然，这个构造函数内部初始化了一个 LinkedHashMap 对象，这个对象恰好被 LinkedHashSet 用来存储它的元素。LinkedHashSet 并没有自己的方法，所有的方法都继承自它的父类 HashSet，因此，对 LinkedHashSet 的所有操作方式就好像对 HashSet 操作一样。

唯一的不同是内部使用不同的对象去存储元素。在 HashSet 中，插入的元素是被当做 HashMap 的键来保存的，而在LinkedHashSet 中被看作是 LinkedHashMap 的键。

这些键对应的值都是常量PRESENT（PRESENT 是 HashSet 的 final 类型静态成员变量，）。

LinkedHashSet 是如何维护插入顺序的？

LinkedHashSet 使用 LinkedHashMap 对象来存储它的元素，插入到 LinkedHashSe t中的元素实际上是被当作LinkedHashMap 的键保存起来的。LinkedHashMap 的每一个键值对都是通过内部的静态类 Entry 来维护的。

【搞定Java基础-集合】 第八篇：HashSet、TreeSet、LinkedHashSet

1、HashSet

1.1 定义

1.1.1 基本属性：基于HashMap实现，底层使用HashMap保存所有元素，且定义一个Object对象作为HashMap的value

1.1.2 构造函数

1.2 方法

iterator()

size()，isEmpty()

contains(Object o)：底层调用containsKey判断HashMap的key值是否为空。

add(E e)

remove(Object o)

clone()

后记：