Java集合(四) Set

Set

第一节 Set

Set就是没有重复元素的集合。

Java中的Set接口等同于有更严格限制的Collection，两个接口具有相同的方法签名，比如add()方法要求不能增加已有的元素，其equals方法只要判断两集包含同样的元素就可，对顺序则没有要求。hashcode方法要求保证包含相同元素的两集会得到相同的散列码。

public interface Set<E> extends Collection<E> {
    // Query Operations
    int size();
    boolean isEmpty();
    boolean contains(Object o);
    Iterator<E> iterator();
    Object[] toArray();
    <T> T[] toArray(T[] a);

    // Modification Operations
    boolean add(E e);
    boolean remove(Object o);


    // Bulk Operations
    boolean containsAll(Collection<?> c);
    boolean addAll(Collection<? extends E> c);
    boolean retainAll(Collection<?> c);
    boolean removeAll(Collection<?> c);
    void clear();


    // Comparison and hashing
    boolean equals(Object o);
    int hashCode();

    @Override
    default Spliterator<E> spliterator() {
        return Spliterators.spliterator(this, Spliterator.DISTINCT);
    }

    static <E> Set<E> of() {
        return ImmutableCollections.Set0.instance();
    }

    @SafeVarargs
    @SuppressWarnings("varargs")
    static <E> Set<E> of(E... elements) {
        switch (elements.length) { // implicit null check of elements
            case 0:
                return ImmutableCollections.Set0.instance();
            case 1:
                return new ImmutableCollections.Set1<>(elements[0]);
            case 2:
                return new ImmutableCollections.Set2<>(elements[0], elements[1]);
            default:
                return new ImmutableCollections.SetN<>(elements);
        }
    }

    @SuppressWarnings("unchecked")
    static <E> Set<E> copyOf(Collection<? extends E> coll) {
        if (coll instanceof ImmutableCollections.AbstractImmutableSet) {
            return (Set<E>)coll;
        } else {
            return (Set<E>)Set.of(new HashSet<>(coll).toArray());
        }
    }
}

---

第二节 HashSet

2.1 散列集

散列表是一种能够快速查找得数据结构，对表内得所有元素都会计算出一个整数即散列码(hash code)，可以参阅博客equals和hashCode异同。

Java用链表数组来实现散列表，每个链表叫做桶(bucket)，比如散列表共有128个桶，准备存储的某个对象计算出散列码为76268，求余得108，所以其应该存放在第108号桶。当桶被占满也就是哈希冲突时，就比较一下这个对象是否已经存在。

散列表可以用来实现几个很重要的数据结构，其中一个就是Set。散列集相关内容可以参阅字符串哈希算法

2.2 HashSet

HashSet即散列集，实现了Set接口，散列集的迭代器可以一次访问所有的桶，因为散列是把元素分散在表的各个位置，所以其访问顺序是随机的，所以在不在意集合中元素的顺序时才应该使用HashSet。

因为散列值的原因，在修改集合中元素时要注意是否导致hashcode改变，会导致其在集合的位置也发生变化。

HashSet部分源码：

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

    private transient HashMap<E,Object> map;
    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();

    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) {//构造一个空的指定容量的散列集
        map = new HashMap<>(initialCapacity);
    }

    public HashSet(int initialCapacity, float loadFactor) {//构造一个具有指定容量和装填因子(0.0~1.0)的空散列集
        map = new HashMap<>(initialCapacity, loadFactor);
    }

    HashSet(int initialCapacity, float loadFactor, boolean dummy) {//由LinkedHashSet使用，dummy只是用来区别其它构造函数
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }
    ...
}

底层是基于一个 HashMap 来实现的，相关操作也是直接调用 HashMap API来完成。其设计就是利用 HashMap 的键来存放元素，用统一的 PRESENT 来作为 HashMap 的值，利用 HashMap 的键的唯一性来实现集合的元素不重复。

---

第三节 TreeSet

树集和散列集很相似，区别就是树集是一个有序集合。

