ArrayList源码解析

2018-04-15  本文已影响3人  谢朴欢

1. 简介

List是一种支持插入、删除、查找，元素可重复，可为null的数据结构，在JDK中有不同的实现类，其中ArrayList基于数组实现，支持随机访问，非线程安全，插入与删除时间复杂度为O(n)。

2. 实现

ArrayList内部是使用数组来实现的，所以可以做到随机访问时间为O(1)，如果不一开始设置好最终的大小，可能在不断添加元素的过程中多次扩容而导致效率问题。

属性

//默认容量
private static final int DEFAULT_CAPACITY = 10;

private static final Object[] EMPTY_ELEMENTDATA = {};
//数组最大大小
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

//元素存放的数组，设置为transient的目的是序列化对象时忽略该数组，因为数组可能不是存满的，我们只序列化必要的对象以节省空间时间。
transient Object[] elementData; // non-private to simplify nested class access
//已经添加的元素数量
private int size;

构造函数

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

// 如果未给出大小，默认大小是数组大小10，只不过这个大小为10的数组是延迟到添加元素创建的，所以这里
// 一开始数组大小是0。
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

扩容函数

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

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    // 新数组的大小为旧数组的1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    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);
}

增删改查方法

// 获取指定位置上的元素
public E get(int index) {
        //范围检查，index超出范围抛出异常
        rangeCheck(index);
        return elementData(index);
}

// 修改指定位置上的元素并返回旧元素
public E set(int index, E element) {
    rangeCheck(index);

    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

// 添加元素到列表尾部
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++;
}

// 移除指定位置上的元素并返回其值
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;
}

// 若存在对象o则移除
public boolean remove(Object o) {
        if (o == null) {
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true;
                }
        } else {
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }

// 清空所有对象
public void clear() {
    modCount++;

    // clear to let GC do its work
    for (int i = 0; i < size; i++)
        elementData[i] = null;

    size = 0;
}

toArray方法

// 复制出一个具有原数组所有元素的新数组
public Object[] toArray() {
    return Arrays.copyOf(elementData, size);
}

subList方法

创建出一个子List，对该List的操作将作用于到原List上

public List<E> subList(int fromIndex, int toIndex) {
    // 检查索引范围是否合法
    subListRangeCheck(fromIndex, toIndex, size);
    return new SubList(this, 0, fromIndex, toIndex);
}

sort方法

List接口中存在默认的sort方法，只不过该方法是为LinkedList非基于数组实现的List准备的，所以ArrayList重写了sort方法，通过调用Arrays.sort()方法直接对数组进行排序效率比默认的高。

public void sort(Comparator<? super E> c) {
    final int expectedModCount = modCount;
    Arrays.sort((E[]) elementData, 0, size, c);
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
    modCount++;
}

3. 适用场景

上一篇 下一篇

猜你喜欢

热点阅读