移步数据结构--容器汇总（java & Android）
内容：
- Set 集合概述
- HashSet 源码简单分析
- LinkedHashSet 源码简单分析
- 关于面试中的集合问题总结
一、 set集合概述
image
- Set 主要的实现类有 HashSet 和 TreeSet 以及LinkedHashSet。
- HashSet 的实现依赖于 HashMap， TreeSet 的实现依赖于 TreeMap，LinkedHashSet 的实现依赖于 LinkedHashMap。
···
public class HashSet<E>
extends AbstractSet<E>
implements Set<E>, Cloneable, java.io.Serializable
public class LinkedHashSet<E>
extends HashSet<E>
implements Set<E>, Cloneable, java.io.Serializable
public class TreeSet<E> extends AbstractSet<E>
implements NavigableSet<E>, Cloneable, java.io.Serializable
···
在看 Set 的源码之前，我们先概括的说下 Set 集合的特点
- HashSet 底层是数组 + 单链表 + 红黑树的数据结构
- LinkedHashSet 底层是 数组 + 单链表 + 红黑树 + 双向链表的数据结构
- Set 不允许存储重复元素，允许存储 null
- HashSet 存储元素是无序且不等于访问顺序
- LinkedHashSet 存储元素是无序的，但是由于双向链表的存在，迭代时获取元素的顺序等于元素的添加顺序，注意这里不是访问顺序
二、 HashSet 的源码分析
HashSet 源码只有短短的 300 行，上文也阐述了实现依赖于 HashMap，这一点充分体现在其构造方法和成员变量上。我们来看下 HashSet 的构造方法和成员变量：
// HashSet 真实的存储元素结构
private transient HashMap<E,Object> map;
// 作为各个存储在 HashMap 元素的键值对中的 Value
private static final Object PRESENT = new Object();
//空参数构造方法 调用 HashMap 的空构造参数
//初始化了 HashMap 中的加载因子 loadFactor = 0.75f
public HashSet() {
map = new HashMap<>();
}
//指定期望容量的构造方法
public HashSet(int initialCapacity) {
map = new HashMap<>(initialCapacity);
}
//指定期望容量和加载因子
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<>(initialCapacity, loadFactor);
}
//使用指定的集合填充Set
public HashSet(Collection<? extends E> c) {
//调用 new HashMap<>(initialCapacity) 其中初始期望容量为 16 和 c 容量 / 默认 load factor 后 + 1的较大值
map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
addAll(c);
}
// 该方法为 default 访问权限，不允许使用者直接调用，目的是为了初始化 LinkedHashSet 时使用
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
- 通过 HashSet 的构造参数我们可以看出每个构造方法，都调用了对应的 HashMap 的构造方法用来初始化成员变量 map
- 因此我们可以知道，HashSet 的初始容量也为 1<<4 即16，加载因子默认也是 0.75f。
- 我们都知道 Set 不允许存储重复元素，又由构造参数得出结论底层存储结构为 HashMap,那么这个不可重复的属性必然是有 HashMap 中**存储键值对的 Key **来实现了。
- 在分析 HashMap 的时候，提到过 HashMap 通过存储键值对的 Key 的 hash 值（经过扰动函数hash()处理后）来决定键值对在哈希表中的位置，当 Key 的 hash 值相同时，再通过 equals 方法判读是否是替换原来对应 key 的 Value 还是存储新的键值对。
- 那么我们在使用 Set 方法的时候也必须保证，存储元素的 HashCode 方法以及 equals 方法被正确覆写。
HashSet 中的添加元素的方法也很简单，我们来看下实现：
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
可以看出 add 方法调用了 HashMap 的 put 方法，构造的键值对的 key 为待添加的元素，而Value 这时有全局变量 PRESENT 来充当，这个PRESENT只是一个 Object 对象。
除了 add 方法外 HashSet 实现了 Set 接口中的其他方法这些方法有：
public int size() {
return map.size();
}
public boolean isEmpty() {
return map.isEmpty();
}
public boolean contains(Object o) {
return map.containsKey(o);
}
//调用 remove(Object key) 方法去移除对应的键值对
public boolean remove(Object o) {
return map.remove(o)==PRESENT;
}
public void clear() {
map.clear();
}
// 返回一个 map.keySet 的 HashIterator 来作为 Set 的迭代器
public Iterator<E> iterator() {
return map.keySet().iterator();
}
HashSet 由于只关注 Key 的内容，所以使用 HashMap 的内部类 KeySet 返回了一个 KeyIterator ，这样在调用 next 方法的时候就可以直接获取下个节点的 key 了。
//HashMap 中的迭代器
final class KeyIterator extends HashIterator
implements Iterator<K> {
public final K next() { return nextNode().key; }
}
final class ValueIterator extends HashIterator
implements Iterator<V> {
public final V next() { return nextNode().value; }
}
final class EntryIterator extends HashIterator
implements Iterator<Map.Entry<K,V>> {
public final Map.Entry<K,V> next() { return nextNode(); }
}
三、 LinkedHashSet 源码分析
- LinkedHashSet 由于继承自 HashSet 使得其代码更加简单只有短短100多行
- LinkedHashSet的构造方法一共有四个，统一调用了父类的 HashSet(int initialCapacity, float loadFactor, boolean dummy)构造方法。
- 在上述分析 HashSet 构造方法的时候，有一个 default 权限的构造方法没有讲，只说了其跟 LinkedHashSet 构造有关系，该构造方法内部调用的是 LinkedHashMap 的构造方法。
//初始化 LinkedHashMap 的初始容量为诶 16 加载因子为 0.75f
public LinkedHashSet() {
super(16, .75f, true);
}
//初始化 LinkedHashMap 的初始容量为 Math.max(2*c.size(), 11) 加载因子为 0.75f
public LinkedHashSet(Collection<? extends E> c) {
super(Math.max(2*c.size(), 11), .75f, true);
addAll(c);
}
//初始化 LinkedHashMap 的初始容量为参数指定值 加载因子为 0.75f
public LinkedHashSet(int initialCapacity) {
super(initialCapacity, .75f, true);
}
//初始化 LinkedHashMap 的初始容量,加载因子为参数指定值
public LinkedHashSet(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor, true);
}
完了..没错，LinkedHashSet 源码就这几行，所以可以看出其实现依赖于 LinkedHashMap 内部的数据存储结构。
