五道ArrayList⾯试题
ArrayList概述
（1）ArrayList是⼀种变长的集合类，基于定长数组实现。
（2）ArrayList允许空值和重复元素，当往 ArrayList 中添加的元素数量⼤于其底层数组容量时，其会通过扩容机制重新⽣成⼀个更⼤的数组。
（3）ArrayList底层基于数组实现，所以其可以保证在O(1)复杂度下完成随机查找操作。
（4）ArrayList是⾮线程安全类，并发环境下，多个线程同时操作 ArrayList，会引发不可预知的异常或错误。
ArrayList的成员属性
在介绍关于ArrayList的各种⽅法之前先看⼀下基础属性成员。其中DEFAULTCAPACITY_EMPTY_ELEMENTDATA与EMPTY_ELEMENTDATA的区别是：当我们向数组中添加第⼀个元素时，DEFAULTCAPACITY_EMPTY_ELEMENTDATA将会知道数组该扩充多少。
//默认初始化容量
private static final int DEFAULT_CAPACITY = 10;
//默认的空的数组，这个主要是在构造⽅法初始化⼀个空数组的时候使⽤
private static final Object[] EMPTY_ELEMENTDATA = {};
//使⽤默认size⼤⼩的空数组实例，和EMPTY_ELEMENTDATA区分开来，
//这样可以知道当第⼀个元素添加的时候进⾏扩容⾄多少
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//ArrayList底层存储数据就是通过数组的形式，ArrayList长度就是数组的长度。
//⼀个空的实例elementData为上⾯的DEFAULTCAPACITY_EMPTY_ELEMENTDATA，当添加第⼀个元素的时候
//会进⾏扩容，扩容⼤⼩就是上⾯的默认容量DEFAULT_CAPACITY
transient Object[] elementData; // non-private to simplify nested class access
//arrayList的⼤⼩
private int size;
static修饰的EMPTY_ELEMENTDATA和DEFAULTCAPACITY_EMPTY_ELEMENTDATA
ArrayList构造⽅法
（1）带有初始化容量的构造⽅法
参数⼤于0，elementData初始化为initialCapacity⼤⼩的数组
参数⼩于0，elementData初始化为空数组
参数⼩于0，抛出异常
//参数为初始化容量
public ArrayList(int initialCapacity) {
//判断容量的合法性
if (initialCapacity > 0) {
//elementData才是实际存放元素的数组
this.elementData = new Object[initialCapacity];
} el if (initialCapacity == 0) {
//如果传递的长度为0，就是直接使⽤⾃⼰已经定义的成员变量(⼀个空数组)
this.elementData = EMPTY_ELEMENTDATA;
} el {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
（2）⽆参构造
构造⽅法中将elementData初始化为空数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA
当调⽤add⽅法添加第⼀个元素的时候，会进⾏扩容
扩容⾄⼤⼩为DEFAULT_CAPACITY=10
//⽆参构造，使⽤默认的size为10的空数组，在构造⽅法中没有对数组长度进⾏设置，会在后续调⽤add⽅法的时候进⾏扩容
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
（3）参数为Collection类型的构造器
//将⼀个参数为Collection的集合转变为ArrayList（实际上就是将集合中的元素换为了数组的形式）。如果
//传⼊的集合为null会抛出空指针异常（调⽤c.toArray()⽅法的时候）
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
//c.toArray()可能不会正确地返回⼀个 Object[]数组，那么使⽤pyOf()⽅法
if (Class() != Object[].class)
elementData = pyOf(elementData, size, Object[].class);
} el {
//如果集合转换为数组之后数组长度为0，就直接使⽤⾃⼰的空成员变量初始化elementData
this.elementData = EMPTY_ELEMENTDATA;
}
}
上⾯的这些构造⽅法理解起来⽐较简单，关注前两个构造⽅法做的事情，⽬的都是初始化底层数组 elementData(this.elementData=XXX)。区别在于⽆参构造⽅法会将elementData 初始化⼀个空数组，插⼊元素时，扩容将会按默认值重新初始化数组。⽽有参的构造⽅法则会将 elementData 初始化为参数值⼤⼩（>= 0）的数组。⼀般情况下，我们⽤默认的构造⽅法即可。倘若在可知道将会向 ArrayList 插⼊多少元素的情况下，可以使⽤有参构造⽅法。
上⾯说到了使⽤⽆参构造的时候，在调⽤add⽅法的时候会进⾏扩容，所以下⾯我们就看看add⽅法以及扩容的细节
ArrayList的add⽅法
add⽅法⼤致流程
//将指定元素添加到list的末尾
public boolean add(E e) {
//因为要添加元素，所以添加之后可能导致容量不够，所以需要在添加之前进⾏判断（扩容）
ensureCapacityInternal(size + 1); // Increments modCount!!（待会会介绍到fast-fail）
elementData[size++] = e;
return true;
}
我们看到add⽅法中在添加元素之前，会先判断size的⼤⼩，所以我们来看看ensureCapacityInternal⽅法的细节
ensureCapacityInternal⽅法分析
private void ensureCapacityInternal(int minCapacity) {
//这⾥就是判断elementData数组是不是为空数组
//（使⽤的⽆参构造的时候，elementData=DEFAULTCAPACITY_EMPTY_ELEMENTDATA）
//如果是，那么⽐较size+1(第⼀次调⽤add的时候size+1=1)和DEFAULT_CAPACITY，
//那么显然容量为10
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
当中国篮球队员
要 add 进第1个元素时，minCapacity为(size+1=0+1=)1，在Math.max()⽅法⽐较后，minCapacity 为10。然后紧接着调⽤ensureExplicitCapacity更新modCount的值，并判断是否需要扩容
ensureExplicitCapacity⽅法分析
private void ensureExplicitCapacity(int minCapacity) {
modCount++; //这⾥就是add⽅法中注释的Increments modCount
//溢出
if (minCapacity - elementData.length > 0)
grow(minCapacity);//这⾥就是执⾏扩容的⽅法
}
下⾯来看⼀下扩容的主要⽅法grow。
grow⽅法分析
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private void grow(int minCapacity) {
// oldCapacity为旧数组的容量
int oldCapacity = elementData.length;
// newCapacity为新数组的容量（oldCap+oldCap/2：即更新为旧容量的1.5倍）
int newCapacity = oldCapacity + (oldCapacity >五险一金指什么意思
> 1);
// 检查新容量的⼤⼩是否⼩于最⼩需要容量，如果⼩于那旧将最⼩容量最为数组的新容量
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//如果新容量⼤于MAX_ARRAY_SIZE，使⽤hugeCapacity⽐较⼆者
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually clo to size, so this is a win:
// 将原数组中的元素拷贝
elementData = pyOf(elementData, newCapacity);
}
hugeCapacity⽅法
这⾥简单看⼀下hugeCapacity⽅法
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
//对minCapacity和MAX_ARRAY_SIZE进⾏⽐较
//若minCapacity⼤，将Integer.MAX_VALUE作为新数组的⼤⼩
//若MAX_ARRAY_SIZE⼤，将MAX_ARRAY_SIZE作为新数组的⼤⼩
//MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}
add⽅法执⾏流程总结
我们⽤⼀幅图来简单梳理⼀下，当使⽤⽆参构造的时候，在第⼀次调⽤add⽅法之后的执⾏流程
这是第⼀次调⽤add⽅法的过程，当扩容值capacity为10之后，
继续添加第2个元素（先注意调⽤ensureCapacityInternal⽅法传递的参数为size+1=1+1=2）
在ensureCapacityInternal⽅法中，elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA不成⽴，所以直接执⾏ensureExplicitCapacity⽅法
ensureExplicitCapacity⽅法中minCapacity为刚刚传递的2，所以第⼆个if判断（2-10=-8）不会成⽴，即newCapacity 不⽐ MAX_ARRAY_SIZE⼤，则不会进⼊grow⽅法。数组容量为10，add⽅法中 return true,size增为1。
假设⼜添加3、4......10个元素（其中过程类似，但是不会执⾏grow扩容⽅法）
当add第11个元素时候，会进⼊grow⽅法时，计算newCapacity为15，⽐minCapacity（为10+1=11）⼤，第⼀个if判断不成⽴。新容量没有⼤于数组最⼤size，不会进⼊hugeCapacity⽅法。数组容量扩为15，add⽅法中return true,size增为11。
add(int index,E element)⽅法
//在元素序列 index 位置处插⼊
public void add(int index, E element) {
rangeCheckForAdd(index); //校验传递的index参数是不是合法
// 1. 检测是否需要扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
// 2.梨子的营养价值
将 index 及其之后的所有元素都向后移⼀位
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
// 3. 将新元素插⼊⾄ index 处
elementData[index] = element;
size++;
}
private void rangeCheckForAdd(int index) {
if (index > size || index < 0) //这⾥判断的index>size（保证数组的连续性），index⼩于0
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
add(int index, E element)⽅法（在元素序列指定位置（假设该位置合理）插⼊）的过程⼤概是下⾯这些
1. 检测数组是否有⾜够的空间(这⾥的实现和上⾯的)
2. 将 index 及其之后的所有元素向后移⼀位
3. 将新元素插⼊⾄ index 处.
将新元素插⼊⾄序列指定位置，需要先将该位置及其之后的元素都向后移动⼀位，为新元素腾出位置。这个操作的时间复杂度为O(N)，频繁移动元素可能会导致效率问题，特别是集合中元素数量较多时。在⽇常开发中，若⾮所需，我们应当尽量避免在⼤集合中调⽤第⼆个插⼊⽅法。
ArrayList的remove⽅法
ArrayList⽀持两种删除元素的⽅式
1、remove(int index) 按照下标删除
public E remove(int index) {
rangeCheck(index); //校验下标是否合法（如果index>size，旧抛出IndexOutOfBoundsException异常）
modCount++;//修改list结构，就需要更新这个值
E oldValue = elementData(index); //直接在数组中查找这个值
int numMoved = size - index - 1;//这⾥计算所需要移动的数⽬
//如果这个值⼤于0 说明后续有元素需要左移(size=index+1)
//如果是0说明被移除的对象就是最后⼀位元素(不需要移动别的元素)
if (numMoved > 0)
//索引index只有的所有元素左移⼀位覆盖掉index位置上的元素
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//移动之后，原数组中size位置null
elementData[--size] = null; // clear to let GC do its work
//返回旧值
return oldValue;
}
//src：源数组
//srcPos：从源数组的srcPos位置处开始移动
//dest:⽬标数组
/
/desPos：源数组的srcPos位置处开始移动的元素，这些元素从⽬标数组的desPos处开始填充
//length：移动源数组的长度
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);
删除过程如下图所⽰
2、remove(Object o) 按照元素删除，会删除和参数匹配的第⼀个元素
public boolean remove(Object o) {
//如果元素是null 遍历数组移除第⼀个null
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
//遍历找到第⼀个null元素的下标调⽤下标移除元素的⽅法
fastRemove(index);
return true;
}
} el {
/
/找到元素对应的下标调⽤下标移除元素的⽅法
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return fal;
}
//按照下标移除元素（通过数组元素的位置移动来达到删除的效果）
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
}
ArrayList三本大学排名
的其他⽅法
ensureCapacity⽅法
最好在 add ⼤量元素之前⽤ ensureCapacity ⽅法，以减少增量从新分配的次数
public void ensureCapacity(int minCapacity) {
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
// any size if not default element table
? 0
// larger than default for default empty table. It's already
// suppod to be at default size.
: DEFAULT_CAPACITY;
if (minCapacity > minExpand) {
ensureExpl79年属什么
icitCapacity(minCapacity);
}
}
ArrayList总结
（1）ArrayList是⼀种变长的集合类，基于定长数组实现，使⽤默认构造⽅法初始化出来的容量是10（1.7之后都是延迟初始化，即第⼀次调⽤add⽅法添加元素的时候才将elementData容量初始化为10）。
（2）ArrayList允许空值和重复元素，当往 ArrayList 中添加的元素数量⼤于其底层数组容量时，其会通过扩容机制重新⽣成⼀个更⼤的数组。ArrayList扩容的长度是原长度的1.5倍
（3）由于ArrayList底层基于数组实现，所以其可以保证在O(1)复杂度下完成随机查找操作。
（4）ArrayList是⾮线程安全类，并发环境下，多个线程同时操作 ArrayList，会引发不可预知的异常或错误。
（5）顺序添加很⽅便
（6）删除和插⼊需要复制数组，性能差（可以使⽤LinkindList）
（7）Integer.MAX_VALUE - 8 ：主要是考虑到推销话术
不同的JVM，有的JVM会在加⼊⼀些数据头，当扩容后的容量⼤于MAX_ARRAY_SIZE，我们会去⽐较最⼩需要容量和
MAX_ARRAY_SIZE做⽐较，如果⽐它⼤, 只能取Integer.MAX_VALUE，否则是Integer.MAX_VALUE -8。这个是从jdk1.7开始才有的
fast-fail机制
fail-fast的解释：
In systems design, a fail-fast system is one which immediately reports at its interface any condition that is likely to indicate a failure. Fail-fast syste党的成就
ms are usually designed to stop normal operation rather than attempt to continue a possibly flawed process. Such designs often check the system’s state at veral points in an operation, so any failures can be detected early. The responsibility of a fail-fast module is detecting errors, then letting the next-highest level of the system
handle them.
⼤概意思是：在系统设计中，快速失效系统⼀种可以⽴即报告任何可能表明故障的情况的系统。快速失效系统通常设计⽤于停⽌正常操作，⽽不是试图继续可能存在缺陷的过程。这种设计通常会在操作中的多个点检查系统的状态，因此可以及早检测到任何故障。快速失败模块的职责是检测错误，然后让系统的下⼀个最⾼级别处理错误。
其实就是在做系统设计的时候先考虑异常情况，⼀旦发⽣异常，直接停⽌并上报，⽐如下⾯的这个简单的例⼦
/
/这⾥的代码是⼀个对两个整数做除法的⽅法，在f最初的英文
ast_fail_method⽅法中，我们对被除数做了个简单的检查，如果其值为0，那么就直接抛出⼀个异常，并明确提⽰异常原因。这其实就是fail-fast理念的实际应⽤。public int fast_fail_method(int arg1,int arg2){
if(arg2 == 0){
throw new RuntimeException("can't be zero");
}
return arg1/arg2;
}
在Java集合类中很多地⽅都⽤到了该机制进⾏设计，⼀旦使⽤不当，触发fail-fast机制设计的代码，就会发⽣⾮预期情况。我们通常说的Java中的fail-fast机制，默认指的是Java集合的⼀种错误检测机制。当多个线程对部分集合进⾏结构上的改变的操作时，有可能会触发该机制时，之后就会抛出并发修改异常ConcurrentModificationException.当然如果不在多线程环境下，如果在foreach遍历的时候使⽤add/remove⽅法，也可能会抛出该异常。参考，这⾥简单做个总结
之所以会抛出ConcurrentModificationException异常，是因为我们的代码中使⽤了增强for循环，⽽在增强for循环中，集合遍历是通过iterator进⾏的，但是元素的add/remove却是直接使⽤的集合类⾃⼰的⽅法。这就导致iterator在遍历的时候，会发现灶王经全文
有⼀个元素在⾃⼰不知不觉的情况下就被删除/添加了，就会抛出⼀个异常，⽤来提⽰可能发⽣了并发修改！所以，在使⽤Java的集合类的时候，如果发⽣ConcurrentModificationException，优先考虑fail-fast有关的情况，实际上这可能并没有真的发⽣并发，只是Iterator使⽤了fail-fast的保护机制，只要他发现有某⼀次修改是未经过⾃⼰进⾏的，那么就会抛出异常。
