java集合源码分析（一）：Collection 与 AbstractCollection

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

概述

我们知道，java 中容器分为 Map 集合和 Collection 集合，其中 Collection 中的又分为 Queue，List，Set 三大子接口。

其下实现类与相关的实现类子类数量繁多。我们仅以最常使用的 List 接口的关系为例，简单的画图了解一下 Collection 接口 List 部分的关系图。

List集合的实现类关系图

根据上图的类关系图，我们研究一下源码中，类与类之间的关系，方法是如何从抽象到具体的。

一、Iterable 接口

Iterable 是最顶层的接口，继承这个接口的类可以被迭代。

Iterable 接口的方法

  • iterator()：用于获取一个迭代器。

  • forEach() ：JDK8 新增。一个基于函数式接口实现的新迭代方法。

    1
    2
    3
    4
    5
    6
    default void forEach(Consumer<? super T> action) {
        Objects.requireNonNull(action);
        for (T t : this) {
            action.accept(t);
        }
    }

  • spliterator()：JDK8 新增。用于获取一个可分割迭代器。默认实现返回一个IteratorSpliterator类。

这个跟迭代器类似，但是是用于并行迭代的，关于具体的情况可以参考一下掘金的一个讨论：Java8里面的java.util.Spliterator接口有什么用？

二、Collection 接口

Collection 接口的方法

Collection 是集合容器的顶级接口，他继承了 Iterable 接口，即凡是 Collection 的实现类都可以迭代，List 也是 Collection 的子接口，因此也拥有此特性。

可以看到， Collection 接口提供了十九个抽象方法，这些方法的命名都很直观的反应的这些方法的功能。通过这些方法规定了 Collection的实现类的一些基本特性：可迭代，可转化为数组，可对节点进行添加删除，集合间可以合并或者互相过滤，可以使用 Stream 进行流式处理。

1.抽象方法

我们可以根据功能简单的分类介绍一下 Collection 接口提供的方法。

判断类：

  • isEmpty()：判断集合是否不含有任何元素；
  • contains()：判断集合中是否含有至少一个对应元素；
  • containsAll()：判断集合中是否含另一个集合的所有元素；

操作类：

  • add()：让集合包含此元素。如果因为除了已经包含了此元素以外的任何情况而不能添加，则必须抛出异常；
  • addAll()：将指定集合中的所有元素添加到本集合；
  • remove()：从集合移除指定元素；
  • removeAll()：删除也包含在指定集合中的所有此集合的元素；
  • retainAll：从此集合中删除所有未包含在指定集合中的元素；
  • clear()：从集合中删除所有元素；

辅助类：

  • size()：获取集合的长度。如果长度超过 Integer.MAX_VALU 就返回 Integer.MAX_VALU；

  • iterator()：获取集合的迭代器；

  • toArray()：返回一个包含此集合中所有元素的新数组实例。因为是新实例，所以对原数组的操作不会影响新数组，反之亦然；

    它有一多态方法参数为T[]，此时调用 toArray()会将内部数组中的元素全部放入指定数组，如果结束后指定数组还有剩余空间，那剩余空间都放入null。

2.JDK8 新增抽象方法

此外，在 JDK8 中新增了四个抽象方法，他们都提供了默认实现：

  • removeIf：相当于一个filter()，根据传入的函数接口的匿名实现类方法来判断是否要删除集合中的某些元素；
  • stream()：JDK8 新特性中流式编程的灵魂方法，可以将集合转为 Stream 流式进行遍历，配合 Lambda 实现函数式编程；
  • parallelStream()：同 stream() ，但是是生成并行流；
  • spliterator()：重写了 Iterable 接口的 iterator()方法。

3.equals 和 hashCode

值得一提的是 Collection 还重写了 Object 的 equals() 和 hashCode() 方法（或者说变成了抽象方法？），这样实现 Collection 的类就必须重新实现 equals() 和 hashCode() 方法。

三、AbstractCollection 抽象类

AbstractCollection 是一个抽象类，他实现了 Collection 接口的一些基本方法。我们可以根据 JavaDoc 简单的了解一下它：

要实现不可修改的集合，程序员只需扩展此类并为iterator和size方法提供实现。（由iterator方法返回的迭代器必须实现hasNext和next 。）

要实现可修改的集合，程序员必须另外重写此类的add方法（否则将抛出UnsupportedOperationException ），并且iterator方法返回的迭代器必须另外实现其remove方法。

