avatar

ArrayList相关学习

ArrayList是工作中常用的集合, 基于数组实现, 可以插入空数据, 也支持随机访问.
ArrayList比较适合 get/set操作, 因为 add/remove需要移动数据, 相对来说比较消耗性能.

默认初始长度

1.默认初始长度为 10
2.底层结构为Object[] 数组

private static final int DEFAULT_CAPACITY = 10;

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/**
* 构造一个初始容量为10的空列表
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

添加方法 add()

  1. 向数组中添加元素, 流程如下
/**
* 将指定的元素追加到此列表的末尾.
*/
public boolean add(E e) {
// 扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
// 添加元素
elementData[size++] = e;
return true;
}

2.扩容过程


transient Object[] elementData;

// 扩容
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
// 计算容量, elementData为空 则使用默认容量 10, 指定容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
// 修改次数自增, 并且如果 新的长度-原长度>0 则使用 grow(minCapacity)方法进行扩容
private void ensureExplicitCapacity(int minCapacity) {
modCount++;

// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
  1. 添加元素赋值
    elementData[size++] = e;

扩容流程 grow(minCapacity)

通过扩容流程可以看出扩容过程中, 是将创建一个原数组1.5倍大小的新数组, 同时将数组元素复制到新数组, 所以一般使用中, 尽量指定数组大小, 从而避免数组的复制.

/**
* 增加容量确保能容纳 minCapacity 数量的元素
*/
private void grow(int minCapacity) {
// overflow-conscious code
// 获取当前 elementData 的长度
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);
}

删除 remove 方法

删除过程中使用 System.arraycopy 本地方法, 对数组进行复制, 所以 ArrayList的 新增和删除方法性能不如, LinkList, 但是 get和set方法, 则直接根据索引修改数据, 比较适合对数据进行修改的操作.

/**
* 删除指定位置的元素, 后面的元素将前移
*/
public E remove(int index) {

// 检查索引 否则抛出 IndexOutOfBoundsException(outOfBoundsMsg(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;
}
/**
* System.arraycopy 方法拷贝 删除
*/
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
}
文章作者: liuzhihang
文章链接: https://liuzhihang.com/2018/08/23/arraylist-related-learning.html
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Notes

评论