Collection集合

1、概述

集合类中也是使用了JDK8中的一些新的特性，在源码中可以体现。

迭代器接口：

public interface Iterable<T> {
    // 返回一个泛型的迭代器
    Iterator<T> iterator();
    
    // jdk8中的默认实现，默认遍历方式
    default void forEach(Consumer<? super T> action) {
        Objects.requireNonNull(action);
        // 可以看到调用的是函数式编程中的accept方法。如何消费自己指定
        for (T t : this) {
            action.accept(t);
        }
    }
    
    // 分离，基本上不怎么常用
    default Spliterator<T> spliterator() {
        return Spliterators.spliteratorUnknownSize(iterator(), 0);
    }
}

再看下Collection接口：

public interface Collection<E> extends Iterable<E> {
    // 集合中的个数
    int size();
    // 集合是否为空
    boolean isEmpty();
    // 集合中是否包含了某个元素
    boolean contains(Object o);
    // 返回迭代器
    Iterator<E> iterator();
    // 将集合中的元素转换成Object类型的数组
    Object[] toArray();
    // 泛型方法。将集合转换成数组
    <T> T[] toArray(T[] a);
    // 向集合中添加元素
    boolean add(E e);
    // 移除某个元素
    boolean remove(Object o);
    // 如果存在，进行移除。可以看到操作的是从迭代器中来操作的
    default boolean removeIf(Predicate<? super E> filter) {
        Objects.requireNonNull(filter);
        boolean removed = false;
        final Iterator<E> each = iterator();
        while (each.hasNext()) {
            if (filter.test(each.next())) {
                each.remove();
                removed = true;
            }
        }
        return removed;
    }
    // 将集合进行清空操作
    void clear();
    // equals和hashCode方法
    boolean equals(Object o);
    int hashCode();
    // 转换成流方法的使用
    default Stream<E> stream() {
        return StreamSupport.stream(spliterator(), false);
    }
    
    default Stream<E> parallelStream() {
        return StreamSupport.stream(spliterator(), true);
    }
}    

可以看到的主要是针对集合的操作。那么怎么操作决定了子类实现类中对数据结构的实现来决定的。

对于常见的集合实现来说，常用的有List和Set集合

那么先看下List常见的实现类：

可以看到List接口中的方法和Collection中是类似的

2、ArrayList源码分析

先看下ArrayList的源码：

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable{
    
    private static final long serialVersionUID = 8683452581122892189L;

    /**
     * Default initial capacity.List集合的初始化值大小是10
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * Shared empty array instance used for empty instances
     * 共享空数组实例数组
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /**
     * Shared empty array instance used for default sized empty instances. We
     * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
     * first element is added.
     * 共享空数组对于默认的list集合。当第一次添加元素的时候，会用EMPTY_ELEMENTDATA
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     * The array buffer into which the elements of the ArrayList are stored.
     * The capacity of the ArrayList is the length of this array buffer. Any
     * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
     * will be expanded to DEFAULT_CAPACITY when the first element is added.
     * 数组缓冲区用来存储数组中的元素的，ArrayList的容量就是这个缓冲区的容量。
     */
    transient Object[] elementData; // non-private to simplify nested class access

    /**
     * The size of the ArrayList (the number of elements it contains).
     * 数组中元素的个数
     * @serial
     */
    private int size;

    /**
     * Constructs an empty list with the specified initial capacity.
     * 构造出来一个指定容量的空list，可以指定容量。如果不指定，默认是10
     * @param  initialCapacity  the initial capacity of the list
     * @throws IllegalArgumentException if the specified initial capacity
     *         is negative
     */
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

    /**
     * Constructs an empty list with an initial capacity of ten.
     * 上面如果没有指定，那么就使用这个来进行指定
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
}

上面主要是介绍了ArrayList的介绍，在共享数组中是没有元素的空数组；如果指定了容量，那么将会直接创建出来指定容量的数组，如果没有指定，那么将会在创建的时候先使用一个空的数组；如果没有指定容量，那么将会在第一次添加的时候再次进行初始化，而我们通常使用的就是第一种。

那么来看一下add方法的操作：

    /**
     * Appends the specified element to the end of this list.
     * 在list集合的尾部来进行追加元素
     * @param e element to be appended to this list
     * @return <tt>true</tt> (as specified by {@link Collection#add})
     */
    public boolean add(E e) {
        // 确定内部容量是否足够。这里的size是初始值，默认是0
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        // 这里分为两步操作。elementData[size] = e; size++;
        elementData[size++] = e;
        return true;
    }

那么接下来看一下，如何确保容量实现的：

    private void ensureCapacityInternal(int minCapacity) {
        // 确保显示容量
        // ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
        // 将上面的进行拆分，划分如下。计算容量
        int result = calculateCapacity(elementData, minCapacity);
        // 确定容量
        ensureExplicitCapacity(result);
    }

从计算容量开始，开始开辟存储数据的空间：

    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        // 可以从空参构造那里看到，初始化的时候是这个空数组
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            // 取出来最大值，因为size初始值是0，这里的minCapacity是1，那么取出来最大值就是1。最终的最大值就是10
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        // 如果已经指定了容量，那么就直接走这一步
        return minCapacity;
    }

