Java HashSet LinkedHashSet TreeSet类源码解析

  1. 云栖社区>
  2. 博客>
  3. 正文

Java HashSet LinkedHashSet TreeSet类源码解析

灰色的风 2018-08-19 11:14:00 浏览1383
展开阅读全文

Set集合中不含有重复的元素,插入重复的元素会失败。常用的有HashSet LinkedHashSet TreeSet。HashSet是无序的集合,LinkedHashSet中的排序和插入成功的顺序一致重复插入,TreeSet中元素是有序排列的,排序的依据是自身的comparator如果为null则根据key从小到大排序。HashSet和LinkedHashSet都是支持插入null的,TreeSet是否支持视comparator的情况,如果comparator不支持比较null的大小或者没有自定义的comparator则不支持插入null


HashSet

HashSet是基于HashMap实现的Set集合,所以支持插入null,但是不保持任何顺序。add成功时返回true,add已有元素时返回false。remove已有元素成功时返回true,remove不存在的元素时失败返回false。和HashMap一样是非线程安全类

    public static void main(String args[]){
        Set<String> set = new HashSet<>();
        System.out.println(set.add("123"));//true
        System.out.println(set.add("123"));//false
        System.out.println(set.add(null));//true
        System.out.println(set.remove(null));//true
        System.out.println(set.remove(null));//false
    }

定义与构造函数

首先从定义上来看,HashSet实现的是Set接口,Set是一种没有重复元素的集合,比如HashMap的KeySet就是一种Set集合

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

从属性中可以看出,他是基于HashMap来实现的,PRESENT是Map跟底层Map相关联的虚拟值,实际上所有对HashSet的操作底层都可以理解为value=PRESENT的对HashMap的操作,后面几个方法中会用到

    private transient HashMap<E,Object> map;

    private static final Object PRESENT = new Object();

然后来看构造函数,无参构造默认构建一个大小为16,负载因子为0.75的HashMap;复制构造时取c/0.75+1和16中的较大值作为大小,负载因子0.75;可以单独设定初始大小,负载因子取默认的0.75,也可以同时指定负载因子;最后一种HashSet(int initialCapacity, float loadFactor, boolean dummy)是内部方法只有LinkedHashSet使用,构建一个链表式HashSet,底层是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);
    }

对集合的操作函数

上面提到了,HashSet底层是基于HashMap的KeySet,所有value都是PRESENT,所以只需要增加参数后复用HashMap的操作即可完成大部分对HashSet的操作

    //返回迭代器
    public Iterator<E> iterator() {
        return map.keySet().iterator();
    }
    //返回元素个数
    public int size() {
        return map.size();
    }
    //返回集合是否为空
    public boolean isEmpty() {
        return map.isEmpty();
    }
    //返回Set中是否含有某个对象,底层通过HashMap.containKey实现
    public boolean contains(Object o) {
        return map.containsKey(o);
    }
    //添加元素e,对于底层来说相等于添加键值对(e,PRESENT),因为map.put会返回旧元素值,而set中不含有重复值,所以若直接map中不存在e则返回null此时函数返回true;而已有e时返回的是e,函数返回值为false
    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }
    //移除某个对象,map.remove方法移除了已有的键值对返回的是value的值,对于Set来说也就是PRESENT,所以返回PRESENT相当于移除成功返回true
    public boolean remove(Object o) {
        return map.remove(o)==PRESENT;
    }
    //直接清除map中的所有对象
    public void clear() {
        map.clear();
    }

clone方法就是先复制一个空的HashSet,然后通过map.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);//因为HashSet和HashMap都实现了clone接口,这个错误理论上不会出现
        }
    }

spliterator基于HashMap.KeySpliterator生成一个初始大小为空的分裂器

    public Spliterator<E> spliterator() {
        return new HashMap.KeySpliterator<E,Object>(map, 0, -1, 0, 0);
    }

序列化函数

