java集合源码分析（八）：Set与AbstractSet

发表于 | 分类于
字数统计: 1.5k

概述

Set 接口是 Collection 接口下三大子接口之一。其下实现类都为元素不可重复的，不保证线程安全的集合。他有两个主要实现，即无序的 HashSet 与有序的 TreeSet。

Set 相对 List 集合与 Queue 集合不同之处在于，他的实现类需要依赖与 Map 集合的实现类密切相关。这体现在以下两点：

  • HashSet 实际依赖于 HashMap，他使用 HashMap 的 key 作为存储容器。TreeSet 同理，依赖于 TreeMap实现。
  • Map 集合中的 keySet 与 EntrySet 视图集合往往以实现了 Set 接口的内部类出现在 Map 的实现类中。
image-20201222152520801

这是关于 java 集合类源码的第八篇文章。往期文章：

  1. java集合源码分析（一）：Collection 与 AbstractCollection
  2. java集合源码分析（二）：List与AbstractList
  3. java集合源码分析（三）：ArrayList
  4. java集合源码分析（四）：LinkedList
  5. java集合源码分析（五）：Map与AbstractMap
  6. java集合源码分析（六）：HashMap
  7. java集合源码分析（七）：LinkedHashMap

一、Set 接口的类关系

1.父接口

Set 接口继承了 Collection 接口，而 Collection 接口又继承了 Iterable 接口，这表明 Set 集合具有 Collection 的通性，是一维的元素集合，并且可以使用迭代器或者 forEach() 迭代。

Set 接口存在一个抽象实现类 AbstractSet，该类继承了 AbstractCollection 抽象类，为 Set 接口提供了大部分抽象方法的实现。

2.子接口

Set 接口还存在子接口，即 SortedSet 与 NavigableSet 接口。这两者都表明实现类是可以根据自然顺序或者比较器排序从而维持有序的集合，并且提供了相关的边界操作方法。

SortedSet

先说 SortedSet，SortedSet是一个可排序的 Set 集合类接口，里面提供了一系列的边界操作——比如查找所有小于或者大于某个值的元素——的抽象方法。实现该接口的实现类中存放的元素必须可以通过比较器或者 equlas()方法对元素进行排序。

1
2
3
4
5
6
7
8
9
10
// 1.返回一个比较器。若要使用自然排序则实现需要返回null
Comparator<? super E> comparator();
// 2.返回一个视图集合。同List实现类的SubList
SortedSet<E> subSet(E fromElement, E toElement);
// 3.获取大于或小于某个值的所有元素
SortedSet<E> headSet(E toElement);
SortedSet<E> tailSet(E fromElement);
// 4.获取最大或最小元素
E first();
E last();

NavigableSet

而 NavigableMap 接口是 SortedMap 的子接口，他在 SortedMap 的基础上进一步提供了更细化的边界操作的抽象方法，比如 SortedMap 提供了 headMap()用于获取所有大于指定值的元素，NavigableMap 就另外再提供 higherXXX()方法用于获取所有大于指定值的元素中的最小元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
// 1.返回小于指定值的最大元素
E lower(E e);
// 2.返回小于等于指定的最大元素
E floor(E e);
// 3.返回大于指定的最小元素
E higher(E e);
// 4.返回大于等于指定值的最小元素
E ceiling(E e);
// 5.获取并删除最大或最小元素
E pollFirst();
E pollLast();
// 6.获取升序迭代器
Iterator<E> iterator();
// 7.获取降序迭代器或降序视图
NavigableSet<E> descendingSet();
Iterator<E> descendingIterator();
// 8.获取指定范围内的视图
SortedSet<E> subSet(E fromElement, E toElement);
SortedSet<E> headSet(E toElement);
SortedSet<E> tailSet(E fromElement);
// 9.获取指定范围内的视图，并且可以选择开闭区间
NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
                           E toElement,   boolean toInclusive);
NavigableSet<E> subSet(E fromElement, boolean fromInclusive,
                           E toElement,   boolean toInclusive);
NavigableSet<E> headSet(E toElement, boolean inclusive);
NavigableSet<E> tailSet(E fromElement, boolean inclusive);

值得一提的是，TreeSet 实现了 SortedSet 与 NavigableSet 接口，同时，它依赖的 TreeMap 也实现了相应的 SortedMap 和 NavigableMap 接口。

二、Set 接口的方法

image-20201222155937401

set 接口不包含任何默认实现，也没有重写 Collection 中的任何方法，因而它提供的抽象方法与 Collection 相同。具体可以参考前文java集合源码分析（一）：Collection 与 AbstractCollection中的第二部分。

三、AbstractSet

AbstractSet 是实现了 Set 接口，并且继承了 AbstractCollection 的抽象类。他为 Set 接口提供了其父类接口 Collection 中的实现类，并且提供了 equlas()，removeAll()，hashCode()三个方法的重写/实现。

1.equlas/hashCode

equals

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public boolean equals(Object o) {
    // 是否同一对象
    if (o == this)
        return true;

    // 是否为Set集合
    if (!(o instanceof Set))
        return false;
    Collection<?> c = (Collection<?>) o;
    // 长度是否相等
    if (c.size() != size())
        return false;
    try {
        // 调用containsAll(c)比较集合
        return containsAll(c);
    } catch (ClassCastException unused)   {
        return false;
    } catch (NullPointerException unused) {
        return false;
    }
}

hashCode

1
2
3
4
5
6
7
8
9
10
11
public int hashCode() {
    int h = 0;
    Iterator<E> i = iterator();
    // 集合hashcode为元素hashcode之和
    while (i.hasNext()) {
        E obj = i.next();
        if (obj != null)
            h += obj.hashCode();
    }
    return h;
}

2.removeAll

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public boolean removeAll(Collection<?> c) {
    Objects.requireNonNull(c);
    boolean modified = false;
	// 迭代较小的结合
    if (size() > c.size()) {
        for (Iterator<?> i = c.iterator(); i.hasNext(); )
            modified |= remove(i.next());
    } else {
        for (Iterator<?> i = iterator(); i.hasNext(); ) {
            if (c.contains(i.next())) {
                i.remove();
                modified = true;
            }
        }
    }
    return modified;
}

四、总结

Set 接口

Set 接口是 Collection 下一个不可重复，线程不安全的集合，主要有 HashSet 与 TreeSet 两大实现类，分别依赖于 Map 接口下 HashMap 与 TreeMap 实现。

Set 继承了 Collection 接口，因而 Set 集合可以通过 forEach()或者迭代器迭代。

Set 接口存在子接口 SortedSet 与孙子接口 NavigableSet，规定了实现该接口的类可以根据自然顺序或者比较器排序保证顺序。

AbstractSet 抽象类

AbstractSet 抽象类继承了 Collection 抽象类，实现了 Set 接口。由于 Set 接口没有除 Collction 接口提供的方法以外的新抽象方法，故 Set 接口的大部分实现有其父类 AbstractCollection 提供，AbstractSet 只实现了 removeAll()，equlas()与 hashCode()方法。

0%