转载

JAVA集合：常见Set源码学习

Set也是Java集合中重要的一部分，我们常见的Set有HashSet，LinkedHashSet，TreeSet，虽然平时可能不是很常用，但是基础还要有必要学习一下的。（以下源码来自jdk1.8.0_20）

HashSet

HashSet其实很简单，源代码量也比较少，学习过HashMap之后基本上看一遍就懂了，关于HashMap可以看一下之前的文章【HashMap源码深度解析】

继承结构

HashSet继承了HashSet，实现了Set接口以及Cloneable, java.io.Serializable接口。

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

成员变量

HashSet其实是使用HashMap的key集合来实现的，所以有个HashMap成员变量

private transient HashMap<E,Object> map;

map中的value值，set只需要使用到key集合，所以value使用new Object即可

private static final Object PRESENT = new Object();

构造函数

从HashSet的构造参数其实就是初始化了一个HashMap。

最后一个构造函数不是public声明的，而是default（同包访问权限），所以我们无法使用，这个构造函数是为了给LinkedHashSet重写用的，第三个参数其实没有作用，而是直接调用了LinkedHashMap的两个参数的构造函数，默认以插入顺序排序

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

主要方法

add方法，增加一个元素，调用的HashMap的put方法

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

contains方法，判断元素是否存在，调用的HashMap的containsKey方法

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

remove方法，删除一个元素，调用的HashMap的remove方法，返回值和PRESENT比较。（如果不存在则返回null和PRESENT比较返回false）

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

size方法，返回set大小，调用的HashMap的size方法

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

isEmpty方法，判断set是否为空，调用HashMap的isEmpty方法

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

clear方法，清空set中的元素，调用HashMap的clear方法

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

clone方法，复制set，先调用父类Object的clone方法，再调用HashMap的clone方法复制map

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

iterator迭代器，返回的是map的key集合的迭代器

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

LinkedHashSet

LinkedHashSet更加简单，继承了HashSet，构造函数调用了上面HashSet的最后一个构造函数，用LinkedHashMap实现，其他主要方法继承自HashSet，没有单独实现。

继承关系

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

构造函数

构造函数都是调用父类HashSet的构造方法，使用LinkedHashMap的key值集合来实现。

public LinkedHashSet(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor, true);
    }
    
    public LinkedHashSet(int initialCapacity) {
        super(initialCapacity, .75f, true);
    }
    
    public LinkedHashSet() {
        super(16, .75f, true);
    }
    
    public LinkedHashSet(Collection<? extends E> c) {
        super(Math.max(2*c.size(), 11), .75f, true);
        addAll(c);
    }

TreeSet

从上面两种set可以看出来set其实就是用对应的map的key值集合来实现的，TreeSet对应的就是有序Map了，默认是TreeMap。关于TreeMap的构造，增加删除元素之后调整的原理可以参考 JAVA集合：TreeMap红黑树深度解析

继承关系

TreeSet继承了AbstractSet类，并且实现了NavigableSet接口以及Cloneable, java.io.Serializable接口，NavigableSet接口继承了SortedSet接口。

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

成员变量

有序map集合，NavigableMap是SortedMap的子类

private transient NavigableMap<E,Object> m;

map的value值

private static final Object PRESENT = new Object();

构造函数

从构造函数可以看出来TreeSet其实是用有序Map来实现的，默认使用TreeMap。

TreeSet(NavigableMap<E,Object> m) {
        this.m = m;
    }
    
    public TreeSet() {
        this(new TreeMap<E,Object>());
    }
    
    public TreeSet(Comparator<? super E> comparator) {
        this(new TreeMap<>(comparator));
    }
    
    public TreeSet(Collection<? extends E> c) {
        this();
        addAll(c);
    }
    
    public TreeSet(SortedSet<E> s) {
        this(s.comparator());
        addAll(s);
    }

常用方法

add方法，增加一个元素，直接调用TreeMap的put方法，e作为key值，value值为PRESENT。

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

addAll方法，把集合中的元素插入到set中

