ArrayList 8 源码剖析
1、简介
- 汇合的底层是Object[] 的数组，外部实现动静扩容
- 在内存中是间断的内存空间、并且依照程序进行存储的，所以在查找某个地位数据是很快的，往两头插入数据是很慢的。
- 容许有空值存在，值也是齐全能够反复的，然而必须是同一类型的值。
- 初始化大小为10，但后续扩容时，波及的数组的复制，所以对系能是一种耗费，如果已知数据量多大的状况下，最好指定汇合的大小。2、实现的接口
（1）RandomAcess接口
容许通用算法在利用于随机或程序拜访列表时扭转其行为以提供良好的性能。（2）Cloneable接口
汇合能够实现接口和数据的克隆。（3）Serializable接口
汇合反对被序列化，能够用于网络传输。3、属性
1、private static final int DEFAULT_CAPACITY = 10; //示意汇合数组的默认大小为10
2、private static final Object[] EMPTY_ELEMENTDATA = {}; // 空数组，当设置大小为0时用
3、private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; //默认空参构造函数应用
4、transient Object[] elementData；数组的值
5、private int size; 以后数组的大小，也就是数组里蕴含的元素的个数4、构造方法
（1）无参构造方法
public ArrayList() {
// 就相当于 elementData = { }
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}（2）指定初始化大小的构造方法
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
// 当初始化大小大于0，则间接赋值
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
//当初始化大小等于0时， == { }
this.elementData = EMPTY_ELEMENTDATA;
} else { //否则参数谬误
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}（3）引入另一个汇合的构造方法
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}5、执行增加操作
（1）一般增加数据
public boolean add(E e) {
//先对以后数组的大小 +1，而后进行判断是否须要扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
//在数组最末地位填充值
elementData[size++] = e;
return true;
}（2）向指定地位增加数据
public void add(int index, E element) {
//这个办法用来判断增加的地位是否越界（正当的地位应该：< size、>0）
rangeCheckForAdd(index);
// 先对以后数组的大小 +1，而后进行判断是否须要扩容
ensureCapacityInternal(size + 1);
// //将index地位之后的数据往后移
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
//挪动完之后 index还是老的值，而后新值间接笼罩
elementData[index] = element;
//长度加1
size++;
}
（3）扩容操作
//办法1：扩容入口
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
//查看以后的数组大小，如果第一次存，则间接返回初始值10
private static int calculateCapacity(Object[] elementData, int minCapacity) {
//判断以后是否是一个空的汇合，第一次数组里还啥也没有，就将默认的10和以后传过来的数（以后数据长度 size + 1）
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
//第一次都返回10
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
//如果以后数组不是空的，间接返回以后数组长度 + 1
return minCapacity;
}
//办法2:
private void ensureExplicitCapacity(int minCapacity) {
modCount++; //对数据的操作次数 + 1
// size 加1 之后的值与数组总长度进行比拟，如果加1之后的数组的个数大于总长度，则须要扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
//办法3：扩容
private void grow(int minCapacity) {
//先获取旧数组的总长度，比方是10
int oldCapacity = elementData.length;
// 新长度 = 旧长度 + 旧长度/2 （即：新的 = 旧的 * 1.5）
int newCapacity = oldCapacity + (oldCapacity >> 1);
//如果扩容1.5倍之后还小于 size + 1的值
if (newCapacity - minCapacity < 0)
//新长度 = size + 1
newCapacity = minCapacity;
//新长度大于Integer.MAX_VALUE - 8么？
if (newCapacity - MAX_ARRAY_SIZE > 0)
//扩容到最大值时（int.Max - 8）时返回int的最大值，示意再也不能扩容了
newCapacity = hugeCapacity(minCapacity);
//创立完新的数组，而后实现数据复制。
elementData = Arrays.copyOf(elementData, newCapacity);
}
通过这个过程你应该了解，在创立list的时候尽可能的指定汇合的大小，防止频繁的扩容。 6、执行删除操作
（1）依据下标删除
public E remove(int index) {
//判断下标是否符合标准
rangeCheck(index);
modCount++;
// 获取到旧值，删除胜利后返回
E oldValue = elementData(index);
//获取须要挪动的元素的个数（数组元素个数 - 以后地位）
int numMoved = size - index - 1;
if (numMoved > 0)
//将以后地位往后的一位数到数组的最初一位数对立往前挪动一位，那以后地位的元素就被index +1的元素笼罩掉了。
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// 将数组最初一地位空
elementData[--size] = null;
return oldValue;
}
留神：这个操作没有遍历数组所以复杂度是o(1（2）依据内容删除
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;
}
}
//如果值不存在间接返回false
return false;
}（3）fastRemove(index)
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
//将以后地位往后的一位数到数组的最初一位数对立往前挪动一位，那以后地位的元素就被index +1的元素笼罩掉了。
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
}（4）在循环遍历删除
List<Integer> list = new ArrayList<>();
list.add(3);
list.add(5);
list.add(9);
list.add(0,999);
System.out.println(list);
for (Integer num : list){
if(num == 9){
list.remove(num); //会报错：java.util.ConcurrentModificationException
}
}
Result：下面这个代码报错的起因是因为在遍历之前就曾经把以后汇合的操作数赋值给一个预期操作数的变量，执行remove之前会把以后的操作指令数 + 1，而后以后操作数会跟预期操作数进行比拟，如果不统一就会报上述谬误，总而言之就是在扭转汇合之前先对以后操作数进行批改了。
So：怎么正确删除汇合的元素呢？
List<Integer> list = new ArrayList<>();
list.add(3);
list.add(5);
list.add(9);
list.add(0,999);
System.out.println(list);
// 先将汇合变成iterator
Iterator<Integer> iterator = list.iterator();
while(iterator.hasNext()){
Integer num = iterator.next();
if(num == 5){
iterator.remove();
}
}
System.out.println(list);7 查问操作
public E get(int index) {
//查看index大小是够正当 （0<= x <= size）
rangeCheck(index);
//注解返回 elementData[index]的值
return elementData(index);
}8 汇合清空
public void clear() {
modCount++;
//循环删除所有元素
for (int i = 0; i < size; i++)
elementData[i] = null;
//长度置为0
size = 0;
}
//这里数组的总长度没有变总结面试题：
1、ArrayList的初始化大小事几？
答：102、ArrayList扩容后的长度是多少？
答：原来长度的1.5倍3、ArrayList增加和查找元素的工夫复杂度是多少？
答：都是O(1)4、ArrayList是线程平安的么？会有什么问题？有线程平安的List吗？
答：不是线程平安的的，会有很多问题，比方反复赋值、反复扩容等，线程平安的List有Vector 、 CopyOnWriteArrayList 。5、ArrrayList和LinkedList有什么区别？
答：（1）构造不同，ArrayList底层是基于数组实现的，所以在内存中数据存储是间断的。而LinkedList底层是基于链表实现的，所以内存中的数据可能是间断的也可能是不间断的。
（2）场景不同，ArrayList因为是内存间断的数组，所以它反对随机拜访，当咱们须要拜访某个地位的数据时，ArrayList可间接获取，LinkedList则须要遍历链表获取，在这个过程中寻址是很慢的。当须要向两头地位新增某一个值的时候，因为ArrayList是间断的内存则须要将所增加地位之后的所有元素后移，留出一个地位来寄存增加元素，而LinkedList链表只须要批改增加地位的元素的前后指针就能够了，删除和批改相似。所以对于随机拜访ArrayList效果显著，当增删改时，LinkedList的效果显著。
注：增删改时ArrayList到底比LinkedList慢多少，这个得看电脑配置。我用MacBookPro 17款 4核 16G内存的电脑，在200万长度之前是一样的，前面开始越多越慢，在300万和3000万时对5001地位新增，ArrayList别离慢1ms 和 10ms.
发表回复