Java深入学习-Java集合框架（二）AbstractCollection

2018-08-13

Collection, Java-DL

Java集合框架-AbstractCollection

Java集合框架具体实现关系

由点组成的方框如表示接口
由小段线组成的方框如表示抽象类
由实线组成的方框如表示实体类

AbstractCollection

AbstractCollection是一个抽象类，最大限度地实现了Collection接口的方法（抽象类不必实现接口类的所有方法），仅剩下size()和iterator()方法在适当的子类实现

默认的AbstractCollection的实现类是一个不可修改（添加元素）的集合，只需要

实现size()和iterator()方法
实现返回的迭代器中的hasNext()和next()方法

若需要AbstractCollection的实现类是一个可修改（添加元素）的集合，则需要

重写覆盖add()方法（AbstractCollection的add()方法默认抛出 UnsupportedOperationException 异常）
实现返回的迭代器中的remove()方法（Iterator接口的remove()方法默认抛出UnsupportedOperationException异常）

AbstractCollection实现源码分析

1.源码整体架构

构造函数+抽象方法

public abstract class AbstractCollection<E> implements Collection<E> {
    
	//AbstractCollection的实现类需要提供一个空的构造函数
    protected AbstractCollection() {
    }
    
    //需要实现的size()和iterator()抽象方法
    public abstract int size();
	public abstract Iterator<E> iterator();
    
}

2.add(E e):boolean

//默认的AbstractCollection实现类不可修改 因此add方法直接抛出异常
//若需要AbstractCollection实现类可修改 则需要在实现类重写add方法
public boolean add(E e) {
    throw new UnsupportedOperationException();
}

3.遍历集合元素的实现方法

contains、remove都是采取遍历集合元素根据传入参数是否为null来进行不同的比较方法的实现方法

//判断元素o是否在集合中
public boolean contains(Object o) {
    //通过迭代器遍历集合
    Iterator<E> it = iterator();
    if (o==null) {
        while (it.hasNext())
            if (it.next()==null)  //若o为null则直接将元素与null比较
                return true;
    } else {
        while (it.hasNext())
            if (o.equals(it.next()))  //若o不为null则调用o.equals()方法与元素比较
                return true;
    }
    return false;
}

//判断集合c所有元素是否在集合中 具体实现同contains()
public boolean containsAll(Collection<?> c) {
    for (Object e : c)
        if (!contains(e))
            return false;
    return true;
}

//移除集合中的元素o
public boolean remove(Object o) {
    //通过迭代器遍历集合
    Iterator<E> it = iterator();
    if (o==null) {
        while (it.hasNext()) {
            if (it.next()==null) { //若o为null则直接将元素与null比较
                it.remove();
                return true;
            }
        }
    } else {
        while (it.hasNext()) {
            if (o.equals(it.next())) { //若o不为null则调用o.equals()方法与元素比较
                it.remove();
                return true;
            }
        }
    }
    return false;
}

//移除集合中的集合c的所有元素 具体实现同remove()
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;
}

//具体实现同add()
public boolean addAll(Collection<? extends E> c) {
    boolean modified = false;
    for (E e : c)
        if (add(e))
            modified = true;
    return modified;
}

//仅保留集合中集合c的所有元素 具体实现方式通过contains判断遍历元素是否在集合c中 不在则移除
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;
}

4.toArray():Object[]

//将集合元素以Object数组形式返回
public Object[] toArray() {
    //创建Object数组
    Object[] r = new Object[size()];
    Iterator<E> it = iterator();
    for (int i = 0; i < r.length; i++) {
        if (! it.hasNext()) // 复制过程中集合元素变少了
            return Arrays.copyOf(r, i);  //将Object数组复制成当前集合元素数量大小的数组
        r[i] = it.next();
    }
    //复制过程中集合元素变多了 调用finishToArray方法返回增大的Object数组
    return it.hasNext() ? finishToArray(r, it) : r;
}

