Collection(二)

¶Collection(二)

¶一. 概述

在 Collection(一) 中简单地从 Collection的数据结构和主要实现接口描述了它们各自定义的的特点，以及能够实现什么样的集合数据结构，接下来将按照 List<E>,Set<E>,Queue<E> 这样的顺序来了解它们以及各自实现类的特点，包括一些重要方法的源码理解分析等。

¶二、List: 顺序集合，支持扩容操作

Collection-List

继承 Collection 结构，增加了支持下标的增删方法,意味着它的实现类既支持直接通过指定元素进行添加删除，也支持下标位置添加删除
而通过元素确定下标位置的方法，在接触过的更基本的数据结构中，可以想到数组也具备这个功能
它的迭代器是自己的内部类，继承了 Iterator 接口的 ListIterator

¶三. ArrayList: 可扩容的顺序泛型集合

先看一下继承图

Collection-ArrayList

继承了 AbstractList 类并且实现 List 接口，抽象类提供的是容量检查，克隆，对象锁相关的方法，对象相关的方法从Object中继承而来，让ArrayList具备了线程安全编程的能力

ArrayList 类本身具备一些特定的属性和方法:

属性：
- DEFAULT_CAPACITY:int [=10]: 默认容量大小,使用无参构造时会用这个容量初始化一个内部对象数组
- EMPTY_ELEMENTDATA:Object[] : 空对象数组，提供给空实例使用
- DEFAULTCAPACITY_EMPTY_ELEMENTDATA:Object[]: 内部共享的默认大小数组
- elementData(int):Object[] : 缓存集合有序元素的数组,集合的size就是这个数组的长度，这个属性不可被序列化
- size:int : 包含的元素数量
- MAX_ARRAY_SIZE:int [=Integer.MAX_VALUE-8]:集合允许定义的最大长度,也受到虚拟机参数的影响，空间不足继续分配容量会导致内存溢出
- modCount:int: 记录集合结构性改变的次数，既size改变的情况，如果在遍历的过程中发生了未预期的元素容量变化，会抛出异常，其实从它的内部元素存储结构也可以得知，按照数组存储元素进行遍历，下标都是已经分配好的，改变元素例如删除或者插入，会导致下标变化，获取到非预期的值，所以要记录集合被改变的次数，另外这个属性不可被序列化。
从这些属性能了解到的东西是ArrayList是通过维护内部的对象数组来存取元素
它并不支持并发修改，modCount 属性用来检查集合内部数组的元素结构,例如长度和顺序等是否被破坏

方法:

构造方法：

无参构造

1
2
3

public ArrayList(){ 
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

使用默认容量初始化内部数组，size = 10

指定初始容量

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

判断指定的容量大于0或者等于0，用不同的常量初始化内部数组

集合参数构造

public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

首先会调用 Collection接口子类都会实现的方法 toArray() 将集合转换成 ArrayList 能够接受的数组形式
判断目标数组的元素数量，存在元素的情况下调用数组元素拷贝方法 Arrays.copyOf(U[] original, int newLength, Class<? extends T[]> newType) ，把所有元素从内部数组拷贝到参数数组，再重新赋值给内部数组

进一步跟踪调用可以看到实际调用了一个 native 方法 System.arraycopy(Object src, int srcPos,Object dest, int destPos, int length) 完成数组拷贝:

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

//native 方法， 位于System.java类
public static native void arraycopy(Object src,  int  srcPos, Object dest, int destPos, int length);
//这个方法的作用是将 src(源对象)，从 srcPos(起点下标)开始复制 length(需要复制的长度)个元素到 dest(目标对象)的 destPos(目标位置)之后

构造方法到此结束了，常用的是无参构造和指定容量构造，因此在使用集合的时候，通常是在无法确定元素数量而且元素可能会继续增加的情况下，因此不指定或者指定一个大概的容量
但是在明确元素数量并且不需要集合的扩展能力以及泛型特性时，应该考虑使用数组来存放元素，因为集合的动态扩容每次都会进行数组元素拷贝，源数组越大，资源占用越多，效率越低
而且大容量集合在操作不当的情况下容易引起内存泄漏

重要方法：

ensureCapacityInternal(int minCapacity) :在所有的新增操作中都会调用，用来确认当前集合容量是否足够存储元素

 private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
 }

//计算容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    //如果内部数组是默认容量数组，返回相对较大的那个值
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

//判断当前数组的容量是否小于增加元素后的容量，是就进行扩容
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

