前言
ArrayList:初始长度：10，扩容原来度的1.5倍，obejct动态数组，数据的特点就是查询数据快。只要不在末尾添加或删除元素，那么元素的位置都要进行移动，详情看之后的分析
ArrayList: add(E e)
public boolean add(E e) {
//检查添加数据是否需要扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
/**
* size++;
* elementData[size]=e;
*/
elementData[size++] = e;
return true;
}
下面把扩容的逻辑代码贴出来分析
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
private static final int DEFAULT_CAPACITY = 10;
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
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);
// 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;
}
在ensureCapacityInternal()里面先判断elementData的值是否等于 DEFAULTCAPACITY_EMPTY_ELEMENTDATA，如果等于minCapacity =10,
否则等于传进来的值,再进ensureExplicitCapacity()，判断minCapacity 是否大于elementData.length,如果大于调用grow()进行扩容操作。
假设elementData的长度为10，已经填满了数据，现在再添加一个数据,一直走到grow方法中，oldCapacity =10，newCapacity =15。15-10>0，第一个if不用走，第二个也不用走了，利用Arrays.copyOf()方法进行数组扩容。
newCapacity =15？怎么算
>>右移运算符：凡位运算符都是把值先转换成二进制再进行后续的处理，10的二进制是1010，在计算机中是0000 1010，高位补零。二进制用短除法操作
image.png
下面用int[] 演示一下添加元素扩容的操作，int[] 的默认值位0
private static int[] sourceArray={1,2,3,4,5,6,7,8,9,10};
public static void main(String[] args){
int index=10;
int size=sourceArray.length;
//多余判断只是为了更好的理解
if(size==sourceArray.length){
int oldLength=sourceArray.length;
int newLength=oldLength+(oldLength >> 1);
sourceArray=Arrays.copyOf(sourceArray,newLength);
}
//也可以这样写
// if(size==sourceArray.length){
// int oldLength=sourceArray.length;
// int newLength=oldLength+(oldLength >> 1);
// int[] newInt= new int[newLength];
// for (int i = 0; i < oldLength; i++) {
// newInt[i]=sourceArray[i];
// }
// sourceArray=newInt;
// }
sourceArray[size++]=11;
for (int i = 0; i <sourceArray.length; i++) {
System.out.print(sourceArray[i]+",");
}
System.out.println("sourceArray的长度："+sourceArray.length);
}
打印的值：1,2,3,4,5,6,7,8,9,10,11,0,0,0,0,sourceArray的长度：15
ArrayList:add(int index, E element), addAll(Collection<? extends E> c)这两个差不多，分析add(int index, E element)就ok了
public void add(int index, E element) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
//判断数组需要扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
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;
}
下面用int[] 演示一下add(int index, E element)的操作，int[] 的默认值位0，
int[] sourceArray={1,2,3,4,5,6,7,8,9,10};经过System.arraycopy()操作之后变成
sourceArray={1,2,3,4,5,6,6,7,8,9,10,0,0,0,0} [index,index]
private static int[] sourceArray={1,2,3,4,5,6,7,8,9,10};
public static void main(String[] args){
int index=5;
int size=sourceArray.length;
//多余判断只是为了更好的理解
if(size==sourceArray.length){
int oldLength=sourceArray.length;
int newLength=oldLength+(oldLength >> 1);
sourceArray=Arrays.copyOf(sourceArray,newLength);
}
System.arraycopy(sourceArray,index,sourceArray,index+1,size-index);
sourceArray[index]=15;
size++;
for (int i = 0; i <sourceArray.length; i++) {
System.out.print(sourceArray[i]+",");
}
System.out.println("sourceArray的长度："+sourceArray.length);
}
删除元素和添加元素都是一样的原理，基本没有太大差别。还有在删除元素中它并没有进行一个缩容的操作，在ArrayList源码中trimToSize() 并没有调用过这个方法
/**
* Trims the capacity of this <tt>ArrayList</tt> instance to be the
* list's current size. An application can use this operation to minimize
* the storage of an <tt>ArrayList</tt> instance.
*/
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