根据Collection接口规范中的建议，程序员通常应提供一个void（无参数）和Collection构造函数

通过类的关系图，AbstractCollection 下面还有一个子抽象类 AbstractList ，进一步提供了对 List 接口的实现。 我们不难发现，这正是模板方法模式在 JDK 中的一种运用。

0.不支持的实现

在这之前，需要注意的是，AbstractCollection 中有一些比较特别的写法，即实现了方法，但是默认一调用立刻就抛出 UnsupportedOperationException异常：

1
2
3
public boolean add(E e) {
    throw new UnsupportedOperationException();
}

如果想要使用这个方法，就必须自己去重写他。这个写法让我纠结了很久，网上找了找也没找到一个具体的说法。

参考 JDK8 新增的接口方法默认实现这个特性，我大胆猜测，这应该是针对一些实现 Collection 接口，但是又不想要实现 add(E e)方法的类准备的。在 JDK8 之前，接口没有默认实现，如果抽象类还不提供一个实现，那么无论实现类是否需要这个方法，那么他都一定要实现这个方法，这明显不太符合我们设计的初衷。

1.isEmpty

非常简短的方法，通过判断容器 size 是否为0判断集合是否为空。

1
2
3
public boolean isEmpty() {
    return size() == 0;
}

2.contains/containsAll

判断元素是否存在。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public boolean contains(Object o) {
    Iterator<E> it = iterator();
    // 如果要查找的元素是null
    if (o==null) {
        while (it.hasNext())
            if (it.next()==null)
                return true;
    } else {
        while (it.hasNext())
            if (o.equals(it.next()))
                return true;
    }
    return false;
}

containsAll()就是在contains()基础上进行了遍历判断。

1
2
3
4
5
6
public boolean containsAll(Collection<?> c) {
    for (Object e : c)
        if (!contains(e))
            return false;
    return true;
}

3.addAll

addAll()方法就是在 for 循环里头调用 add()

1
2
3
4
5
6
7
public boolean addAll(Collection<? extends E> c) {
    boolean modified = false;
    for (E e : c)
        if (add(e))
            modified = true;
    return modified;
}

4.remove/removeAll

remove()这个方法与 contains()逻辑基本一样，因为做了null判断，所以List是默认支持传入null的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public boolean remove(Object o) {
    Iterator<E> it = iterator();
    if (o==null) {
        while (it.hasNext()) {
            if (it.next()==null) {
                it.remove();
                return true;
            }
        }
    } else {
        while (it.hasNext()) {
            if (o.equals(it.next())) {
                it.remove();
                return true;
            }
        }
    }
    return false;
}

5.removeAll/retainAll

removeAll()和 retainAll()的逻辑基本一致，都是通过 contains()方法判断元素在集合中是否存在，然后选择保存或者删除。由于 contains()方法只看是否存在，而不在意有几个，所以如果目标元素有多个，会都删除或者保留。

1
2
3
4
5
6
7
8
9
10
11
12
public boolean removeAll(Collection<?> c) {
    Objects.requireNonNull(c);
    boolean modified = false;
    Iterator<?> it = iterator();
    while (it.hasNext()) {
        if (c.contains(it.next())) {
            it.remove();
            modified = true;
        }
    }
    return modified;
}
1
2
3
4
5
6
7
8
9
10
11
12
public boolean retainAll(Collection<?> c) {
    Objects.requireNonNull(c);
    boolean modified = false;
    Iterator<E> it = iterator();
    while (it.hasNext()) {
        if (!c.contains(it.next())) {
            it.remove();
            modified = true;
        }
    }
    return modified;
}

5.toArray（扩容）

用于将集合转数组。有两个实现。一般常用的是无参的那个。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public Object[] toArray() {
    // 创建一个和List相同长度的数字
    Object[] r = new Object[size()];
    Iterator<E> it = iterator();
    for (int i = 0; i < r.length; i++) {
        // 如果数组长度大于集合长度
        if (! it.hasNext())
            // 用Arrays.copyOf把剩下的位置用null填充
            return Arrays.copyOf(r, i);
        r[i] = it.next();
    }
    // 如果数组长度反而小于集合长度，就扩容数组并且重复上述过程
    return it.hasNext() ? finishToArray(r, it) : r;
}

其中，在 finishToArray(r, it) 这个方法里涉及到了一个扩容的过程：

1
2
3
4
5
6
7
8
9
10
// 成员变量，允许数组理论允许的大小
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