在制定下标的插入方法中，还会先调用 rangeCheckForAdd(index) 检查下标是否越界

grow() : 重点：集合的扩容方法

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    //原有容量的1.5倍扩容，后面的位移操作等于 oldCapacity/2
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    //判断扩容后的大小是否小于新增元素后的数组大小
    if (newCapacity - minCapacity < 0)
   		newCapacity = minCapacity;
    //如果扩容后数组大小超过了 MAX_ARRAY_SIZE，会将容量提升到 Integer.MAX_VALUE
    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);
}

扩容的依据是添加元素后的容量大于当前容量，然后进行数组大小扩容和原数组的元素拷贝

但每次都进行1.5倍扩容，在某些情况下是浪费了空间的，例如那些原数组足够大，但只会扩容一次的集合，可以考虑调用 trimToSize()进行集合瘦身

public void trimToSize() {
    modCount++;
    if (size < elementData.length) {
        elementData = (size == 0)
            ? EMPTY_ELEMENTDATA
            //如果当前数组大小超过了数组内的元素数量，会将数组元素重新拷贝到刚好容纳所有元素的数组中，节约空间
            : Arrays.copyOf(elementData, size);
    }
}

clone():克隆集合，JDK文档有这样一句描述: The elements themselves are not copied. 意思是这个方法会返回当前集合的一个浅拷贝，但是不会将数组中的元素本身也进行拷贝,意思并不是调用拷贝方法获取不到集合元素，而是不会在拷贝数组的同时调用对象的拷贝方法把对象也拷贝一遍，只是把数组和size 属性赋值给了新的集合并返回.

public Object clone() {
    try {
        ArrayList<?> v = (ArrayList<?>) super.clone();
        v.elementData = Arrays.copyOf(elementData, size);
        v.modCount = 0;
        return v;
    } catch (CloneNotSupportedException e) {
        // this shouldn't happen, since we are Cloneable
        throw new InternalError(e);
    }
}

可以看到只是进行了数组赋值，返回了新对象的引用

add(E) ,add(int,E) : 新增元素，从最后的位置插入或者在指定位置插入，将其后的元素整体后移一位，它们的实现也有区别

//不指定插入位置新增
public boolean add(E e) {
    //判断是否需要扩容
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    //插入元素
    elementData[size++] = e;
    return true;
}

//指定插入位置
public void add(int index, E element) {
    rangeCheckForAdd(index);
	
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    //区别在这里，为了在指定位置插入元素，需要将该位置之后的所有元素都后移一位，意味着往头部插入元素的效率会很低
    //如果和链表对比这个缺点更加明显，链表只需要改变前后元素和插入元素的引用
    System.arraycopy(elementData, index, elementData, index + 1, size - index);
    elementData[index] = element;
    size++;
}

指定插入位置的元素新增，自己调用了拷贝方法进行数组元素的移动，要移动的元素越多，插入效率越低
可以的话尽量避免在集合的前面插入元素，如果是插入删除元素比较频繁的情况，建议使用链表代替存储元素

remove(Object)，remove(int) : 移除元素，指定元素或者指定下标位置

public E remove(int index) {
    rangeCheck(index);

    modCount++;
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    //移除元素也要把数组进行拷贝，避免存在空引用
    if (numMoved > 0)
   		System.arraycopy(elementData, index+1, elementData, index,numMoved);
    //将被移除元素的位置置空，下一次GC便会回收没有引用对象的对象
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

//指定元素移除
public boolean remove(Object o) {
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                //fastRemove(index) 通过下标删除元素，并将数组元素移动，数组末尾置空等
                fastRemove(index);
                return true;
            }
    } else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}

可以看到删除元素也有复制移动数组的必要，大量元素的复制移动都是需要避免的

removeAll(Collection<? extends E>)，retainAll(Collection<? extends E>)，batchRemove(Collection<? extends E>,boolean):

之所以放在一起是因为它们都是调用了 batchReomve 来进行元素移除或者保留的

//removeAll
public boolean removeAll(Collection<?> c) {
    Objects.requireNonNull(c);
    //参数 false
    return batchRemove(c, false);
}

//retainAll
public boolean retainAll(Collection<?> c) {
    Objects.requireNonNull(c);
    //参数true
    return batchRemove(c, true);
}

