Java 容器总结(一)

Java 容器总结(一) —— ArrayList

1、ArrayList 的基本原理是：内部有一个数组 elementData，一般会有一些预留的空间，有一个整数 size 记录实际的元素个数。elementData 会随着实际元素个数的增多而重新分配，而 size 则始终记录实际的元素个数。

2、add(E e) 方法源码解析

public boolean add(E e) {
    // 首先调用 ensureCapacityInternal 确保数组容量是够的
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}
------------------
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 表示内部的修改次数，modCount++ 当然就是增加修改次数
    modCount++;

    // overflow-conscious code  这里指整数运算超出其取值范围的情况
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
----------------
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    // 右移一位相当于除 2，所以，newCapacity 相当于 oldCapacity 的 1.5 倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    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);
}
---------------
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

3、remove(int index) 方法源码解析

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);
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}
---------------
private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

4、迭代
foreach 适用于各种容器，比较通用。其背后的实现原理是，编译器会将 foreach 转换为类似如下代码：

// 原先代码
public class Test {
    public static void main(String[] args) {
        ArrayList<String> list = new ArrayList<String>();
        for (String s : list) {
            System.out.println(s);
        }
    }
}
// 编译后的 class 代码
public class Test {
    public Test() {
    }

    public static void main(String[] args) {
        ArrayList<String> list = new ArrayList();
        Iterator var2 = list.iterator();

        while(var2.hasNext()) {
            String s = (String)var2.next();
            System.out.println(s);
        }

    }
}

迭代相关的源码：

// ArrayList 实现了 Iterable 接口，Iterable 表示可迭代的
public interface Iterable<T> {
    Iterator<T> iterator();
}
--------------
// Iterable 中的 iterator 方法返回一个实现了 Iterator 接口的对象
public interface Iterator<E> {
    // hasNext() 判断是否还有元素未访问
    boolean hasNext();
    // next() 返回下一个元素
    E next();
    // remove() 删除最后返回的元素
    void remove();
}

所以，只要对象实现了 Iterable 接口，就可以使用 foreach 语法，编译器会转换为调用 Iterable 和 Iterator 接口的方法。

5、Iterable & Iterator

• Iterable 表示对象可以被迭代，它有一个方法 iterator()，返回 Iterator 对象，实际通过 Iterator 接口的方法进行遍历。
• 如果对象实现了 Iterable，就可以使用 foreach 语法。
• 类可以不实现 Iterable，也可以创建 Iterator 对象。

6、除了 iterator()，ArrayList 还提供了两个返回 Iterator 接口的方法：
public ListIterator listIterator()
public ListIterator listIterator(int index)

ListIterator 扩展了 Iterator 接口，增加了一些方法，向前遍历、添加元素、修改元素、返回索引位置等。

public interface ListIterator<E> extends Iterator<E> {
    boolean hasPrevious();
    E previous();
    int nextIndex();
    int previousIndex();
    void set(E e);
    void add(E e);
}

listIterator() 方法返回的迭代器从 0 开始，而 listIterator(int index) 方法返回的迭代器从指定位置 index 开始。

7、迭代器的陷阱
关于迭代器，有一种常见的误用，就是在迭代的中间调用容器的删除方法。这时候一般都会抛出 java.util.ConcurrentModificationException 异常。

// 调用容器的 remove 方法，会产生 ConcurrentModificationException
public void remove(ArrayList<Integer> list){
    for(Integer a : list){
        if(a<=100){
            list.remove(a);
        }
    }
}

因为迭代器内部会维护一些索引位置相关的数据，要求在迭代过程中，容器不能发生结构性变化，否则这些索引位置就失效了。

// 而使用迭代器的 remove 方法，则不会产生异常
public static void remove(ArrayList<Integer> list){
    Iterator<Integer> it = list.iterator();
    while(it.hasNext()){
        if(it.next()<=100){
            it.remove();
        }
    }
}

8、迭代器的实现原理 —— ArrayList 中 iterator 方法的实现

public Iterator<E> iterator() {
    return new Itr();
}
--------------
// Itr 是 ArrayList 的一个成员内部类，实现了 Iterator 接口
private class Itr implements Iterator<E> {
    // 表示下一个要返回的元素位置
    int cursor;       // index of next element to return
    // 表示最后一个被返回元素的索引位置，-1 表示没有返回过任何元素或者被删除了
    int lastRet = -1; // index of last element returned; -1 if no such
    // expectedModCount 期望的修改次数，初始化为外部类当前的修改次数 modCount
    int expectedModCount = modCount;

    Itr() {}

    public boolean hasNext() {
        return cursor != size;
    }

    @SuppressWarnings("unchecked")
    public E next() {
        // 每次迭代都去检查预期的 ModCount 和 现在的 ModCount 是否一致
        checkForComodification();
        int i = cursor;
        if (i >= size)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        // 刚才判断 i < size 这会 i > 数组 length，中间数组结构发生改变
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        cursor = i + 1;
        return (E) elementData[lastRet = i];
    }