//将it迭代器剩余的元素添加到数组r中
private static <T> T[] finishToArray(T[] r, Iterator<?> it) {
    //数组r中元素的数量
    int i = r.length;
    while (it.hasNext()) {
        //目前数组r的大小
        int cap = r.length;
        //元素数量与数组r一样大 it剩余元素无法插入数组r 需要扩容
        if (i == cap) {
            //数组r的扩容量为(1.5*cap+1)
            int newCap = cap + (cap >> 1) + 1;
            //若新容量大于MAX_ARRAY_SIZE
            //MAX_ARRAY_SIZE为AbstractCollection类声明的静态变量 值为Integer.MAX_VALUE - 8
            if (newCap - MAX_ARRAY_SIZE > 0)
                //调用hugeCapacity()将newCap调整为合适大小
                newCap = hugeCapacity(cap + 1);
            //将数组r扩容成newCap容量的数组
            r = Arrays.copyOf(r, newCap);
        }
        //将it迭代器的元素添加到数组r中
        r[i++] = (T)it.next();
    }
    //数组中元素的数量与数组r的大小比较
    //若相等则返回数组r 
    //若不等表示数组扩容有剩余空间 则将数组r复制成当前元素数量大小的数组
    return (i == r.length) ? r : Arrays.copyOf(r, i);
}

//用于确定数组极限的值
private static int hugeCapacity(int minCapacity) {
    //cap+1>Integer.MAX_VALUE变成负值 则抛出异常
    if (minCapacity < 0) 
        throw new OutOfMemoryError
        ("Required array size too large");
    //cap+1<=Integer.MAX_VALUE时
    return (minCapacity > MAX_ARRAY_SIZE) ?
        //cap+1在 (MAX_ARRAY_SIZE,Integer.MAX_VALUE]之间
        //数组扩容成Integer.MAX_VALUE 这是最大容量的数组
        Integer.MAX_VALUE :
    //cap+1<MAX_ARRAY_SIZE时
    //数组扩容成MAX_ARRAY_SIZE 这是AbstractCollection类声明的数组最大值
    MAX_ARRAY_SIZE;
}

5.toArray(T[] a): T[]

//将集合元素填充到给定数组a中并返回填充完毕的数组(不一定是数组a)
public <T> T[] toArray(T[] a) {
    //集合元素数量
    int size = size();
    //数组a容量大于等于集合元素数量 则将r指向数组a
    //数组a容量小于集合元素数量 则利用反射创建一个大小为集合数量大小的数组并用r指向它
    T[] r = a.length >= size ? a :
    (T[])java.lang.reflect.Array
        .newInstance(a.getClass().getComponentType(), size);
    Iterator<E> it = iterator();

    for (int i = 0; i < r.length; i++) {
        if (! it.hasNext()) { //复制过程集合元素变少了
            if (a == r) {
                r[i] = null; // 若r引用的是a数组 则让a数组i位后的值全部为null
            } else if (a.length < i) {  //若r引用的是新数组 由于一开始数组a容量小于集合元素数量 因此集合元素都被填充到了新数组中 此时集合元素变少了 因此直接截断新数组返回
                return Arrays.copyOf(r, i);
            } else {  //r引用的是新数组 一开始数组a容量小于集合元素数量 因此集合元素全部被复制到了新数组中 但此时数组a容量大于集合元素数量了 因此需要将新数组的i位元素复制到a数组中 然后a数组i位后的值全部为null 返回a数组
                System.arraycopy(r, 0, a, 0, i);
                if (a.length > i) {
                    a[i] = null;
                }
            }
            return a;
        }
        r[i] = (T)it.next();
    }
    //复制过程集合元素变多情况 参考toArray():Object[]中的扩容方案
    return it.hasNext() ? finishToArray(r, it) : r;
}

6.toString():String

//将集合所有元素以String方式表示
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(' ');
    }
}

AbstractSet

继承了AbstractCollection抽象类，AbstractSet抽象类没有覆盖AbstractCollection类中任何实现，它只是添加了equals(Object o)和hashCode实现

AbstractSet实现源码分析

public abstract class AbstractSet<E> extends AbstractCollection<E> implements Set<E> {
    //无参构造函数 继承类自动调用
    protected AbstractSet() {
    }