//batchRemove
private boolean batchRemove(Collection<?> c, boolean complement) {
    final Object[] elementData = this.elementData;
    int r = 0, w = 0;
    boolean modified = false;
    try {
        for (; r < size; r++)
            //关键在这儿,通过complete参数来判断是保留参数数组包含的元素还是移除参数数组包含的元素
            if (c.contains(elementData[r]) == complement)
                //将元素顺序保存在当前数组
                elementData[w++] = elementData[r];
    } finally {
        // Preserve behavioral compatibility with AbstractCollection,
        // even if c.contains() throws.
        //finally 块的方法，保证即便抛出异常也会完成元素拷贝
        //这里移动的方式是把重新添加元素后的数组，从 r 位置开始复制到 数组的 W位置之后，复制的数量是 size - r
        if (r != size) {
            System.arraycopy(elementData, r,elementData, w,size - r);
            w += size - r;
        }
        //进行元素移动后，把剩余元素之外的下标引用置空，可以在下一次 GC 被回收
        if (w != size) {
            // clear to let GC do its work
            for (int i = w; i < size; i++)
                elementData[i] = null;
            modCount += size - w;
            size = w;
            modified = true;
        }
    }
    return modified;
}

一个 batchRemove 方法通过控制 complete 参数来确定是移除还是保留元素，而不用为每个方法实现一个 batchRemove
finally 块的代码，保证在元素遍历没有完成的情况下，将已经确认的元素复制到当前集合中

总结：
- ArrayList 的基本特点是：有序，元素可重复，支持下标索引，动态扩容
  - 有序：指的是的存储的顺序和元素在集合中的顺序一致，并不是元素的大小排序
  - 元素可重复：在 add()/addAll() 方法中我们都没有看到添加元素会进行元素是否存在的校验，从另一方面来说，集合内部数组的每个下标都代表了一个元素，下标是唯一的，在获取我们知晓的元素时非常方便，不同于 HashMap 那样需要通过 key 的 hash() 方法来保证 key唯一，确保一个Key 不会返回两个结果。
  - 支持下标索引：这是由内部实现提供的能力，数组支持下标索引，再加上初始化时的泛型，其实内部就是一个具体类型数组；好处是取元素不需要遍历集合，直接通过下标获取；坏处是为了保证数组的的每个位置都是连续且存在值，在插入和删除元素后需要赋值移动数组元素，移动元素很多时效率不高。
  - 动态扩容：这个可以拿来和数组进行比较，假设我们声明了一个定长10的数组，存满了10个元素之后，想继续存储更多的元素只能重新声明一个数组，另外确定一个容量，把元素都复制过去；而集合的这个所谓动态扩容，从 resize() 方法里面可以看到它就是这么做的，最后产生的数组重新赋值给了集合内部数组，实现了扩容。
- 实践建议：
  - 确定要存储的元素数量且不需要扩容，优先使用数组
  - 确定初次要存储元素数量但需要扩容，初始化集合指定一个容量
  - 声明泛型集合，避免类型安全错误，另外集合的 sort()，contains() 方法等都会调用具体对象的 comparator() ,equals() , hashCode() 方法等，所以存储自定义对象时，必要的话最好重写这些方法。

¶四. LinkedList: 双链表实现的顺序集合

先看一下类继承图:

属性：

first:Node: 头节点的引用，具备 first == null && last == null 以及 first.prev == null && first.item != null 这样的不变性
last:Node: 尾节点的引用，具备 first == null && last == null 以及 last.next == null && last.item != null 这样的不变性
size:int [=0] : 集合的元素数量或者说节点数量
modCount:int [=0] : 记录集合被结构性更改的次数
头节点和尾节点的特性，在插入和删除元素时会用到，链表的元素插入是需要改变节点引用的，而这种 node.prev == null 和 node.next == null 的特性，分别表示它们是头尾节点
modCount 说明它不支持并发修改

主要方法：

构造：

无参构造:
1
public LinkedList(){}
- 构造一个空集合

有參构造:

public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
}

先构造一个空集合，再调用 addAll(Collection) 方法进行元素添加

addAll(Collection<? extends E>) :

public boolean addAll(Collection<? extends E> c) {
    //方法增强的表现
    return addAll(size, c);
}