writeObject基本上就是HashMap的基础上去掉了value值的写入。readObject先读取基本参数,并调整大小保证集合至少有0.25的负载率,最后新建底层的Map并读取元素插入集合。

    private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException {
        // 写入隐藏的序列化对象
        s.defaultWriteObject();

        // 写入HashMap的大小和负载因子
        s.writeInt(map.capacity());
        s.writeFloat(map.loadFactor());

        // 写入元素个数
        s.writeInt(map.size());

        // 依次写入所有元素
        for (E e : map.keySet())
            s.writeObject(e);
    }

    private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        // 读取隐藏的序列化对象
        s.defaultReadObject();

        // 读取大小并检验不是负值
        int capacity = s.readInt();
        if (capacity < 0) {
            throw new InvalidObjectException("Illegal capacity: " +
                                             capacity);
        }

        // 读取负载因子,并检验是正数且不是NaN
        float loadFactor = s.readFloat();
        if (loadFactor <= 0 || Float.isNaN(loadFactor)) {
            throw new InvalidObjectException("Illegal load factor: " +
                                             loadFactor);
        }

        // 读取元素个数并检验是非负数
        int size = s.readInt();
        if (size < 0) {
            throw new InvalidObjectException("Illegal size: " +
                                             size);
        }

        // 重设大小,HashMap的大小需要至少有25%的负载率
        capacity = (int) Math.min(size * Math.min(1 / loadFactor, 4.0f),
                HashMap.MAXIMUM_CAPACITY);

        // 创建底层HashMap,若本身是LinkedHashSet则创建LinkedHashSet
        map = (((HashSet<?>)this) instanceof LinkedHashSet ?
               new LinkedHashMap<E,Object>(capacity, loadFactor) :
               new HashMap<E,Object>(capacity, loadFactor));

        // 从流中顺序读取所有元素,并以map.put(e, PRESENT)的方式加入到map中
        for (int i=0; i<size; i++) {
            @SuppressWarnings("unchecked")
                E e = (E) s.readObject();
            map.put(e, PRESENT);
        }
    }

LinkedHashSet

LinkedHashSet是基于LinkedHashMap实现的,所以也支持插入null并且可以保持元素的顺序一定和插入顺序是一致的,同时插入同一个元素而失败时不会影响排序。整个集合完全是基于其他类实现的,所以代码非常少。先看一下关键的构造函数部分,基本上如前面HashSet中提到,这个true的参数除了鉴别重载类型外没有实际意义,而LinkedHashMap在新建时没有给出accessOrder参数所以默认是插入顺序。复制构造这里有些不同,初始大小是c的元素个数2倍和11中的较大值,而不是一般的16

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

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

分裂器是重写过的,Spliterator.DISTINCT | Spliterator.ORDERED代表这个分裂器的集合是不重复的且有序的

    public Spliterator<E> spliterator() {
        return Spliterators.spliterator(this, Spliterator.DISTINCT | Spliterator.ORDERED);
    }

TreeSet

TreeSet是一个排序Set,并且他在没有重写过支持null的comparator的情况下是不支持插入null的

    public static void main(String args[]){
        Set<String> set = new TreeSet<>();
        System.out.println(set.add("123"));//true
        System.out.println(set.add("123"));//false
        //System.out.println(set.add(null));报错
        //System.out.println(set.remove(null));报错
        System.out.println(set.remove("123"));//true
        System.out.println(set.remove("123"));//false
    }

定义与构造函数

首先我们可以看到TreeSet实现的接口就和HashSet不同,是NavigableSet说明这是一个有序排列的Set,底层基于TreeMap实现的NavigableMap接口,同时也是使用一个内存中共享的PRESENT作为虚假的value值。

public class TreeSet<E> extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable
    
    private transient NavigableMap<E,Object> m;

    private static final Object PRESENT = new Object();

之前在TreeMap解析中提到过比较器的问题,如果不在构造时给出新的构造器,则默认根据key的大小来排序,此时若key是不能比较类或抛出错误。构造函数可以看出除非在构造时直接给出comparator或者根据SortedSet进行复制构造,否则都是按key自身来进行排序

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

集合操作函数

TreeSet除了可以返回升序的迭代器外,还可以返回降序的迭代器和降序的Set,在TreeMap中分析过,这里的遍历是对红黑树的中序遍历,而降序迭代器只是改变了指针移动的顺序,对于descendingSet来说因为TreeMap.descendingMap()是返回的自身而新建的TreeSet中只是将这个返回结果设为m,所以对descendingSet的操作会直接反映到原本的TreeSet上面

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

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

    public NavigableSet<E> descendingSet() {
        return new TreeSet<>(m.descendingMap());
    }

add和remove操作和HashSet的设计一样以PRESENT作为虚假的value值进行操作,由于TreeMap在使用key默认排序时不支持以null作为key,所以对于没有设置comparator时插入null会抛出java.lang.NullPointerException错误

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

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

然后是addAll方法,在自身的底层集合为空,c不为空,c是SortedMap,自身的底层集合是TreeMap时可以通过addAllForTreeSet调用buildFromSorted来完成线性时间的构建,否则只能一个个插入树中,一次插入时间复杂度为O(lgn),n是size大小

    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) {//自身的底层集合为空,c不为空,c是SortedMap,自身的底层集合是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))) {//双方的comparator相等
                map.addAllForTreeSet(set, PRESENT);
                return true;
            }
        }
        return super.addAll(c);
    }
    //仅供TreeSet使用
    void addAllForTreeSet(SortedSet<? extends K> set, V defaultVal) {
        try {
            buildFromSorted(set.size(), set.iterator(), null, defaultVal);
        } catch (java.io.IOException cannotHappen) {
        } catch (ClassNotFoundException cannotHappen) {
        }
    }

