JDK8源码详解-util篇-AbstractCollection

概述

功能：该类提供了Collection接口的基础框架

开始版本：JDK 1.2

注意：本类为抽象类

实现接口：Collection

所在包：java.util

具体实现子类：ArrayDeque

导入类：无

类声明：

public abstract class AbstractCollection<E> implements Collection<E>

框架图：

常量 私有常量 数组最大长度 MAX_ARRAY_SIZE

注意：
1. 未使用最大Integer值的原因为 —— 有些虚拟机在数组头中会保留一些信息，使用最大Integer值可能导致溢出。
2. 此处提供的预留头位数为4位二进制位(即0000)

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

方法 构造器

// 唯一构造器
protected AbstractCollection() {}

抽象方法 01.迭代器 iterator

public abstract Iterator<E> iterator();

02.集合个数 size

public abstract int size();

私有方法 01.toArray()最终返回数组处理 finishToArray(T[] r, Iterator it)

参数：
1. r —— 存放结果的指定数组
2. it —— 当前集合的迭代器

说明：
1. 本方法为私有静态方法，主要提供给本方法的toArray()和toArray(T[] a)方法使用
2. 在集合转换数组中途集合有新增元素，导致数组中存入的并非当前集合全部元素时会被调用
3. 此问题需要判断数组扩容是否溢出，可能会抛出OutOfMemoryError异常
4. 如果数组长度不够，扩容规则为 —— (原数组长度 * 1.5 + 1)

private static <T> T[] finishToArray(T[] r, Iterator<?> it) {
    // 获取数组长度，便于后续比较是否超过长度，注意此处是动态的会随数组长度变化而变化
    int i = r.length;
    while (it.hasNext()) {
        // 再次获取因为此值在循环中会被改变
        int cap = r.length;
        // 若当前数组下标等于数组长度则扩容
        if (i == cap) {
            // 扩容：(原长度 * 1.5 + 1)
            int newCap = cap + (cap >> 1) + 1;
            // 判断扩容后是否超过数组上限
            if (newCap - MAX_ARRAY_SIZE > 0)
                // 判断原数组长度+1是否超过数组长度上限，若超过则将数组扩容为最大Integer值，否则扩容为数组的最大长度
                newCap = hugeCapacity(cap + 1);
            // 复制数组，防止多余扩容出来的位置为null被浪费    
            r = Arrays.copyOf(r, newCap);
        }
        r[i++] = (T)it.next();
    }
    // 判断数组是否已被元素占满，没有占满则使用Arrays.copyOf将多余的位置去除
    return (i == r.length) ? r : Arrays.copyOf(r, i);
}

@Test
void contextLoads() {
    // 模拟集合 - 5个元素
    List<String> list = new ArrayList<>();
    list.add("1");
    list.add("2");
    list.add("3");
    list.add("4");
    list.add("5");

    // 新数组长度初始长度：5，模拟已赋值前五位的情况
    String[] r = new String[5];

    // 中途新增元素(此时集合中有10个元素了)
    list.add("6");
    list.add("7");
    list.add("8");
    list.add("9");
    list.add("10");

    Iterator<String> it = list.iterator();

    // 模拟已存入前五个集合的元素
    for (int i = 0; i < 5; i++) {
        it.hasNext();
        r[i] = it.next();
    }

    // 模拟最后元素为全部储存在数组中调用方法
    int i = r.length;
    while (it.hasNext()) {
        // 数组长度：此处为5
        int cap = r.length;
        if (i == cap) {
            int newCap = cap + (cap >> 1) + 1;
            // ( 2147483639 即 MAX_ARRAY_SIZE )
            if (newCap - 2147483639 > 0)
                // 原(hugeCapacity(cap + 1))
                newCap = ((cap + 1) > 2147483639) ? Integer.MAX_VALUE : 2147483639;
            r = Arrays.copyOf(r, newCap);
        }
        r[i++] = it.next();
    }
    // 原(return (i == r.length) ? r : Arrays.copyOf(r, i))
    // [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    System.out.println((i == r.length) ? Arrays.toString(r) : Arrays.toString(Arrays.copyOf(r, i)));
}

