移步数据结构--容器汇总（java & Android）
内容：

1. Set 集合概述
2. HashSet 源码简单分析
3. LinkedHashSet 源码简单分析
4. 关于面试中的集合问题总结

一、 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 集合的特点

1. HashSet 底层是数组 + 单链表 + 红黑树的数据结构
2. LinkedHashSet 底层是 数组 + 单链表 + 红黑树 + 双向链表的数据结构
3. Set 不允许存储重复元素，允许存储 null
4. HashSet 存储元素是无序且不等于访问顺序
5. 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 内部的数据存储结构。

参考

搞懂 HashSet & LinkedHashSet 源码以及集合常见面试题目