    //判断o对象与集合对象是否相等
    public boolean equals(Object o) {
        //判断o对象是否是集合对象(实例地址相等) 则返回true
        if (o == this)
            return true;
		
        //判断o对象与集合对象的类型是否相同 不相同则返回false
        if (!(o instanceof Set))
            return false;
        //将引用类型为Object的o强制类型转换成引用类型为Collection集合类型的c
        Collection<?> c = (Collection<?>) o;
        //判断c集合中元素个数与集合元素个数是否相等 不相等返回false
        if (c.size() != size())
            return false;
        try {
            //调用containsAll方法判断当前集合是否包含c集合所有元素 若包含 由于元素个数相等 则两个集合相同 返回true
            return containsAll(c);
        } catch (ClassCastException unused)   {
            return false;
        } catch (NullPointerException unused) {
            return false;
        }
    }

    //返回集合的哈希码
    public int hashCode() {
        int h = 0;
        Iterator<E> i = iterator();
        while (i.hasNext()) {
            E obj = i.next();
            if (obj != null)
                //由于每个集合元素都是Object对象 调用Object.hashCode()得到每个元素的哈希码
                h += obj.hashCode();
        }
        return h;
    }

    //移除集合中集合c的所有元素
    public boolean removeAll(Collection<?> c) {
        Objects.requireNonNull(c);
        boolean modified = false;

        //通过比较集合元素数量和集合c元素数量 遍历元素数量少的集合 提升效率
        if (size() > c.size()) {
            //集合元素数量大于集合c元素数量 遍历集合c的元素
            for (Iterator<?> i = c.iterator(); i.hasNext(); )
                //集合中若存在集合c的元素则移除
                modified |= remove(i.next());
        } else {
            //集合元素数量小于集合c元素数量 遍历集合的元素
            for (Iterator<?> i = iterator(); i.hasNext(); ) {
                if (c.contains(i.next())) {  //集合c若包含集合的元素 则在集合中移除该元素
                    i.remove();
                    modified = true;
                }
            }
        }
        return modified;
    }

}

equals()方法通过多重的判定来提升效率，而不是直接进行集合各元素的比较
removeAll()方法通过比较集合元素数量和集合c元素数量，遍历元素数量少的集合，提升效率
hashCode()方法通过所有元素都是Object对象的实例，调用Object类的hashCode()方法得到所有元素的哈希码，我们来看下Object类的hashCode()方法研究下怎么计算单个元素的哈希码
1
2
3
public class Object {
public native int hashCode();
}
源码中Object类的hashCode()是采用native修饰符修饰的方法，简单来说，native方法就是一个Java调用非Java代码的接口，称作JNI（Java Native Interface）Java本地接口，官方定义为

“A native method is a Java method whose implementation is provided by non-java code.”

如图是Java代码通过JNI接口调用C++代码的方式，JNI的书写步骤如下
1. 编写带有native声明的方法的Java类
2. 使用javac命令编译编写的Java类
3. 使用java -jni来生成后缀名为.h的头文件
4. 使用其他语言（C、C++）实现本地方法
5. 将本地方法编写的文件生成动态链接库(DLL)

AbstractList

AbstractList主要用于最大程度实现随机访问数据（数组）的接口，对于顺序访问数据（链表）的类应该优先使用AbstractSequentialList类

AbstractList继承AbstractCollection抽象类，AbstractCollection要求子类需要实现size()和iterator()方法，AbstractList仅实现了iterator()方法

AbstractList实现了List接口，实现了其中的一些方法，新增了一个抽象方法get(int)

AbstractList的继承类要实现不可修改元素的列表，只需要实现get(int)【From List】和size()方法【From AbstractCollection】

AbstractList的继承类要实现可修改元素的列表，还要重写add(),set(),remove()方法，否则会抛出UnsupportedOperationException异常

源码分析

1.默认不支持的方法

需要继承类根据自身特点实现或者重写的方法

抽象方法：get(int)
从AbstractCollection继承的方法：add(E)
从List接口实现的不支持的方法：add(int,E)，set(int,E)，remove(int)

abstract public E get(int index);

public boolean add(E e) {
    add(size(), e);
    return true;
}

public void add(int index, E element) {
    throw new UnsupportedOperationException();
}

public E set(int index, E element) {
    throw new UnsupportedOperationException();
}