下边几个子集函数,参数中int的XXElement都是下标类参数,Inclusive代表这个下标元素本身是否包含在截取范围内,因为TreeMap中所有子集操作都是基于自身而没有复制元素,所以对于以下这些子集的修改都会反映到TreeSet上面

    //截取fromElement到toElement间,Inclusive为true时为下标自身包含在范围内
    public NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
                                  E toElement,   boolean toInclusive) {
        return new TreeSet<>(m.subMap(fromElement, fromInclusive,
                                       toElement,   toInclusive));//fromElement、toElement是截取的下标范围,Inclusive为true时本身也包括在内
    }
    //截取小于(inclusive为true时为小于等于)toElement的子集
    public NavigableSet<E> headSet(E toElement, boolean inclusive) {
        return new TreeSet<>(m.headMap(toElement, inclusive));
    }
    //截取大于(inclusive为true时为小于等于)fromElement的子集
    public NavigableSet<E> tailSet(E fromElement, boolean inclusive) {
        return new TreeSet<>(m.tailMap(fromElement, inclusive));
    }
    //截取包含从fromElement开始到不含toElement结束的子集
    public SortedSet<E> subSet(E fromElement, E toElement) {
        return subSet(fromElement, true, toElement, false);
    }
    //截取小于toElement的子集
    public SortedSet<E> headSet(E toElement) {
        return headSet(toElement, false);
    }
    //截取大于等于fromElement的子集
    public SortedSet<E> tailSet(E fromElement) {
        return tailSet(fromElement, true);
    }

下面几个都是查询方法,直接通过TreeMap对应的函数来寻找指定的值

    public E first() {
        return m.firstKey();//返回最小的元素
    }

    public E last() {
        return m.lastKey();//返回最大的元素
    }

    public E lower(E e) {
        return m.lowerKey(e);//返回大于e的元素中最小的
    }

    public E floor(E e) {
        return m.floorKey(e);//返回小于e的元素中最大的
    }

    public E ceiling(E e) {
        return m.ceilingKey(e);//返回大于等于e的元素中最小的
    }

    public E higher(E e) {
        return m.higherKey(e);//返回小于等于e的元素中最大的
    }

poll在查询的基础上如果查找成功会删除对应的元素,只能从最小和最大的开始删除

    public E pollFirst() {
        Map.Entry<E,?> e = m.pollFirstEntry();//删除最小的结点
        return (e == null) ? null : e.getKey();
    }

    public E pollLast() {
        Map.Entry<E,?> e = m.pollLastEntry();//删除最大的结点
        return (e == null) ? null : e.getKey();
    }

TreeMap的clone方法复制了底层的集合但没有复制元素本身,也就是说对树的操作相互之间不影响,但是对相同元素的操作是相互影响的。比如说Set中的元素是一个bean,将原TreeSet中第一个元素的某个属性修改了,clone出的TreeSet中的第一个元素也会改变,这点前面两个Set类也是同样的。

    public Object clone() {
        TreeSet<E> clone;
        try {
            clone = (TreeSet<E>) super.clone();
        } catch (CloneNotSupportedException e) {
            throw new InternalError(e);
        }

        clone.m = new TreeMap<>(m);//复制出一个新的TreeMap
        return clone;
    }

序列化

writeObject比较容易看懂,就是依次写入比较器、元素个数和每个元素,元素的顺序是树的中序遍历顺序

    private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException {
        // 写入任何隐藏的部分
        s.defaultWriteObject();

        // 写入比较器
        s.writeObject(m.comparator());

        // 写入元素个数
        s.writeInt(m.size());

        // 根据迭代器的顺序也就是key从小到大写入所有元素
        for (E e : m.keySet())
            s.writeObject(e);
    }

readObject先读取比较器和大小,然后通过TreeMap.readTreeSet从流中读取构建一个TreeMap

    private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        // 读入隐藏部分
        s.defaultReadObject();

        // 读入比较器
        @SuppressWarnings("unchecked")
            Comparator<? super E> c = (Comparator<? super E>) s.readObject();

        // 创建一个TreeMap设为m
        TreeMap<E,Object> tm = new TreeMap<>(c);
        m = tm;

        // 读入元素个数
        int size = s.readInt();

        tm.readTreeSet(size, s, PRESENT);
    }
    //只有TreeSet.readObject调用
    void readTreeSet(int size, java.io.ObjectInputStream s, V defaultVal)
        throws java.io.IOException, ClassNotFoundException {
        buildFromSorted(size, null, s, defaultVal);//从流中读取构建一个TreeMap
    }

网友评论

登录后评论
0/500
评论
灰色的风
+ 关注