//addAll(int index,Collection<? extends E> c)
public boolean addAll(int index, Collection<? extends E> c) {
        checkPositionIndex(index);
		
        Object[] a = c.toArray();
        int numNew = a.length;
        if (numNew == 0)
            return false;
		
        Node<E> pred, succ;
        if (index == size) {
            succ = null;
            pred = last;
        } else {
            succ = node(index);
            pred = succ.prev;
        }

        for (Object o : a) {
            @SuppressWarnings("unchecked") E e = (E) o;
            //以pred 节点作为前驱结点，构造要一个要插入的节点，这里是尾部插入，所以后继节点为空
            Node<E> newNode = new Node<>(pred, e, null);
            if (pred == null)
                //判断尾节点是否为空，为空说明是次一次插入节点，当前节点就是头节点
                first = newNode;
            else
                //否则将当前尾节点的next指向newNode
                pred.next = newNode;
            //再将newNode 作为尾节点
            pred = newNode;
        }
		//succ == null 只有在尾插时发生
        if (succ == null) {
            //将 next 指向null 的 pred 节点作为尾节点
            last = pred;
        } else {
            //如果succ != null ，说明是在succ 节点之前插入，而pred又指向了插入的元素,so...
            pred.next = succ;
            succ.prev = pred;
        }

        size += numNew;
        modCount++;
        return true;
}

addAll(int,Collection<? extends E>) 方法中遍历要插入的集合进行插入的操作，也是和之后单个插入类似的，没有做任何元素相等之类的判断，只有改变插入位置前后元素和插入元素的节点引用，这一点来说它的效率比 ArrayList 要高
第一插入元素时会判断头节点是否为空，因为这种情况下的处理和非空集合是不一样的

重要方法：只看一部分最常用的方法实现

addFirst(E):头部插入元素

public void addFirst(E e) {
	//私有方法，用来将插入元素作为头节点链接进来
    linkFirst(e);
}

//linkFirst(E)
private void linkFirst(E e) {
    final Node<E> f = first;
    final Node<E> newNode = new Node<>(null, e, f);
    first = newNode;
    if (f == null)
        //头节点为空，说明是空集合
        last = newNode;
    else
        //集合非空，只需要将原来头节点的 prev 指向插入节点
        f.prev = newNode;
    size++;
    modCount++;
}

方法实现比较简单，和之前看到的 addAll(Collection<? extends E>) 比较类似的步骤是都先判断了是否是空集合

removeFirst():E:移除集合头部元素

public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    //真正用来移除链表头部元素的方法
    return unlinkFirst(f);
}

//ublinkFirst(Node<E> f)
private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    final E element = f.item;
    final Node<E> next = f.next;
    //将原本头节点的item和next 都置空
    f.item = null;
    f.next = null; // help GC
    first = next;
    if (next == null)
        last = null;
    else
        //将原本第二个节点的prev置空，让它成为头节点
        next.prev = null;
    size--;
    modCount++;
    return element;
}

依旧是改变引用达到删除元素的目的

add(E)：直接添加元素的方法

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

//linkLast(E)
void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        //插入队尾
        l.next = newNode;
    size++;
    modCount++;
}

逻辑很类似

remove(Object)：移除指定元素

public boolean remove(Object o) {
    if (o == null) {
        //遍历链表的方法
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                //匹配到元素值之后，unlink
                unlink(x);
                return true;
            }
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

//unlink(Node<E>)
E unlink(Node<E> x) {
    // assert x != null;
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;
	//两个步骤，将x的前驱节点的next指向x的后继结点
    if (prev == null) {
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }
	//将x的后继结点的prev指向x的前驱结点
    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }
	//置空引用
    x.item = null;
    size--;
    modCount++;
    return element;
}

这个方法和之前的linkFirst () ，unlinkFirst()等都很类似

总结:
- 由于底层实现的特殊性，LinkedList没有所谓的扩容一说
- 而在添加和删除元素的方法中可以看到它的效率是很高的，没有任何元素复制移动这种操作

¶五.小结:

1. `List`:接口规定了它的子集具备基于索引位置的 get,set,add,remove 等方法，在不同类型的具体实现中，虽然都支持这种下标索引，但效率因各自的底层实现有所差距，`ArrayList` 是有数组实现的，下标存取很方便 ； 而 `LinkedList`需要先转换成数组再进行这个操作
2. 它们添加和删除元素的方式是一个比较明显的区别，`ArrayList` 在中间插入一个元素之后，需要将插入位置之后的所有元素都后移一位，进行元素的整体拷贝，返回一个新的数组 ; 而在 `LinkedList` 中，它的实现是一条双链表，存储的是 具备前后节点引用的 *Node* 元素，所以它的元素插入只需要改变插入位置前后的元素引用，就可以组成一条新的链表，没有扩容，也没有大量的元素移动
3. LinkedList 同时继承了 Deque 接口，可以自己简单包装一下，实现基于LinkedList 的栈结构和双向队列等。