public E remove(int index) {
    throw new UnsupportedOperationException();
}

2.实现的iterator()方法和Itr内部类

实现了从AbstractCollection继承的iterator()方法，实现了Iterator接口，实现了迭代器的基础功能，为ListItr提供基础方法

//实现了从AbstractCollection继承的iterator()方法
public Iterator<E> iterator() {
    return new Itr();
}
//transient修饰的变量不参与序列化过程
protected transient int modCount = 0;

private class Itr implements Iterator<E> {
    //当前游标位置
    int cursor = 0;  
    //迭代器最后一次调用next()/previous()的位置 调用add()/remove()时该值被初始化为-1
    int lastRet = -1;  
    //用于并发冲突检验 modCount为列表被修改次数
    int expectedModCount = modCount;  
    
    //检测并发冲突 迭代器进行操作时会检测expectedModCount==modCount 若不相等表示迭代器进行操作时列表被修改了 抛出异常
    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }

    //检测游标是否可以后移
    public boolean hasNext() {
        return cursor != size();
    }

    //得到游标索引的元素将游标移至下一位
    public E next() {
        checkForComodification();
        try {
            int i = cursor;
            E next = get(i);  //对于随机访问列表 迭代器使用get(cursor)得到游标索引的元素
            lastRet = i;  //记录最后一次访问元素的索引
            cursor = i + 1;  //将游标移至下一位
            return next;
        } catch (IndexOutOfBoundsException e) {
            checkForComodification();
            throw new NoSuchElementException();
        }
    }

    //删除迭代器最后一次访问的元素
    public void remove() {
        if (lastRet < 0)  //若删除元素坐标为-1 则列表修改过 lastRet被初始化 无法删除
            throw new IllegalStateException();
        checkForComodification();

        try {
            //调用AbstractList的remove(int)方法删除元素
            AbstractList.this.remove(lastRet);
            //完成删除后 元素发生了位移 调整游标坐标
            if (lastRet < cursor)
                cursor--;
            //完成删除后初始化lastRet
            lastRet = -1;
            //调用了remove方法修改列表会增加modCount值 需要同步到expectedModCount
            expectedModCount = modCount;  
        } catch (IndexOutOfBoundsException e) {
            throw new ConcurrentModificationException();
        }
    }
}

3.实现的listIterator()方法和ListItr内部类

通过ListItr内部类实现了List接口的listIterator和listIterator(int index)方法，其余的List接口的方法的实现都是基于ListItr列表迭代器实现

ListItr内部类主要通过继承Itr实现的方法来实现列表迭代器功能，相比于Itr增加了向前遍历、设置cursor游标位置等功能

