[游戏开发]ArrayList源码分析

ArrayList是一种动态可扩展数组，初始容量为10，每次扩容为原来的1.5倍，当然可能是1.5倍与实际需要的最大值

elementData用来存放实际的数据，size记录数组的大小。

源码分析

构造函数

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 {
        // initialCapacity < 0，异常
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

// 入参为集合类
public ArrayList(Collection<? extends E> c) {
    // 转换为数组
    elementData = c.toArray();
    // 长度大于0，判断数组类型是否为Object[],不是就住那换
    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 {
        // 等于0，则赋值空数组
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

add方法

public boolean add(E e) {
    // 确保容量是否足够，不够就扩容
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 插入最后一个位置，并自增size
    elementData[size++] = e;
    return true;
}

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

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    // 当前数组是空膨胀数组，则取10和minCapacity的最大值，否则取minCapacity
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

private void ensureExplicitCapacity(int minCapacity) {
    // 修改次数+1
    modCount++;

    // overflow-conscious code
    // 需要的容量与当前大小对比
    if (minCapacity - elementData.length > 0)
        // 需要扩容
        grow(minCapacity);
}

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    // 相对于1.5*oldCapacity ，扩大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);
}

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
    MAX_ARRAY_SIZE;
}

add(int index, E element)方法

public void add(int index, E element) {
    // 校验index是否符合范围
    rangeCheckForAdd(index);
	// 判断是否扩容
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 调用Native方法进行拷贝
    
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}

private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

/**
* @param      src      the source array. 源数组
* @param      srcPos   starting position in the source array. 源数组中的起始位置
* @param      dest     the destination array.目标数组
* @param      destPos  starting position in the destination data. 目标数据中的起始位置
* @param      length   the number of array elements to be copied.要复制的数组元素的数量
*/
public static native void arraycopy(Object src,  int  srcPos,Object dest, int destPos,int length);

set方法

public E set(int index, E element) {
    // 校验是否溢出，index>=size?  size可能大于数组的长度
    rangeCheck(index);
	//  下标获取值
    E oldValue = elementData(index);
    // 覆盖旧值
    elementData[index] = element;
    return oldValue;
}

get方法

public E get(int index) {
    // 校验是否溢出，index>=size?  size可能大于数组的长度
    rangeCheck(index);

    return elementData(index);
}

remove方法

public E remove(int index) {
    // 校验是否溢出，index>=size?  size可能大于数组的长度
    rangeCheck(index);
    modCount++;
    
    E oldValue = elementData(index);
	// 获取需要移动的元素个数
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    // 将最后一个元素置为null，size-1
    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);
                return true;
            }
    } else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}

private void fastRemove(int index) {
    	//跟remove(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
    }

总结

ArrayList虽然结构相对简单，但是因为其是线程不安全的，容易造成并发问题。具体可以拿add方法进行多线程运算，容易出问题。因为可以使用以下方法去替代ArrayList。

1. 使用Vector，大部分方法都加上了synchronized

2. 使用CopyOnWriteArrayList（读写分离，原理是读正常读，写的时候使用ReentrantLock手动加锁，弄个数组副本，修改完成后替换）

   

3. 使用List synchronizedList = Collections.synchronizedList(list)。通过synchronized对信号量进行加解锁。