Java集合源码分析-HashSet和LinkedHashSet

前两篇文章分别分析了Java的ArrayList和LinkedList实现原理，这篇文章分析下HashSet和LinkedHashSet的源码。重点讲解HashSet，因为LinkedHashSet是继承自HashSet，只是它的成员变量map类型是LinkedHashMap而不是HashMap。
HashSet和LinkedHashSet只能使用Iterator进行遍历(解释下foreach底层实现也是基于Iterator)，而在Java的java.util包下的集合框架中，所有的Iterator遍历都是fail-fast的，java.util.concurrent包下的集合框架中，所有的Iterator遍历都是fail-safe的。

HashSet类图

HashSet类图
HashSet只有两个成员变量：map: HashMap<E,Object>和PRESENT: Object，所以操作函数都是通过map实现的，PRESENT: Object是指map所有key的value都是PRESENT: Object。
HashSet实现Set接口，是一个不包含重复元素的一个无序的集合，允许使用null，最多允许一个元素为null。
HashSet也是一个非同步的方法，如果要在多个线程中使用，要注意进行同步封装！
Set s = Collections.synchronizedSet(new HashSet(...));

HashSet构造器

HashSet的构造器比较多，共提供了5个：

    public HashSet() {
        map = new HashMap<>();
    }

    public HashSet(Collection<? extends E> c) {
        map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
        addAll(c);
    }

    public HashSet(int initialCapacity, float loadFactor) {
        map = new HashMap<>(initialCapacity, loadFactor);
    }

    public HashSet(int initialCapacity) {
        map = new HashMap<>(initialCapacity);
    }

    HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }

请注意第5个构造器，它的第三个参数表示是LinkedHashSet调用的，那么将map的类型改为LinkedHashMap。

HashSet核心操作

HashSet核心操作包括：

1. size():int
2. add(E):boolean
3. remove(o:Object):boolean
4. contains(o:Object):boolean
5. iterator():Iterator<E>
6. clone():Object

size():int

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

add(E):boolean

    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }

其实调用的是HashMap的put方法。

remove(o:Object):boolean

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

其实调用的是HashMap的remove方法。

contains(o:Object):boolean

    public boolean contains(Object o) {
        return map.containsKey(o);
    }

其实调用的是HashMap的contains方法。

iterator():Iterator<E>

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

可以看出，HashSet的迭代器就是HashMap的key的迭代器，而且跟ArrayList和LinkedList一样是fail-fast的。

clone():Object

    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(e);
        }
    }

克隆出一个新的HashSet，注意是浅拷贝。

LinkedHashSet

LinkedHashSet继承自HashSet，源码更少、更简单，唯一的区别是LinkedHashSet内部使用的是LinkHashMap。这样做的意义或者好处就是LinkedHashSet中的元素顺序是可以保证的，也就是说遍历序和插入序是一致的。^引用