//返回集合的List迭代器
public ListIterator<E> listIterator() {
    return listIterator(0);
}
//返回从指定坐标开始的List迭代器
public ListIterator<E> listIterator(final int index) {
    rangeCheckForAdd(index);
    return new ListItr(index);
}
//检测指定的坐标是否超过迭代器元素范围
private void rangeCheckForAdd(int index) {
    if (index < 0 || index > size())
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
//指定坐标超过迭代器元素范围的异常提示
private String outOfBoundsMsg(int index) {
    return "Index: "+index+", Size: "+size();
}

//ListItr内部类
private class ListItr extends Itr implements ListIterator<E> {
    //指定坐标的构造函数
    ListItr(int index) {
        cursor = index;
    }
	//检测游标是否可以前移
    public boolean hasPrevious() {
        return cursor != 0;
    }
	//将游标前移再获取当前游标位置的元素
    public E previous() {
        checkForComodification();
        try {
            int i = cursor - 1;  
            E previous = get(i);  //通过get(int)获取元素
            lastRet = cursor = i;  //将游标位置和最后一次操作元素的位置更新
            return previous;
        } catch (IndexOutOfBoundsException e) {
            checkForComodification();
            throw new NoSuchElementException();
        }
    }
    //通过next()得到的元素就是当前游标位置的元素
    public int nextIndex() {
        return cursor;
    }
	//通过previous()得到的元素就是当前游标-1位置的元素
    public int previousIndex() {
        return cursor-1;
    }
	//更新迭代器最后一次操作的元素值为E
    public void set(E e) {
        if (lastRet < 0)  //检测是否有最后一次操作元素
            throw new IllegalStateException();
        checkForComodification();

        try {
            AbstractList.this.set(lastRet, e);  //通过set(int,E)方式更新元素值
            //更新元素值不改变列表大小 因此无需初始化lastRet
            //调用了set()方法修改列表会增加modCount值 需要同步到expectedModCount
            expectedModCount = modCount;  
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }
	//在当前游标增加元素E
    public void add(E e) {
        checkForComodification();

        try {
            int i = cursor;
            AbstractList.this.add(i, e);  //通过add(int,E)方法增加在i位置增加元素E
            lastRet = -1;  //改变了列表大小 初始化lastRet
            cursor = i + 1;  //增加了元素 需要修改当前游标位置
            //调用了add()方法修改列表会增加modCount值 需要同步到expectedModCount
            expectedModCount = modCount; 
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }
}

4.基于ListItr实现或者重写的方法

基于ListItr重写了AbstractCollection的clear()方法

//清空列表
public void clear() {
    removeRange(0, size());
}
//清除列表位置从fromIndex到toIndex的元素
protected void removeRange(int fromIndex, int toIndex) {
    ListIterator<E> it = listIterator(fromIndex);
    for (int i=0, n=toIndex-fromIndex; i<n; i++) {
        it.next();  //将lastRet移动到需要删除的元素位置上
        it.remove();  //删除该元素 并将cursor后移一位
    }
}

基于ListItr实现了List接口的一些方法

//返回集合中第一次出现指定元素的索引，若集合中不存在该元素则返回-1
public int indexOf(Object o) {
    ListIterator<E> it = listIterator();
    if (o==null) {
        while (it.hasNext())
            if (it.next()==null)
                //it.next()得到的元素的坐标是cursor坐标-1
                return it.previousIndex();
    } else {
        while (it.hasNext())
            if (o.equals(it.next()))
                //it.next()得到的元素的坐标是当前cursor坐标-1
                return it.previousIndex();  
    }
    return -1;
}
//返回集合中最后一次出现指定元素的索引，若集合中不存在该元素则返回-1
public int lastIndexOf(Object o) {
    //将cursor设为列表尾
    ListIterator<E> it = listIterator(size());
    if (o==null) {
        //向前遍历
        while (it.hasPrevious())
            if (it.previous()==null)
                //it.previous()得到的元素的坐标是cursor坐标
                return it.nextIndex();  //it.nextIndex()即得到当前cursor坐标
    } else {
        while (it.hasPrevious())
            if (o.equals(it.previous()))
                return it.nextIndex();
    }
    return -1;
}
//基于add()方法实现
public boolean addAll(int index, Collection<? extends E> c) {
    rangeCheckForAdd(index);
    boolean modified = false;
    for (E e : c) {
        add(index++, e);
        modified = true;
    }
    return modified;
}

基于ListItr重写了Object的一些方法

//利用ListItr遍历元素进行比较
public boolean equals(Object o) {
    if (o == this)
        return true;
    if (!(o instanceof List))
        return false;

    ListIterator<E> e1 = listIterator();
    ListIterator<?> e2 = ((List<?>) o).listIterator();
    while (e1.hasNext() && e2.hasNext()) {
        E o1 = e1.next();
        Object o2 = e2.next();
        if (!(o1==null ? o2==null : o1.equals(o2)))
            return false;
    }
    return !(e1.hasNext() || e2.hasNext());
}
//计算集合的哈希码
public int hashCode() {
    int hashCode = 1;
    for (E e : this)
        //使用31的好处在后文解释
        hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());
    return hashCode;
}

计算哈希码使用31的好处：

31是一个质数（素数），与数字相乘的结果也是质数，减少哈希冲突
31*i==32i-i==(i*2^5)-i=(i<<5)-1，即31i可以仅使用*移位运算和减法，算法效率较高
哈希计算尽量选择较大的数，使得计算出的哈希值较大，减少哈希冲突（不使用15的原因）
31仅有5bits，相乘造成数据移除的概率小（不使用63的原因）

Fright For Better Day

ItEassy