ArrayList 源码分析

ArrayList 简介三种构造方式自增的实现方式查找的实现方式contains(Object o), indexOf(Object o), lastIndexOf() 删除两种remove私有fastRemoveremoveRange(int fromIndex, int toIndex) 图片来自： http://blog.csdn.net/bondsui/article/details/8520078

ArrayList 简介

可变长数组，非线程安全。由于增加或者删除需要array.copyOf 复制数组，不适合需要频繁增删的数据类型。

三种构造方式

无initialCapacity：ArrayList();有initialCapacity：ArrayList(10);有collection：ArrayList(Collection<? extends E> c);

自增的实现方式

ArrayList 有两个add方法，可在array下一位加入，或者在指定index加入。选择第二种方式，ArrayList 会先检测一下index是否为负数或者大于当前size。而自动变长，则由grow()方法完成。

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

calculateCapacity(elementData, size+1), 如果向空array添加数据，返回DEFAULT_CAPACITY 默认为10，否则返回已有size+1；

private static int calculateCapacity(Object[] elementData, int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { return Math.max(DEFAULT_CAPACITY, minCapacity); } return minCapacity; } private void ensureCapacityInternal(int minCapacity) { ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); }

ensureExplicitCapacity() 调用grow 实现增长

private void ensureExplicitCapacity(int minCapacity) { modCount++; // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity); }

新长度为原有长度+原有长度的一半。如果超过最大值，调用hugeCapacity设为Integer最大值。

private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; 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); }

查找的实现方式

contains(Object o), indexOf(Object o), lastIndexOf()

contains 实际上调用indexOf实现遍历，但是返回boolean类型，而indexOf 返回int。 由于java中null既不是对象也不是一种类型。对于null的比较如果使用equals() 会造成空指针异常，因此需要分成null以及非null两种情况进行比较。lastIndexOf() 与indexOf() 类似，从后向前遍历。

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

addAll() 两种实现方式，均用arraycopy进行数组的复制

public boolean addAll(Collection<? extends E> c) { Object[] a = c.toArray(); int numNew = a.length; ensureCapacityInternal(size + numNew); // Increments modCount System.arraycopy(a, 0, elementData, size, numNew); size += numNew; return numNew != 0; } public boolean addAll(int index, Collection<? extends E> c) { rangeCheckForAdd(index); Object[] a = c.toArray(); int numNew = a.length; ensureCapacityInternal(size + numNew); // Increments modCount int numMoved = size - index; if (numMoved > 0) System.arraycopy(elementData, index, elementData, index + numNew, numMoved); System.arraycopy(a, 0, elementData, index, numNew); size += numNew; return numNew != 0; }

删除

两种remove

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

私有fastRemove

内部调用，不检测或返回 index

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 }

removeRange(int fromIndex, int toIndex)

删除指定index内的数据

protected void removeRange(int fromIndex, int toIndex) { modCount++; int numMoved = size - toIndex; System.arraycopy(elementData, toIndex, elementData, fromIndex, numMoved); // clear to let GC do its work int newSize = size - (toIndex-fromIndex); for (int i = newSize; i < size; i++) { elementData[i] = null; } size = newSize; }