如果现在还不懂ArrayList的原理,赶快收藏这篇文章
2020-07-13 本文已影响0人
小燃儿
01 原理
ArrayList底层采用数组实现,具有也具有数组的优缺点,同时支持动态扩容(扩展为原来的1.5倍)。所以它非常适合需要使用索引快速访问的场景。同时由于其自动扩容的功能,我们需要注意在初始化集合时需要指定大小。
02 特点
- 具有连续的内存空间,支持随机访问:
- 修改操作性能好:
- 插入操作性能差(插入位置不在末尾时,需要内存复制):
- 删除性能差(删除位置不在末尾时,需要内存复制)。在实际应用中为了提 高删除性能,有时候会先标记数据数字删除(会造成内存碎片多),到了内 存不够的时候再去真正删除数据,并进行内存复制,如GC中标记-整理算 法。具体流程如下(也可以先进行内存复制,再删除最后一位数据):
03 具体代码
最后从源码里具体分析一下,ArrayList中的添加(add),随机访问(get),删除(remove),插入(add),扩容操作(grow)。
添加(add)****:
public boolean add(E e) {
ensureCapacityInternal(size + 1); // 确保数组容量足够,否则进行扩容grow
elementData[size++] =e;// 为数组[size]赋值,当前数据长度+1 return true;}
随机访问(get):
public E get(int index) {
rangeCheck(index); //检查数组下标值是否超过list实际含有的数据量
return elementData(index);// 随机访问数组
}
删除(remove):
public E remove(int index) {
rangeCheck(index);//检查数组下标值是否超过list实际含有的数据量
modCount++;// 迭代遍历时,用于确定list是否被操作过了
E oldValue =elementData(index);//旧值
int numMoved = size - index - 1; i
f (numMoved > 0) // 删除的位置不是末尾数据,进行数组的复制
System.arraycopy(elementData,index+1, elementData, index, numMoved);
elementData[--size] =null; //删除了一个值,所以原来的数组最后一位数据为null
return oldValue;
}
插入(add):
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!grow
System.arraycopy(elementData, index,elementData, index + 1, size- index); //复制数组
elementData[index] =element;// 插入数据
size++;
}
扩容(grow):
private void grow(int minCapacity) { // overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity =oldCapacity + (oldCapacity >> 1);//新容量原来的1.5倍
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE >0)
newCapacity =hugeCapacity(minCapacity); // minCapacity is usually close tosize, so this is a win:
elementData =Arrays.copyOf(elementData, newCapacity);// 原来的数据复制到扩容后的数组中 }