ArrayList 底层实现原理
// 集合内部存储结构
transient Object[] elementData; // non-private to simplify nested class access
// 集合大小
private int 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 {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
// 提供初始化集合构造ArrayList
public ArrayList(Collection<? extends E> c) {
// 将集合转换成数组，并赋值给elementData数组
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// 如果c.toArray返回的不是Object[]类型的数组，转换成Object[]类型
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
// 集合默认容量
private static final int DEFAULT_CAPACITY = 10;
// 实例化一个空的对象
private static final Object[] EMPTY_ELEMENTDATA = {};
// 无参构造方法会将其设置给集合底层数据结构
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
public boolean add(E e) {
// 插入元素之前判断是否需要扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
// 表示调用默认构造函数初始化，并且是第一次插入元素
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// 集合大小+1 与默认值10 比较去大的值
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;
// 每次扩容大小为上一次集合大小的一半
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 扩容后进行数据的拷贝
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;
}
public void add(int index, E element) {
// 确保插入的位置合法
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
// index 后面所有元都需要进行后移一位
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));
}
// 按照索引删除元素
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) {
// 删除元素 null 与非 null 的区别是比较方法，非null 元素使用equals进行比较
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) {
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
}
删除集合操作
// 移除集合中的元素
public boolean removeAll(Collection<?> c) {
// 非空校验
Objects.requireNonNull(c);
// 批量删除元素
return batchRemove(c, false);
}
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++)
// 待删除集合是否不包含指定元素，complement为false
if (c.contains(elementData[r]) == complement)
// 将不包含在待删除集合中的元素移动到集合的前面
elementData[w++] = elementData[r];
} finally {
// 如果删除的元素过程中抛出了异常，则r与size不相同的
if (r != size) {
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
// 如果删除集合中非空，且上面已经正确删除了，则需要将删除的引用赋值为null
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;
}
// 获取指定索引的值
public E get(int index) {
// 校验索引正确性
rangeCheck(index);
return elementData(index);
}
// 设置指定索引的值
public E set(int index, E element) {
// 校验索引正确性
rangeCheck(index);
// 获取指定索引值
E oldValue = elementData(index);
// 替换指定索引的值并返回旧值
elementData[index] = element;
return oldValue;
}
List<String> list = new ArrayList<>() ;
//第一种
for (int i = 0; i < list.size(); i++) {
list.get(i);
}
//第二种
for (Iterator iter = list.iterator(); iter.hasNext(); ) {
iter.next();
}
//第三种
for (Object obj : list)
;
//第四种 ， 只支持JDK1.8+
list.forEach(
e->{
;
}
);
// 从前往后找，找到则返回下标否则返回-1
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;
}
/**
* 拷贝数组
* @param {[type]} U[] original 源数组
* @param {[type]} int newLength 新数组的大小
* @param {[type]} Class<? extends T[]> newType 新数组的类型
* @return {[type]} [description]
*/
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
// 判断新数组类型是否是Object[]否则反射创建正确的数组对象
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
// 调用本地的数组拷贝方法，使用底层C++实现
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
// 返回拷贝后的数组
return copy;
}
// 本地的数组拷贝方法，使用底层C++实现
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);