// 位运算，扩大当前容量的一半+1
int newCap = cap + (cap >> 1) + 1;
// 如果扩容后的大小比MAX_ARRAY_SIZE还大
if (newCap - MAX_ARRAY_SIZE > 0)
    // 使用原容量+1，去判断要直接扩容到MAX_ARRAY_SIZE，Integer.MAX_VALUE还是直接抛OutOfMemoryError异常
    newCap = hugeCapacity(cap + 1);
r = Arrays.copyOf(r, newCap);

这里的 MAX_ARRAY_SIZE 是一个常量：

1
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

这里又通过hugeCapacity()方法进行了大小的限制：

1
2
3
4
5
6
7
8
9
10
11
12
private static int hugeCapacity(int minCapacity) {
    // 如果已经大到溢出就抛异常
    if (minCapacity < 0)
        throw new OutOfMemoryError
        ("Required array size too large");
    // 容量+1是否还是大于允许的数组最大大小
    return (minCapacity > MAX_ARRAY_SIZE) ?
        // 如果是，就把容量直接扩大到Integer.MAX_VALUE
        Integer.MAX_VALUE :
    // 否则就直接扩容到运行的数组最大大小
    MAX_ARRAY_SIZE;
}

可能有人会疑问，MAX_ARRAY_SIZE应该就是允许扩容的最大大小了，为什么还可以扩容到Integer.MAX_VALUE？

实际上，根据 JavaDoc 的解释：

Some VMs reserve some header words in an array. Attempts to allocate larger arrays may result in OutOfMemoryError

一些 JVM 可能会用数组头存放一些关于数组的数据，一般情况下，最好不要直接可以扩容到Integer.MAX_VALUE，因此扩容到Integer.MAX_VALUE-8就是理论上允许的最大值了，但是如果真的大到了这个地步，就只能特殊情况特殊对待，试试看可不可以扩容到Integer.MAX_VALUE，如果再大就要溢出了。

6.clear

迭代并且删除全部元素。

1
2
3
4
5
Iterator<E> it = iterator();
while (it.hasNext()) {
    it.next();
    it.remove();
}

7.toString

AbstractCollection 重写了 toString 方法，这也是为什么调用集合的toStirng() 不是像数组那样打印一个内存地址的原因。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public String toString() {
    Iterator<E> it = iterator();
    if (! it.hasNext())
        return "[]";

    StringBuilder sb = new StringBuilder();
    sb.append('[');
    for (;;) {
        E e = it.next();
        sb.append(e == this ? "(this Collection)" : e);
        if (! it.hasNext())
            return sb.append(']').toString();
        sb.append(',').append(' ');
    }
}

四、总结

Collection

Collection 接口类是 List ，Queue，Set 三大子接口的父接口，他继承了 Iterable 接口，因而所有 Collection 的实现类都可以迭代。

Collection 中提供了规定了实现类应该实现的大部分增删方法，但是并没有规定关于如何使用下标进行操作的方法。

实现类的equlas与hashCode方法

值得注意的是，他重规定了 equlas() 和 hashCode()的方法，因此 Collection 的实现类的这两个方法不再跟 Object 类一样了。

AbstractCollection

AbstractCollection 是实现 Collection 接口的一个抽象类，JDK 在这里使用了模板方法模式，Collection 的实现类可以通过继承 AbstractCollection 获得绝大部分实现好的方法。

在 AbstractCollection 中，为add()抽象方法提供了不支持的实现：即实现了方法，但是调用却会抛出 UnsupportedOperationException。根据推测，这跟 JDK8 接口默认实现的特性一样，是为了让子类可以有选择性的去实现接口的抽象方法，不必即使不需要该方法，也必须提供一个无意义的空实现。

AbstractCollection 提供了对添加复数节点，替换、删除的单数和复数节点的方法实现，在这些实现里，因为做了null判断，因此是默认是支持传入的元素为null，或者集合中含有为null的元素，但是不允许传入的集合为null。

扩容

AbstractCollection 在集合转数组的 toArrays() 中提供了关于扩容的初步实现：一般情况下新容量=旧容量 + (旧容量/2 + 1)，如果新容量大于 MAX_ARRAY_SIZE，就会使用 旧容量+1去做判断，如果已经溢出则抛OOM溢出，大于 MAX_ARRAY_SIZE 就使用 Integer.MAX_VALUE 作为新容量，否则就使用 MAX_ARRY_SIZE。

0%