public  boolean addAll(Collection<? extends E> c) {
        // Use linear-time version if applicable
        if (m.size()==0 && c.size() > 0 &&
            c instanceof SortedSet &&
            m instanceof TreeMap) {
            SortedSet<? extends E> set = (SortedSet<? extends E>) c;
            TreeMap<E,Object> map = (TreeMap<E, Object>) m;
            Comparator<?> cc = set.comparator();
            Comparator<? super E> mc = map.comparator();
            if (cc==mc || (cc != null && cc.equals(mc))) {
                map.addAllForTreeSet(set, PRESENT);
                return true;
            }
        }
        return super.addAll(c);
    }

first方法，获取第一个（最小的）元素，直接调用Map的firstKey，返回最左边的元素

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

last方法，获取最后一个（最大的）元素，调用Map的lastKey方法，返回最右边的元素

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

floor方法，获取小于等于给定元素的最大元素，调用Map的floorKey方法

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

以默认的TreeMap为例

public K floorKey(K key) {
        return keyOrNull(getFloorEntry(key));
    }
    
    final Entry<K,V> getFloorEntry(K key) {
        Entry<K,V> p = root;
        while (p != null) {     //根节点不为null，进入循环，否则直接返回null
            int cmp = compare(key, p.key);
            if (cmp > 0) {      //如果key大于当前节点
                if (p.right != null)    //如果right不为null，说明有更大的节点，继续循环right节点
                    p = p.right;
                else                    //否则说明当前节点最大，并且小于key，直接返回
                    return p;
            } else if (cmp < 0) {   //如果key小于当前节点，则查找左子树
                if (p.left != null) {   //如果left不为null，继续循环left
                    p = p.left;
                } else {                //否则查找比当前节点更小的节点（向上查找）
                    Entry<K,V> parent = p.parent;
                    Entry<K,V> ch = p;
                    while (parent != null && ch == parent.left) {   //如果当前节点是左孩子，说明父节点较大，继续向上查找
                        ch = parent;
                        parent = parent.parent;
                    }   //直到节点是右孩子，此时的父节点比当前节点小，继续循环父节点
                    return parent;
                }
            } else      //如果相等，直接返回
                return p;

        }
        return null;
    }

ceiling方法，获取大于给定元素的最小元素，调用Map的getCeilingEntry方法

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

以TreeMap为例，此方法和上面的getFloorEntry方法正好相反

public K ceilingKey(K key) {
        return keyOrNull(getCeilingEntry(key));
    }
    
    final Entry<K,V> getCeilingEntry(K key) {
        Entry<K,V> p = root;
        while (p != null) {
            int cmp = compare(key, p.key);
            if (cmp < 0) {
                if (p.left != null)
                    p = p.left;
                else
                    return p;
            } else if (cmp > 0) {
                if (p.right != null) {
                    p = p.right;
                } else {
                    Entry<K,V> parent = p.parent;
                    Entry<K,V> ch = p;
                    while (parent != null && ch == parent.right) {
                        ch = parent;
                        parent = parent.parent;
                    }
                    return parent;
                }
            } else
                return p;
        }
        return null;
    }

higher方法，获取大于给定元素的最小元素，此方法和getCeilingEntry方法一样

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

lower方法，返回小于给定元素的最大元素，调用Map的getLowerEntry方法，和getFloorEntry方法一样

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

pollFirst方法，返回第一个元素并删除，调用Map的pollFirstEntry方法

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

以TreeMap为例，获取第一个元素，如果不为null，则删除，如果为null，则新建一个entry返回

public Map.Entry<K,V> pollFirstEntry() {
        Entry<K,V> p = getFirstEntry();
        Map.Entry<K,V> result = exportEntry(p);
        if (p != null)
            deleteEntry(p);
        return result;
    }
    
    static <K,V> Map.Entry<K,V> exportEntry(TreeMap.Entry<K,V> e) {
        return (e == null) ? null :
            new AbstractMap.SimpleImmutableEntry<>(e);
    }

pollLast方法，返回最后一个元素并删除，和pollFirst对应

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

contains方法，判断是否含有给定的元素，调用Map的containsKey方法

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

remove方法，删除给定的元素，调用Map的remove方法

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

clear方法，清空set中的元素，调用Map的clear方法

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

isEmpty方法，判断set是否为空，调用Map的isEmpty方法

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

iterator迭代器，返回Map的key值集合的迭代器

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

subSet，获取子set

public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
                                  E toElement,   boolean toInclusive) {
        return new TreeSet<>(m.subMap(fromElement, fromInclusive,
                                       toElement,   toInclusive));
    }