ArrayList是Java集合框架中的一个重要的类，它继承于AbstractList，实现了List接口，是一个长度可变的集合，提供了增删改查的功能。集合中允许null的存在。ArrayList类还是实现了RandomAccess接口，可以对元素进行快速访问。实现了Serializable接口，说明ArrayList可以被序列化，还有Cloneable接口，可以被复制。和Vector不同的是，ArrayList不是线程安全的。
public class ArrayList extends AbstractList
implements List, RandomAccess, Cloneable, java.io.Serializable 为了对应不同的构造函数，ArrayList使用了不同的数组：
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};构造函数的目的就是初始化底层数组 elementData，根据构造函数有参无参，有参再分情况讨论，初始化底层数组。
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}插入 *** 作分为两种情况：一种是在元素序列尾部插入，另一种是在元素序列其他位置插入。
public boolean add(E e) {
//检测是否需要扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
//将 index 及其之后的所有元素都向后移一位
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}根据上面的add方法，可以接着看ArrayList的扩容机制。
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
//获取最小扩容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
扩容机制的思路分析：
- 当插入第一个元素时，首先调用ArrayList的add()，此时size=0，minCapacity=1，elementData还是默认空的，这时求得最小的扩容量是默认值10和minCapacity的较大值。获取到最小的扩容量后，minCapacity=10，和elementData的长度进行对比，由于最小扩容量仍然比elementData大，所以扩容，进入grow方法。
- 当插入第二个元素时，首先调用ArrayList的add()，此时size=1，minCapacity=2，elementData的长度已经扩大至10，2<10，因此不会扩容，也不会进入grow方法。
- 添加第 3、4···到第 10 个元素时，依然不会执行 grow 方法，数组容量都为 10。
- 直到添加第 11 个元素，minCapacity(为 11)比 elementData.length（为 10）要大。进入 grow 方法进行扩容。
grow方法分析：
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//将oldCapacity 右移一位，其效果相当于oldCapacity /2
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);
}int newCapacity = oldCapacity + (oldCapacity >> 1),所以 ArrayList 每次扩容之后容量都会变为原来的 1.5 倍。
问题一：为什么是移位运算？">>"（移位运算符）：>>1 右移一位相当于除 2，右移 n 位相当于除以 2 的 n 次方。这里 oldCapacity 明显右移了 1 位所以相当于 oldCapacity /2。对于大数据的 2 进制运算,位移运算符比那些普通运算符的运算要快很多,因为程序仅仅移动一下而已,不去计算,这样提高了效率,节省了资源。
当最小扩容量比MAX_ARRAY_SIZE还要大时，调用hugeCapacity方法：
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}如果 minCapacity 大于最大容量，则新容量则为Integer.MAX_VALUE，否则，新容量大小则为 MAX_ARRAY_SIZE 即为 Integer.MAX_VALUE - 8。
ensureCapacity方法的使用
这个方法 ArrayList 内部没有被调用过，所以很显然是提供给用户调用的。
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
// supposed to be at default size.
: DEFAULT_CAPACITY;
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}这个方法直接通过比较调用grow方法进行扩容，如果没有调用这一方法，并且还是add大量元素，就需要从第一次add方法开始不断从0开始一点点扩容，浪费了不必要的时间。因此，最好在 add 大量元素之前用 ensureCapacity 方法，以减少增量重新分配的次数 。
遍历时删除是一个不正确的 *** 作，即使有时候代码不出现异常，但执行逻辑也会出现问题。关于这个问题，阿里巴巴 Java 开发手册里也有所提及。这里引用一下：
【强制】不要在 foreach 循环里进行元素的 remove/add *** 作。remove 元素请使用 Iterator 方式，如果并发 *** 作，需要对 Iterator 对象加锁。
测试代码：
List list=new ArrayList<>();
list.add("1");
list.add("2");
for(String item:list){
if("1".equals(item)){
list.remove(item);
}
} 代码的运行结果是只显示了1.这是因为我们都知道 Java 中的 foreach 是个语法糖，编译成字节码后会被转成用迭代器遍历的方式。所以我们可以把上面的代码转换一下，等价于下面形式：
List a = new ArrayList<>();
a.add("1");
a.add("2");
Iterator it = a.iterator();
while (it.hasNext()) {
String temp = it.next();
System.out.println("temp: " + temp);
if("1".equals(temp)){
a.remove(temp);
}
} 而ArrayList 的迭代器源码：
private class Itr implements Iterator {
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
int expectedModCount = modCount;
Itr() {}
public boolean hasNext() {
return cursor != size;
}
@SuppressWarnings("unchecked")
public E next() {
checkForComodification();
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[lastRet = i];
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
} 第一次进入 while 循环时，一切正常，元素 1 也被删除了。但删除元素 1 后，就无法再进入 while 循环，此时 it.hasNext() 为 false。原因是删除元素 1 后，元素计数器 size = 1，而迭代器中的 cursor 也等于 1，从而导致 it.hasNext() 返回false。
如果测试代码进行一些改变，则会抛错： List a = new ArrayList<>();
a.add("1");
a.add("2");
a.add("3");
Iterator it = a.iterator();
while (it.hasNext()) {
String temp = it.next();
System.out.println("temp: " + temp);
if("1".equals(temp)){
a.remove(temp);
}
} 原因是ArrayList有个变量modCount，每次list调用add()或remove()方法都会modCount++，在上述代码中由于有三次add()调用，因此modCount=3，而迭代器初始化的时候就赋值int expectedModCount = modCount;而在迭代器的next()方法中首先检查expectedModCount和modCount是否相等，这样是为了做快速失败——如果在遇到并发修改时，迭代器会快速地抛出异常，而不是在将来某个不确定的时间点冒着任意而又不确定行为的风险来进行 *** 作，也就是将可能出现的bug点推前。因此如果不等，说明这期间其他线程可能对list做了修改。
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}第一个测试代码之所以没有报错而是直接结束运行，是因为在第二次循环的时候，运行到hasNext()就已经是false，无需往下面进行。
第二个测试点之所以报错是因为在第二次循环的时候，运行到hasNext()，cursor=1，size=2，所以hasNext()=true，进入next()方法，然后判断modCount=4，expecedModCount=3，抛错。
正确写法应该是调用迭代器的删除方法：
public void sortColors() {
List a = new ArrayList<>();
a.add("1");
a.add("2");
a.add("3");
Iterator it = a.iterator();
while (it.hasNext()) {
String temp = it.next();
System.out.println("temp: " + temp);
if("1".equals(temp)){
//调用迭代器的remove方法
it.remove();
}
}
} 代码运行的结果不会再抛错。原因可以参考源码：
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
//两个参数保持一致，所以删除结点也不会报错
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}https://www.tianxiaobo.com/2018/01/28/ArrayList源码分析/
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）