可以确定，这里是将数组中的长度进行确定好了。那么再次进入到下一步：

    private void ensureExplicitCapacity(int minCapacity) {
        // modCount+1
        modCount++;

        // 考虑溢出的代码
        // 将上面传入进来的容量作为参数来进行校验，确定最小容量是否大于数组长度。如果大于，那么将进行扩容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

private void grow(int minCapacity) {
    // 扩充到原来的1.5倍是从这里来的
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 如果新的数组容量仍然小于旧的，俺么就使用旧的容量。
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 确定是否使用最大的容量
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    // 最终将数组扩容的时候会走到这一步。
    elementData = Arrays.copyOf(elementData, newCapacity);
}

这里就是指定了原来的数组和新的容量大小：

    @SuppressWarnings("unchecked")
    public static <T> T[] copyOf(T[] original, int newLength) {
        // 这一步将Object类型的数组转换成T[]的
        return (T[]) copyOf(original, newLength, original.getClass());
    }

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
    @SuppressWarnings("unchecked")
    T[] copy = ((Object)newType == (Object)Object[].class)
        ? (T[]) new Object[newLength]
        : (T[]) Array.newInstance(newType.getComponentType(), newLength);
    // 最终会调用这个数组来进行操作
    System.arraycopy(original, 0, copy, 0,
                     Math.min(original.length, newLength));
    return copy;
}

也就是说这种操作会将数组中的元素一直在后面追加，从0下标开始进行拷贝，直到指定的大小。

所以在添加元素中，首先判断的是数组是否是空的，如果是空的，首先进行初始化，指定容量；如果不是空的，那么考虑是否应该进行扩容；最终将元素放入进去。

那么追踪下：什么时候开始进行扩容？

    public boolean add(E e) {
        // 确定内部容量是否足够。这里的size是初始值，默认是0
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        // 这里分为两步操作。elementData[size] = e; size++;
        elementData[size++] = e;
        return true;
    }

    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        // 可以从空参构造那里看到，初始化的时候是这个空数组
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            // 取出来最大值，因为size初始值是0，这里的minCapacity是1，那么取出来最大值就是1。最终的最大值就是10
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        // 如果已经指定了容量，那么就直接走这一步
        return minCapacity;
    }

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        // 将上面传入进来的容量作为参数来进行校验，确定最小容量是否大于数组长度。如果大于，那么将进行扩容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

第一次添加的时候，size为0，size+1为1，添加第一个元素，这个时候走到了ensureExplicitCapacity方法中的判断中的时候，不会来进行扩容。

但是当第9次添加的时候，size+1为10，但是依然不会大于elementData.length，因为默认初始化就是10；

那么当是第10次添加的时候，size+1位11，这个时候，大于了，就会走扩容阶段的方法。默认是10，也就是说扩容的时间发生在数组中元素满了的时候，先进行尝试添加，然后添加进去的时候判断空间是否足够，不足够再进行扩容。

3、重要方法

其实有很多，但是唯一一个值得一提的是clear方法

    public void clear() {
        modCount++;

        // clear to let GC do its work
        for (int i = 0; i < size; i++)
            elementData[i] = null;

        size = 0;
    }

可以看到这里的clear是依次循环将立面的元素置为null。所以我们在使用的时候，通常也不会来进行使用。