总结
总结放前面防止太长不看:
- ArrayList内部是用数组实现的。
- 如果使用无参构造函数建立ArrayList,在添加第一个元素的时候会分配10个元素的空间。
- ArrayList的扩容是以1.5倍为基准的。
- ArrayList是线程不安全的,有fail-fast机制作改动保障。
层次图
ArrayList的Hierarchy:

先来看看List接口:
List接口
List代表有序集合,元素可以重复。
List家族一览:

默认实现方法:
default void replaceAll(UnaryOperator operator);
以指定的方法替换List中的所有元素,UnaryOperator
是一个函数式接口,输入一个类型对象,返回一个同类型对象。
default void replaceAll(UnaryOperator<E> operator) {
Objects.requireNonNull(operator);
final ListIterator<E> li = this.listIterator();
while (li.hasNext()) {
li.set(operator.apply(li.next()));
}
}
示例:
List<Integer> list = new ArrayList<Integer>();
list.add(1);
list.add(3);
list.add(5);
list.replaceAll(a->a+1); //list = [2,4,6]
default void sort(Comparator<? super E> c);
根据排序方法排序。还是先转为了Array再使用Arrays的sort方法进行排序。
default void sort(Comparator<? super E> c) {
Object[] a = this.toArray();
Arrays.sort(a, (Comparator) c);
ListIterator<E> i = this.listIterator();
for (Object e : a) {
i.next();
i.set((E) e);
}
}
AbstractList接口
AbstractList接口继承自AbstractCollection,为什么要提它呢,因为里面有个重要的字段modCount
,用于迭代器遍历元素时检查列表中的元素是否发生结构性变化。
参考下面“重要的内部类”中迭代器里next方法的实现。
重要的字段
transient Object[] elementData;
ArrayList的元素存储在这个数组中。
private int size;
记录空间大小。
重要的内部类
Itr实现了迭代器Iterator,ListItr实现了集合迭代器ListIterator
两者的介绍: 谈谈java中的Iterator
next的实现:
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];
}jav
其中的checkForComodification():
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
modCount在ArrayList每次add或者remove它的值都会加1。在初始化迭代器的时候,令expectedModCount = modCount
,在迭代器迭代的过程中,如果modCount被改变了,就会造成expectedModCount不等于modCount,抛出ConcurrentModificationException
警告。
比如下面这段程序就会抛出警告:
为什么在迭代器循环的时候不让使用list.remove修改元素呢?
有多线程下被影响的考虑,更重要的是,强制了在迭代器迭代的时候只能使用iterator.remove移除元素.
比如上面这段程序应该改成:
构造方法
已知ArrayList的元素是存放于一个数组中,那么在初始化一个ArrayList对象的时候会分配一个多大的数组?
先看两个构造方法:
public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}
其中常量DEFAULTCAPACITY_EMPTY_ELEMENTDATA
是一个空数组:
private static final Object[] DEFAULTCAPACITY_EMPTY_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);
}
}
使用一个初始容量初始化ArrayList。
如果传入的参数大于0,则分配一个这么大的数组。
注意到如果这里的initialCapacity等于0,令其等于常量EMPTY_ELEMENTDATA
也是一个空数组。
那为什么要区分EMPTY_ELEMENTDATA
和DEFAULTCAPACITY_EMPTY_ELEMENTDATA呢
?
因为他们是两个不同对象的引用,ArrayList通过这个区分当前对象是用无参构造方法创建的还是由ArrayList(0)
这样一个构造方法创建的
在后文“重要的内部方法”中的calculateCapacity方法,当第一个元素被加进来的时候就能知道应该扩容多少。
重要的内部方法
空间分配相关
private static int calculateCapacity(Object[] elementData, int minCapacity);
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
这个方法用于计算:
当原来数组为空,第一次插入元素的时候,数组应该分配多少空间,DEFAULTCAPACITY_EMPTY_ELEMENTDATA
呼应了上面构造方法中的无参构造方法,常量DEFAULT_CAPACITY=10
。
这说明:如果ArrayList是以无参构造方法建立的,在添加第一个元素时会直接分配10个元素的空间。
private void grow(int minCapacity);
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//即newCapacity = 1.5*oldCapacity
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);
}
可以看出数组是以1.5倍为基准扩容的,如果1.5倍后大于MAX_ARRAY_SIZE (Integer.MAX_VALUE - 8)
,则使用hugeCapacity(minCapacity)
确认(size是int类型,不能超过int范围的最大值)。
元素获取、增改相关
E elementData(int index);
E elementData(int index) {
return (E) elementData[index];
}
取元素,就是从数组中获取元素,是get等方法的依赖。
private void rangeCheck(int index);
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
边界检查。
rangeCheck方法是提供给get,remove,set之类的方法检查的,是给已经存在元素的集合操作的,范围0至size-1,这个方法把检查负责的职责交给了数组的访问,像get(-1)时会报异常ArrayIndexOutOfBoundsException。
private void rangeCheckForAdd(int index);
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
这个方法是提供给add和addAll的,会检查负数。因为如果扩容了数组再抛出异常就白扩容了。
原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/arraylist%e6%ba%90%e7%a0%81%e5%88%86%e6%9e%90/