TreeSet实现了SortedSet接口，TreeSet的排序是通过红黑树来实现的，红黑树可以参考博客算法复习 (二) 查找-平衡查找树，每一次添加元素都会将其放入正确的排序位置，迭代器总是以顺序来访问集合，相应的其就要为此消耗一些性能在新增上，相比HashSet，TreeSet的add要慢一些。

所以选用TreeSet还是HashSet取决于是否要为排序来付出这个开销，还有一些情况下数据的比较会比较困难(因为树的排序要求不相等的元素必须是可比的)，相较下散列却比较容易实现，这个时候也可以用HashSet来实现集。

public class TreeSet<E> extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable{
    
    TreeSet(NavigableMap<E,Object> m) {
        this.m = m;
    }

    public TreeSet() {//构造一个空树集
        this(new TreeMap<>());
    }

    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的排序和NavigableSet添加一个定制的比较器来排序。

    public static void main(String[] args) {
        SortedSet<Person> people = new TreeSet<>();//根据年龄和姓名排序
        people.add(new Person("Mary",17));
        people.add(new Person("Lee",20));
        people.add(new Person("Ada",17));
        System.out.println("people:" + people);

        NavigableSet<Person> sortByName = new TreeSet<>(Comparator.comparing(Person::getName));//根据姓名来排序，这里使用NavigableSet和SortedSet结果一样
        sortByName.addAll(people);
        System.out.println("sortByName:" + sortByName);
    }

public class Person implements Comparable<Person>{
    private String name;
    private int age;

    @Override
    public int compareTo(Person o) {
        int diff = Integer.compare(this.age,o.getAge());
        return diff != 0 ? diff : this.name.compareTo(o.getName());
    }

    @Override
    public String toString() {
        return "name: " + name;
    }
}

执行结果如下：

people:[name: Ada, name: Mary, name: Lee]
sortByName:[name: Ada, name: Lee, name: Mary]

TreeSet根据Person的compareTo()来排序，但TreeSet构造时通过参数赋予了新的比较方式后就按照新的来排序。

---

第四节 SortedSet

有序集，相比Set声明了用来排序的比较器，因为有序，所以增加了头尾相关的方法。

public interface SortedSet<E> extends Set<E> {
    Comparator<? super E> comparator();//返回用于对元素排序的比较器，若元素使用Comparable接口的compareTo方法进行比较会返回null

    SortedSet<E> subSet(E fromElement, E toElement);//返回有序集从元素fromElement到toElement范围的部分

    SortedSet<E> headSet(E toElement);//返回有序集小于元素toElement范围的部分

    SortedSet<E> tailSet(E fromElement);//返回有序集大于元素fromElement范围的部分

    E first();//返回有序集的最小元素

    E last();//返回有序集的最大元素

    @Override
    default Spliterator<E> spliterator() {
        return new Spliterators.IteratorSpliterator<E>(
                this, Spliterator.DISTINCT | Spliterator.SORTED | Spliterator.ORDERED) {
            @Override
            public Comparator<? super E> getComparator() {
                return SortedSet.this.comparator();
            }
        };
    }
}

---

第五节 NavigableSet

继承SortedSet，增加了用来遍历的正反迭代器。

public interface NavigableSet<E> extends SortedSet<E> {
    
    E higher(E e);//返回大于e的最小元素，没有则返回null
    E lower(E e);//返回小于e的最大元素，没有则返回null

    E ceiling(E e);//返回大于等于e的最小元素，没有则返回null
    E floor(E e);//返回小于等于e的最大元素，没有则返回null

    E pollFirst();//删除并返回有序集中的最小元素，集为空返回null
    E pollLast();//删除并返回有序集中的最大元素，集为空返回null

    Iterator<E> iterator();//获取迭代器

    NavigableSet<E> descendingSet();//返回集合中元素的逆序集合

    Iterator<E> descendingIterator();//获取一个逆序的迭代器

    NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
                           E toElement,   boolean toInclusive);//返回有序集从元素fromElement到toElement范围的部分，若fromElement和toElement相等且fromInclusive和toInclusive不为true，则返回空集

    NavigableSet<E> headSet(E toElement, boolean inclusive);//返回有序集小于元素toElement范围的部分，若inclusive为true则包括边界toElement

