2018-05-23

Java ArrayList

基于数组实现

基于java1.8

底层存储结构

ArrayList解决的就是数组的动态扩展问题，底层就是个数组。为了泛型，数组设计为Object类型。额外维护的变量只有size。

ArrayList.java

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable{
    transient Object[] elementData;
    private int size;
}

值得注意的是数据被声明了transient,说明序列化是手动负责。
自行定义了writeObject和readObject方法，要点在于增加了并发修改的感知，因为并不能原子操作，需要遍历数组，不支持并发修改。

ArrayList.java

private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException{
    int expectedModCount = modCount;
    s.defaultWriteObject();
    s.writeInt(size);

    for (int i=0; i<size; i++) {
        s.writeObject(elementData[i]);
    }
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
}

因为ArrayList底层基于数组，随机访问性能良好，因此实现了RandomAccess接口
这个接口是个空白接口，作为一个标记，算法可以根据这个标记优先使用下标遍历，实现更好的性能

容量控制

无参数构造和传入0构造都是空数组，然而是不同的，指向不同的静态空数组

ArrayList.java

private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

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

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

首先看是如何插数据。先确保还有1个容量，然后写入进去。

ArrayList.java

public boolean add(E e) {
    ensureCapacityInternal(size + 1);
    elementData[size++] = e;
    return true;
}

检查容量时提现出了区别，如果是无参数构造，那么会改变需求，DEFAULT_CAPACITY是10。
也就是说明明插第一个数据只要求1个空间，却提了10个空间的要求。

ArrayList.java

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    //最小需求量超出现有，需要扩容
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

扩容策略是先尝试原容量的1.5倍，如果不满足需求就直接扩展为需求量
直接使用Arrays的copyOf方法调整数组大小

ArrayList.java

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);  //1.5 times
    if (newCapacity - minCapacity < 0) //still not enough
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

也就是说如果无参构造的话，第一下容量直接扩到10，而传入0构造的话第一下容量只扩到1。

数据移位

数组的特点是数据连续性，因此插入/删除数据的操作会移动数据保证连续
单一的数据的删除,删除位置后的数据都要移动。先算出移动的数目，System.arraycopy直接做，最后把末尾置null。

ArrayList.java

private void fastRemove(int index) {
    modCount++;
    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
}

多个数据的删除,采用覆盖写的方式，遍历数据，将不删的数据写入到前面相应位置，复杂度O(n)
注意finially块处理了即使中途报错，也保证状态正确

ArrayList.java

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++)
            if (c.contains(elementData[r]) == complement)
                elementData[w++] = elementData[r];
    } finally {
        // Preserve behavioral compatibility with AbstractCollection,
        // even if c.contains() throws.
        if (r != size) {
            System.arraycopy(elementData, r, elementData, w, size - r);
            w += size - r;
        }
        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;
}

只有中间插入时需要移位，先arraycopy挪出index位置，再把新数据填上

ArrayList.java

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

搜索定位

由于没有值的线索，只能遍历查找，查询效率不高

ArrayList.java

public boolean contains(Object o) {
    return indexOf(o) >= 0;
}

public int indexOf(Object o) {
    if (o == null) {
        for (int i = 0; i < size; i++)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

public int lastIndexOf(Object o) {
    if (o == null) {
        for (int i = size-1; i >= 0; i--)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = size-1; i >= 0; i--)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

子列问题

ArrayList的子列并不再是ArrayList，而是单独定制的SubList

ArrayList.java

public List<E> subList(int fromIndex, int toIndex) {
    subListRangeCheck(fromIndex, toIndex, size);
    return new SubList(this, 0, fromIndex, toIndex);
}

子列并没有脱离母体，底层数据是共享的,子列只维护了偏移量
注意子列没有序列化接口，不能网络传输

ArrayList.java

private class SubList extends AbstractList<E> implements RandomAccess {
    private final AbstractList<E> parent;
    private final int parentOffset;
    private final int offset;
    int size;

    SubList(AbstractList<E> parent,
            int offset, int fromIndex, int toIndex) {
        this.parent = parent;
        this.parentOffset = fromIndex;
        this.offset = offset + fromIndex;
        this.size = toIndex - fromIndex;
        this.modCount = ArrayList.this.modCount;
    }
    //...
}

子列的定位只是一个视图，子列和母体相互影响，修改已有数据是可以的，因为数据只是值变化位置并没变
然而如果发生结构性变化，比如增删操作，那必须在子列上调用子列方法进行。
因为如果母体进行了增删操作，子列完全无法感知，子列维护的偏移将会错误。
也就是说在子列存在时，要禁止母体进行增删，否则数据难以预料。

转数组问题

转数组后，得到的数组是一份拷贝。此时替换掉数组一些位置的数据也不会反映到原始List，但是修改数据还是可以反映的因为是浅拷贝。如果不传参数，返回就是Object类型，Object[]不可以强制转换成其他类型数组。

ArrayList.java

1
2
3

public Object[] toArray() {
    return Arrays.copyOf(elementData, size);
}

可以传入一个数组来告知类型

如果传入的数组容量不够，那么就会生成一个新数组，这样返回的数组和传入的就不是一个
如果传入的数组容量超了，那么剩余的就会置null
最佳方式是传入一个和List一样大小的数组，这样可以避免内存浪费

ArrayList.java

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);
    if (a.length > size)
        a[size] = null;
    return a;
}

一分也是爱~

This site by Linest is licensed under a Creative Commons BY-NC-ND 4.0 International License.
由Linest创作并维护的博客采用创作共用保留署名-非商业-禁止演绎4.0国际许可证。

本文永久链接：http://linest.github.io/2018/05/23/java-arraylist/