02.数组临界长度判断 hugeCapacity(int minCapacity)

参数：minCapacity —— 需判断的数组长度

说明：
1. 本方法为私有静态方法，主要提供给本方法的finishToArray(T[] r, Iterator方法使用扩容超过数组最大值时使用
2. 若未超过Integer最大值(溢出)，判断是否超过数组最大值，未超过返回数组最大值，超过则返回Integer最大值

private static int hugeCapacity(int minCapacity) {
    // 小于0表示超过了Integer最大值，抛出溢出异常
    if (minCapacity < 0) 
        throw new OutOfMemoryError("Required array size too large");
    // 判断是否超过数组最大值返回对应的数值
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

公有方法 01.当前集合是否为空 isEmpty()

注意：此方法需保证调用对象不能为Null

// 源码
public boolean isEmpty() {
    // 返回集合元素个数是否为0
    return size() == 0;
}

02.当前集合是否包含某对象 contains(Object o)

参数：o —— 判断的元素

注意：此集合的元素类型需要重写equals方法

// 源码
public boolean contains(Object o) {
    Iterator<E> it = iterator();
    // null值需要单独比较，防止使用equals出现空指针
    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;
}

03.当前集合转数组 toArray()

注意：
1. 若在生成待返回数组和生成迭代器之间集合元素减少，导致数组长度大于集合元素个数，会通过调用Arrays.copyOf将多余的null值数组部分去除，防止返回的数组中包含null值
2. 若在生成待返回数组和生成迭代器之间集合元素增加，导致数组长度小于集合元素个数，在循环结束会调用finishToArray()方法处理，它会生成足够容量的新数组将已遍历的值复制进去，再将剩余元素存入
3. 无需担心出现生成迭代器之后集合变更，因为此情况会直接报错java.util.ConcurrentModificationException，报错原因为迭代器的next()方法中调用了checkForComodification方法，它会判断中途是否有元素的增删且未与迭代器同步，有就会报错，因为此情况会导致迭代器的指针混乱、数据异常、空指针等问题
4. 如需在生成迭代器后进行增删改等 *** 作请尽量使用迭代器中的方法，这些方法会将集合的改变与迭代器同步

// 源码
public Object[] toArray() {
    // 创建一个和集合元素个数一致的数组
    Object[] r = new Object[size()];
    Iterator<E> it = iterator();
    for (int i = 0; i < r.length; i++) {
        // 如果集合中没有元素了但数组还有空余位置，直接返回Arrays.copyOf()后的数组对象
        if (! it.hasNext()) 
            return Arrays.copyOf(r, i);
        r[i] = it.next();
    }
    // 判断是否在生成数组和生成迭代器之间集合有元素增加
    return it.hasNext() ? finishToArray(r, it) : r;
}

// 示例：生成待返回数组和生成迭代器之间集合元素减少
@Test
void contextLoads() {
    // 模拟集合 - 4个元素
    List<String> list = new ArrayList<>();
    list.add("1");
    list.add("2");
    list.add("3");
    list.add("4");
    String[] r = new String[list.size()];
    list.remove(3);
    Iterator<String> it = list.iterator();
    for (int i = 0; i < r.length; i++) {
        if (! it.hasNext()){
            // 原(return Arrays.copyOf(r, i);)
            // 减少元素后的返回：[1, 2, 3]
            System.out.println("减少元素后的返回：" + Arrays.toString(Arrays.copyOf(r, i)));
            break;
        }
        r[i] = it.next();
    }
    // 减少元素后未处理的返回：[1, 2, 3, null]
    System.out.println("减少元素后未处理的返回：" + Arrays.toString(r));
}

04.当前集合转至指定数组 toArray(T[] a)

参数：a —— 指定存入的数组

注意：
1. 本方法如果集合元素个数可存入指定的数组则返回指定数组，否则会根据指定数组的类型新创建一个以集合元素个数为长度的数组
2. 若指定数组内的元素会被替换掉，不建议使用已有数据的数组，剩余原数据与拷贝数据之间使用null分隔
3. 若在生成待返回数组(已比较过指定数组长度和集合元素个数)和生成迭代器之间集合元素减少，导致数组长度大于集合元素个数，会通过调用Arrays.copyOf将多余的null值数组部分去除，防止返回的数组中包含null值
4. 若在生成待返回数组(已比较过指定数组长度和集合元素个数)和生成迭代器之间集合元素增加，导致数组长度小于集合元素个数，在循环结束会调用finishToArray()方法处理，它会生成足够容量的新数组将已遍历的值复制进去，再将剩余元素存入
5. 如需在生成迭代器后进行增删改等 *** 作请尽量使用迭代器中的方法，这些方法会将集合的改变与迭代器同步

补充：
1. Array.newInstance() 方法创建数组与普通初始化的唯一区别是 —— 适用于泛型，在不确定数组类型时通过此方法创建避免了使用Object[]后再次传换类型。
2. public static native void arraycopy(Object src, int srcPos, Object dest, int destPos, int length) 方法标有native关键字，表示本方法为外部方法，参数说明 —— ( 原数组[即要被复制的数组], 原数组开始复制的下标, 目标数组, 目标数组开始存放拷贝元素的下标, 复制的元素个数 )

// 源码
public <T> T[] toArray(T[] a) {
    // 获取当前集合的元素个数
    int size = size();
    // 判断指定数组长度是否大于等于集合元素个数，不等于则新建一个数组
    T[] r = a.length >= size ? a :
              (T[])java.lang.reflect.Array
              .newInstance(a.getClass().getComponentType(), size);
    // 迭代器，注意在此处生成迭代器之前数组个数已确定，但是集合个数仍可能改变        
    Iterator<E> it = iterator();
    // 注意此处循环从0开始进行赋值，因此即使原数组长度可以储存集合元素，内部的数据会被替换
    for (int i = 0; i < r.length; i++) {
        // 判断集合元素是否已遍历完，遍历完即数组长度大于集合元素个数
        if (! it.hasNext()) { 
            // 若使用的数组即指定数组(集合元素个数<数组长度)，当前元素赋值为null
            // 出现情况：原指定数组可以存放下元素，生成后又有元素移除
            if (a == r) {
                r[i] = null; 
            } else if (a.length < i) {
                // 1.a的长度与r的长度不同(不是指定数组，a的长度小于集合元素个数)
                // 2.r的长度大于集合元素个数(集合在生成迭代器之前有移除 *** 作)
                // 出现情况：虽进行了移除元素 *** 作，但是移除后仍无法存入原数组，使用Arrays.copyOf()复制，去除多余的长度
                return Arrays.copyOf(r, i);
            } else {
                // 进入条件：a != r && a.length >= i
                // a != r —— 指定数组长度小于原集合元素个数，生成了新数组
                // a.length >= i —— 指定数组长度大于当前集合元素个数
                // 出现情况：移除元素过多已可以使用原数组进行存储，使用指定数组储存
                System.arraycopy(r, 0, a, 0, i);
                // 若原数组长度大于集合元素个数，当前元素赋值为null，用于分隔拷贝数据与原数据
                if (a.length > i) {
                    a[i] = null;
                }
            }
            return a;
        }
        r[i] = (T)it.next();
    }
    // 判断是否在生成r数组和生成迭代器之间集合元素增加
    return it.hasNext() ? finishToArray(r, it) : r;
}

// 中途减少元素示例1：元素个数仍大于指定数组长度
@Test
void contextLoads() {
    // 模拟集合 - 5个元素
    List<String> list = new ArrayList<>();
    list.add("1");
    list.add("2");
    list.add("3");
    list.add("4");
    list.add("5");
    // 模拟传入数组 - 长度为3
    String[] a = new String[3];
    // 指定数组有元素存在
    a[0] = "100";

    int size = list.size();
    // 新数组长度初始长度：5
    String[] r = a.length >= size ? a :
            (String[])java.lang.reflect.Array
                    .newInstance(a.getClass().getComponentType(), size);

    // 中途移除元素，且移除后集合元素个数可存放于指定数组中(此时集合中有4个元素了)
    list.remove(4);

    Iterator<String> it = list.iterator();
    for (int i = 0; i < r.length; i++) {
        if (! it.hasNext()) {
            if (a == r) {
                r[i] = null;
            } else if (a.length < i) {
                // 原(return Arrays.copyOf(r, i);)
                // 减少元素后新数组返回：[1, 2, 3, 4]
                System.out.println("减少元素后新数组返回：" + Arrays.toString(Arrays.copyOf(r, i)));
                break;
            } else {
                System.arraycopy(r, 0, a, 0, i);
                if (a.length > i) {
                    a[i] = null;
                }
            }
            // 原(return a;)
            System.out.println("减少元素后指定数组返回：" + Arrays.toString(a));
            break;
        }
        r[i] = it.next();
    }
    // 减少元素后未处理的返回(新数组)：[1, 2, 3, 4, null]
    System.out.println("减少元素后未处理的返回(新数组)：" + Arrays.toString(r));
}

// 中途减少元素示例2：元素个数小于指定数组长度
@Test
void contextLoads() {
    // 模拟集合 - 5个元素
    List<String> list = new ArrayList<>();
    list.add("1");
    list.add("2");
    list.add("3");
    list.add("4");
    list.add("5");
    // 模拟传入数组 - 长度为3
    String[] a = new String[3];
    // 指定数组有元素存在
    a[0] = "100";

    int size = list.size();
    // 新数组长度初始长度：5
    String[] r = a.length >= size ? a :
            (String[])java.lang.reflect.Array
                    .newInstance(a.getClass().getComponentType(), size);

    // 中途移除元素，且移除后集合元素个数可存放于指定数组中(此时集合中只有1个元素了)
    list.remove(4);
    list.remove(3);
    list.remove(2);
    list.remove(1);

    Iterator<String> it = list.iterator();
    for (int i = 0; i < r.length; i++) {
        if (! it.hasNext()) {
            if (a == r) {
                r[i] = null;
            } else if (a.length < i) {
                // 原(return Arrays.copyOf(r, i);)
                System.out.println("减少元素后新数组返回：" + Arrays.toString(Arrays.copyOf(r, i)));
                break;
            } else {
                System.arraycopy(r, 0, a, 0, i);
                if (a.length > i) {
                    a[i] = null;
                }
            }
            // 原(return a;)
            // 减少元素后指定数组返回：[1, null, null]
            System.out.println("减少元素后指定数组返回：" + Arrays.toString(a));
            break;
        }
        r[i] = it.next();
    }
    // 减少元素后未处理的返回(新数组)：[1, null, null, null, null]
    System.out.println("减少元素后未处理的返回(新数组)：" + Arrays.toString(r));
}

// 指定数组有元素示例
@Test
void contextLoads() {
    // 模拟集合 - 5个元素
    List<String> list = new ArrayList<>();
    list.add("1");
    list.add("2");
    list.add("3");
    list.add("4");
    // 模拟传入数组 - 长度为3
    String[] a = new String[]{"a","b","c","d","e","f"};

    int size = list.size();
    // 新数组长度初始长度：5
    String[] r = a.length >= size ? a :
            (String[])java.lang.reflect.Array
                    .newInstance(a.getClass().getComponentType(), size);

    Iterator<String> it = list.iterator();
    for (int i = 0; i < r.length; i++) {
        if (! it.hasNext()) {
            if (a == r) {
                // 本方法进入此分支
                r[i] = null;
            } else if (a.length < i) {
                // 原(return Arrays.copyOf(r, i);)
                System.out.println("减少元素后新数组返回：" + Arrays.toString(Arrays.copyOf(r, i)));
                break;
            } else {
                System.arraycopy(r, 0, a, 0, i);
                if (a.length > i) {
                    a[i] = null;
                }
            }
            // 原(return a;)
            // 减少元素后指定数组返回：[1, 2, 3, 4, null, f]
            System.out.println("减少元素后指定数组返回：" + Arrays.toString(a));
            break;
        }
        r[i] = it.next();
    }
    // 减少元素后未处理的返回(新数组)：[1, 2, 3, 4, null, f]
    System.out.println("减少元素后未处理的返回(新数组)：" + Arrays.toString(r));
}

05.新增元素 add(E e)

参数：e —— 新增的元素

注意：本方法是用于重写的，若未重写直接调用会直接抛出UnsupportedOperationException异常

拓展：Arrays.asList()生成的集合其实是Arrays的内部类，而不是一般的ArrayList，此内部类没有重写add()，调用会报错

// 源码
public boolean add(E e) {
    throw new UnsupportedOperationException();
}

// 源码示例：Arrays.asList() 里的内部类 ArrayList
// 注意：本方法中的 ArrayList<>(E) 内部类并没有实现 add() 方法，因此使用 Arrays.asList() 生成的集合进行 add()  *** 作会抛出异常

public static <T> List<T> asList(T... a) {
    return new ArrayList<>(a);
}
// 以下为 Arrays 里调用的 new ArrayList<>(E) 内部类方法
private static class ArrayList<E> extends AbstractList<E> implements RandomAccess, java.io.Serializable
{
    private static final long serialVersionUID = -2764017481108945198L;
    private final E[] a;

    ArrayList(E[] array) {
        a = Objects.requireNonNull(array);
    }

    @Override
    public int size() {
        return a.length;
    }

    @Override
    public Object[] toArray() {
        return a.clone();
    }

    @Override
    @SuppressWarnings("unchecked")
    public <T> T[] toArray(T[] a) {
        int size = size();
        if (a.length < size)
            return Arrays.copyOf(this.a, size,
                                 (Class<? extends T[]>) a.getClass());
        System.arraycopy(this.a, 0, a, 0, size);
        if (a.length > size)
            a[size] = null;
        return a;
    }

    @Override
    public E get(int index) {
        return a[index];
    }

    @Override
    public E set(int index, E element) {
        E oldValue = a[index];
        a[index] = element;
        return oldValue;
    }

    @Override
    public int indexOf(Object o) {
        E[] a = this.a;
        if (o == null) {
            for (int i = 0; i < a.length; i++)
                if (a[i] == null)
                    return i;
        } else {
            for (int i = 0; i < a.length; i++)
                if (o.equals(a[i]))
                    return i;
        }
        return -1;
    }

    @Override
    public boolean contains(Object o) {
        return indexOf(o) != -1;
    }

    @Override
    public Spliterator<E> spliterator() {
        return Spliterators.spliterator(a, Spliterator.ORDERED);
    }

    @Override
    public void forEach(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        for (E e : a) {
            action.accept(e);
        }
    }

    @Override
    public void replaceAll(UnaryOperator<E> operator) {
        Objects.requireNonNull(operator);
        E[] a = this.a;
        for (int i = 0; i < a.length; i++) {
            a[i] = operator.apply(a[i]);
        }
    }

    @Override
    public void sort(Comparator<? super E> c) {
        Arrays.sort(a, c);
    }
}

// 示例
@Test
void contextLoads4() {
    Integer[] r = {1,2,3,4,5,6};
    List<Integer> asList = Arrays.asList(r);
    // [1, 2, 3, 4, 5, 6]
    System.out.println(asList);
    // java.lang.UnsupportedOperationException
    asList.add(7);
    System.out.println(asList);
}

06.移除元素 remove(Object o)

参数：o —— 移除的元素

注意：
1. 本方法仅移除集合中第一次出现的指定元素，移除后就返回true
2. 若从集合中未找到指定元素会返回false

// 源码
public boolean remove(Object o) {
    Iterator<E> it = iterator();
    if (o==null) {
        // null的情况单独判断，使用eqauls匹配会空指针
        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;
}

// 示例
@Test
void contextLoads5() {
    List<String> list = new ArrayList<>();
    list.add("1");
    list.add("2");
    list.add("1");
    list.add("4");
    list.add("1");
    // [1, 2, 1, 4, 1]
    System.out.println(list);
    // 移除元素'1' true
    System.out.println(list.remove("1"));
    // 移除元素'5' false
    System.out.println(list.remove("5"));
    // [2, 1, 4, 1]
    System.out.println(list);
}

07.是否包含某一集合全部元素 containsAll(Collection c)

参数：c —— 指定集合

注意：本方法底层调用的实际还是contains(Object o)循环比较的

// 源码
public boolean containsAll(Collection<?> c) {
    for (Object e : c)
        if (!contains(e))
            return false;
    return true;
}

08.新增指定集合中的全部元素 addAll(Collection c)

参数：c —— 指定集合

注意：
1. 本方法底层调用的实际上是add(E e)，因此此方法必须重写，未重写add(E e)方法时，会抛出UnsupportedOperationException异常。
2. 本方法是循环全部指定集合进行多次元素插入实现的，因此重复元素也会插入，不会去重，如需元素唯一需在重写add(E e)方法实现，例如HashSet

// 源码
public boolean addAll(Collection<? extends E> c) {
    boolean modified = false;
    for (E e : c)
        if (add(e))
            modified = true;
    return modified;
}

// HashSet示例
@Test
void contextLoads5() {
    Set<String> set = new HashSet<>();
    set.add("1");
    set.add("2");
    set.add("1");
    set.add("3");
    set.add("1");
    // [1, 2, 3]
    System.out.println(set);
    List<String> list = new ArrayList<>();
    list.add("2");
    list.add("4");
    list.add("2");
    // [2, 4, 2]
    System.out.println(list);
    set.addAll(list);
    // [1, 2, 3, 4]
    System.out.println(set);
}

09.移除指定集合包含的全部元素 removeAll(Collection c)

参数：c —— 指定集合

注意：
1. 若未从集合中找到指定集合中任一元素会返回false
2. 本方法会移除指定集合中包含的全部元素，无论在当前集合中有几个此元素

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

// 示例
@Test
void contextLoads5() {
    AbstractCollection<Integer> collection = new ArrayList<>();
    collection.add(1);
    collection.add(2);
    collection.add(3);
    collection.add(1);
    collection.add(1);
    // [1, 2, 3, 1, 1]
    System.out.println(collection);
    List<Integer> list = new ArrayList<>();
    list.add(1);
    list.add(4);
    list.add(1);
    // [1, 4, 1]
    System.out.println(list);
    collection.removeAll(list);
    // [2, 3]
    System.out.println(collection);
}

10.去除非指定集合中的元素 retainAll(Collection c)

参数：c —— 指定集合

注意：
1. 若未从集合中找到不属于指定集合中任一元素会返回false
2. 本方法会移除不属于指定集合中包含的全部元素，无论在当前集合中有几个此元素，留下的元素不会去重，原集合有几个仍然还有几个

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

@Test
void contextLoads5() {
    AbstractCollection<Integer> collection = new ArrayList<>();
    collection.add(1);
    collection.add(2);
    collection.add(3);
    collection.add(1);
    collection.add(1);
    // [1, 2, 3, 1, 1]
    System.out.println(collection);
    List<Integer> list = new ArrayList<>();
    list.add(1);
    list.add(4);
    list.add(1);
    // [1, 4, 1]
    System.out.println(list);
    collection.retainAll(list);
    // [1, 1, 1]
    System.out.println(collection);
}

10.清空集合 clear()

注意：本方法实际是一个一个元素遍历移除的

public void clear() {
    Iterator<E> it = iterator();
    while (it.hasNext()) {
        it.next();
        it.remove();
    }
}

11.字符串输出 toString()

备注：输出格式 —— [element1, element2, element3]

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