    public void remove() {
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();

        try {
            // 调用了 ArrayList 的 remove 方法，注意这里删除的是最后一个返回的元素的索引位置！！！
            ArrayList.this.remove(lastRet);
            // 删除元素以后，后面的元素就会顶上来，所以指示下一个元素为被删除位置上的元素
            cursor = lastRet;
            // 最后一个返回的元素删了，不存在了，所以 -1 表示
            lastRet = -1;
            // 修改 expectedModCount，只有这样迭代的时候才不会抛异常
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }

    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}
--------------

每次发生结构性变化的时候 modCount 都会增加，而每次迭代器操作的时候都会检查 expectedModCount 是否与 modCount 相同，这样就能检测出结构性变化。

注意：使用 iterator 的 remove 方法前，必须先调用 next，从而为 lastRet 赋上正确的值，要不然是默认值 0，输出的结果很可能就是错的。而且循环删除的时候，第一次删除成功以后 lastRet 的值为 -1，再删的时候会抛异常 java.lang.IllegalStateException。

9、迭代器的好处
迭代器语法更为通用，它适用于各种容器类。迭代器表示的是一种关注点分离的思想，将数据的实际组织方式与数据的迭代遍历相分离，是一种常见的设计模式。需要访问容器元素的代码只需要一个 Iterator 接口的引用，不需要关注数据的实际组织方式，可以使用一致和统一的方式进行访问。而提供 Iterator 接口的代码了解数据的组织方式，可以提供高效的实现。从封装的思路上讲，迭代器封装了各种数据组织方式的迭代操作，提供了简单和一致的接口。

10、Java 的各种容器类有一些共性的操作，这些共性以接口的方式体现，Iterable 接口就是如此。此外，ArrayList 还实现了三个主要的接口 Collection, List 和 RandomAccess。

11、Collection 接口
Collection 表示一个数据集合，数据间没有位置或顺序的概念。
boolean retainAll(Collection<?> c); retainAll 只保留参数容器中的元素，其他元素会进行删除。

有一个抽象类 AbstractCollection 对 Collection 接口中的很多方法都提供了默认实现，实现的方式就是利用迭代器方法逐个操作。ArrayList 继承了 AbstractList，而 AbstractList 又继承了 AbstractCollection，ArrayList 对其中一些方法进行了重写，以提供更为高效的实现。

12、List 表示有顺序或位置的数据集合，它扩展了 Collection。

13、RandomAccess 接口
RandomAccess 是一个标记接口，是一个没有任何代码的接口，用于声明类的一种属性。

实现了 RandomAccess 接口的类表示可以随机访问，可随机访问就是具备类似数组那样的特性，数据在内存是连续存放的，根据索引值就可以直接定位到具体的元素，访问效率很高。

有没有声明 RandomAccess 有什么关系呢？主要用于一些通用的算法代码中，它可以根据这个声明而选择效率更高的实现。

14、ArrayList 与 数组的相互转换

// 第一个方法返回是 Object 数组
public Object[] toArray() {
    return Arrays.copyOf(elementData, size);
}
-----------
// 第二个方法返回对应类型的数组，如果参数数组长度足以容纳所有元素，就使用该数组，否则就新建一个数组
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
    if (a.length < size)
        // Make a new array of a's runtime type, but my contents:
        return (T[]) Arrays.copyOf(elementData, size, a.getClass());
    System.arraycopy(elementData, 0, a, 0, size);
    // 如果指定的数组能容纳队列，并有剩余的空间（即数组的元素比队列多），那么会将数组中紧接 collection 尾部的元素设置为 null。（仅在调用者知道列表中不包含任何 null 元素时才能用此方法确定列表长度）。
    if (a.length > size)
        a[size] = null;
    return a;
}

15、Arrays 中有一个静态方法 asList 可以返回对应数组的 List。

public static <T> List<T> asList(T... a) {
    return new ArrayList<>(a);
}
--------
// Arrays 类中的 ArrayList 静态内部类
private static class ArrayList<E> extends AbstractList<E>
        implements RandomAccess, java.io.Serializable
    {......}

需要注意的是，这个方法返回的 List，它的实现类并不是真正的 ArrayList，而是 Arrays 类的一个内部类，在这个内部类的实现中，内部用的的数组就是传入的数组，没有拷贝，也不会动态改变大小，所以对数组的修改也会反映到 List 中。对 List 调用 add/remove 方法会抛出 java.lang.UnsupportedOperationException 异常，因为内部类中根本就不存在这些方法。

要使用 ArrayList 完整的方法，应该新建一个 ArrayList：List<Integer> list = new ArrayList<Integer>(Arrays.asList(i));

16、对于 ArrayList，它的特点是：内部采用动态数组实现，这决定了：

• 可以随机访问，按照索引位置进行访问效率很高，效率是 O(1)。
• 除非数组已排序，否则按照内容查找元素效率比较低，具体是 O(N)。
• 添加元素的效率还可以，重新分配和拷贝数组的开销被平摊了，具体来说，添加 N 个元素的效率为 O(N)。
• 插入和删除元素的效率比较低，因为需要移动元素，具体为 O(N)。

参考博客

Java编程的逻辑 - 剖析 ArrayList