    NavigableSet<E> tailSet(E fromElement, boolean inclusive);//返回有序集大于元素fromElement范围的部分，若inclusive为true则包括边界fromElement

    SortedSet<E> subSet(E fromElement, E toElement);

    SortedSet<E> headSet(E toElement);

    SortedSet<E> tailSet(E fromElement);
}

---

第六节 LinkedHashSet

链接散列集，记录插入元素项的顺序，所以使无序的散列表变得有序，条目则存入双向链表中。LinkedHashSet加载LinkedHashMap，而普通HashSet加载HashMap。

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

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

---

第七节 EnumSet

枚举集就是一个枚举类型的元素集，EnumSet通过位序列来实现对于枚举类型的存储。

public abstract class EnumSet<E extends Enum<E>> extends AbstractSet<E>
    implements Cloneable, java.io.Serializable{

    final transient Class<E> elementType;//枚举类别
    final transient Enum<?>[] universe;//枚举数组

    EnumSet(Class<E> elementType, Enum<?>[] universe) {
        this.elementType = elementType;
        this.universe    = universe;
    }

    private static <E extends Enum<E>> E[] getUniverse(Class<E> elementType) {
        return SharedSecrets.getJavaLangAccess()
                                        .getEnumConstantsShared(elementType);
    }
    ...
    public static <E extends Enum<E>> EnumSet<E> allOf(Class<E> elementType) {//返回包含给定枚举类型所有值的集
        EnumSet<E> result = noneOf(elementType);
        result.addAll();
        return result;
    }
    public static <E extends Enum<E>> EnumSet<E> noneOf(Class<E> elementType) {//返回一个有足够空间放下给定枚举类型所有值的空集
        Enum<?>[] universe = getUniverse(elementType);
        if (universe == null)
            throw new ClassCastException(elementType + " not an enum");

        if (universe.length <= 64)
            return new RegularEnumSet<>(elementType, universe);
        else
            return new JumboEnumSet<>(elementType, universe);
    }
    public static <E extends Enum<E>> EnumSet<E> range(E from, E to) {//返回包含从from到to之间所有值的集
        if (from.compareTo(to) > 0)
            throw new IllegalArgumentException(from + " > " + to);
        EnumSet<E> result = noneOf(from.getDeclaringClass());
        result.addRange(from, to);
        return result;
    }
    public static <E extends Enum<E>> EnumSet<E> of(E e1, E e2, E e3) {//返回包含给定值的集
        EnumSet<E> result = noneOf(e1.getDeclaringClass());
        result.add(e1);
        result.add(e2);
        result.add(e3);
        return result;
    }
}

测试以上方法。

public static void main(String[] args) {
    System.out.println("always");
    print(always);
    System.out.println("never");
    print(never);
    System.out.println("workday");
    print(workday);
    System.out.println("mwf");
    print(mwf);
}

enum WeekDay {MONDAY,TUESDAY,WEDNESDAY,THURSTAY,FRIDAY,SATURDAY,SUNDAY};
//初始化EnumSet元素
static EnumSet<WeekDay> always = EnumSet.allOf(WeekDay.class);
static EnumSet<WeekDay> never = EnumSet.noneOf(WeekDay.class);
static EnumSet<WeekDay> workday = EnumSet.range(WeekDay.MONDAY,WeekDay.FRIDAY);
static EnumSet<WeekDay> mwf = EnumSet.of(WeekDay.MONDAY,WeekDay.WEDNESDAY,WeekDay.FRIDAY);

public static void print(EnumSet set){
    set.forEach(v -> System.out.println("value[" + v + "]"));
}

输出结果如下：

always
value[MONDAY]
value[TUESDAY]
value[WEDNESDAY]
value[THURSTAY]
value[FRIDAY]
value[SATURDAY]
value[SUNDAY]
never
workday
value[MONDAY]
value[TUESDAY]
value[WEDNESDAY]
value[THURSTAY]
value[FRIDAY]
mwf
value[MONDAY]
value[WEDNESDAY]
value[FRIDAY]

---

参考博客和文章书籍等：

《Java核心技术 卷Ⅰ》

因博客主等未标明不可引用，若部分内容涉及侵权请及时告知，我会尽快修改和删除相关内容