JAVA集合:常见Set源码学习

677 阅读7分钟

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

总结

  • HashSet其实是使用HashMap的key值集合来实现的,所以不能有重复的元素。
  • LinkedHashSet继承了HashSet,用LinkedHashMap的key值集合来实现其功能,所以不能有重复元素,并且以插入元素的顺序排序。
  • TreeSet是使用有序的Map来实现的,默认使用的是TreeMap。

Set其实就是Map的key集合,用Map来实现Set,所以掌握了Map基本上就学会了Set。