网站flash客服/最好的优化公司

内部结构

• ArrayList内部核心是一个Object数组elementData
• Object数组的长度（length）视为ArrayList当前的容量（capacity）
• size对象表示ArrayList当前的元素个数

类上的重要注释

内部是Object数组
允许put null值,会自动扩容
size、isEmpty、get、set、add 等方法时间复杂度都是 O (1);
多个线程操作一个ArrayList实例，如果有改变结构的操作，就一定要在外部进行线程同步，推荐的做法：List list = Collections.synchronizedList(new ArrayList(...))
增强for循环,或者使用迭代器迭代过程中，如果数组大小被改变，会快速失败，抛出异常。

如何初始化一个有元素的ArrayList

1. 普通方式：

ArrayList<String> list = new ArrayList<>();
list.add("1");
list.add("2");

2. 内部类方式：

ArrayList<String> list = new ArrayList<>(){add("aaa");add("bbb");
}

3. Arrays.asList

ArrayList<String> list = new ArrayList<>(Arrays.asList("aaa", "bbb");

4. Collections.ncopies

例子：初始化一个由10个0组成的集合

ArrayList<Integer> list = new ArrayList<>(Collections.nCopies(10, 0));

重要源码

构造

ArrayList有三种构造方法

public ArrayList()；//elementData初始化一个空数组
public ArrayList(int initialCapacity) //this.elementData = new Object[initialCapacity]
public ArrayList(Collection<? extends E> c) 

这里主要关注new ArrayList()和new ArrayList(0)的区别，两者都是初始化一个空数组，但是：

无参构造得到的ArrayList，容量一开始是0，初次add时会直接扩容到10（重新申请一个length为10的数组，并且拷贝过来）

但new ArrayList(0)得到ArrayList，按照扩容核心方法grow()中的写法，从0开始增长容量，前期容量增长的会很慢（0->1->2->3->4->6->9->13)

一般情况下为了避免扩容造成的造成的损耗，new ArrayList(0)不推荐使用

add 尾部添加

//要点：添加前会确认容量,防止数组越界public boolean add(E e) {ensureCapacityInternal(size + 1);elementData[size++] = e;return true;
}//扩容
//1.先确认是否需要扩容,当期望容量(size(元素数)+1)超过当前容量了，就需要扩容
//2.一般期望容量都是size+1,除了无参构造的空数组第一次扩容时,期望容量是10
private void ensureCapacityInternal(int minCapacity) {ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}private void ensureExplicitCapacity(int minCapacity) {modCount++;// overflow-conscious codeif (minCapacity - elementData.length > 0) //所需的最小容量超过当前容量了，就需要扩容grow(minCapacity);
}private static int calculateCapacity(Object[] elementData, int minCapacity) {if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { //无参构造,默认初始化容量为10return Math.max(DEFAULT_CAPACITY, minCapacity);}return minCapacity;
}//扩容本质是按照新容量创建一个新数组，然后把老数组数据用Arrays.copyOf复制过去
//新容量的计算规则//1.一般是原容量的3/2，用old+old>>1实现//2.3/2可能都不够（比如0*3/2）,直接扩容成期望容量(其实就是+1)//3.3/2超过最大容量了 Integer.MAX_VALUE - 8,看看期望容量和Integer.MAX_VALUE - 8哪个更适合
private void grow(int minCapacity) {// overflow-conscious codeint oldCapacity = elementData.length;int newCapacity = oldCapacity + (oldCapacity >> 1);  //3/2if (newCapacity - minCapacity < 0) //比如0的3/2倍还是0,直接扩容到1就好了newCapacity = minCapacity;if (newCapacity - MAX_ARRAY_SIZE > 0) //newCapacity超大了,就不能用3/2规则了,看看minCapacitynewCapacity = 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) // overflowthrow new OutOfMemoryError();return (minCapacity > MAX_ARRAY_SIZE) ?Integer.MAX_VALUE :MAX_ARRAY_SIZE;
}

指定位置插入

从逻辑上看指定位置插入是四步：

1. 查看index是否越界
2. 容量检查，不够扩容
3. 数据迁移：将插入位置之后的所有元素拷贝到+1的位置
4. element插入到指定位置

注意这个方法上面的注释

1. rangeCheck，越界的标准是看size而不是capacity：
   • 对于ArrayList来说，内部数组的长度就是capacity也就是容量，当前数组的元素个数是size，这两个数据并不见得相等（比如无参构造生成的ArrayList，size可能为1，capacity为10）
   • 但从使用者的角度来看，ArrayList就是个动态增长的list，使用者感知不到容量、扩容，使用者看起来这个ArrayList的末尾就是size
   • 调用add只能在数据中间插入或者在数据末尾（下标为size的位置）插入，否则即使插入的下标没有超过capacity，但是超过了size，也算越界。
   • 删除,同理,也会有rangeCheck
2. 固定位置的插入删除,每次都会涉及大量的数据迁移,在拥有大量数据的ArrayList中不建议这么做

public void add(int index, E element) {rangeCheckForAdd(index);ensureCapacityInternal(size + 1);  // Increments modCount!!System.arraycopy(elementData, index, elementData, index + 1,size - index);elementData[index] = element;size++;
}

指定位置删除

可类比上个方法

public E remove(int index) {
//溢出校验rangeCheck(index);modCount++;E oldValue = elementData(index);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//返回被删除元素return oldValue;}

按元素删除

方法注释：

• 新增的时候是没有对 null 进行校验的，所以删除的时候也是允许删除 null 值的；
• 找到值在数组中的索引位置，是通过 equals 来判断的，如果数组元素不是基本类型，需要我们关注 equals 的具体实现。

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;}}return false;}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}

重点：迭代器

迭代器模式简介

我们遍历一个一维的集合时，经常会使用for循环或者foreach循环

for (String item : list) {System.out.println(item);
}

如果我们要遍历一个二维的图，简单的for循环就做不到了，这时我们可能会采用DFS或者BFS之类的办法，相信大家刷算法的时候都写过。

这时就会存在以下问题，同时也引出迭代器模式：

1. 我肯定不想每次遍历时都把DFS的代码重新在客户端代码里写一遍，这意味着客户端代码需要关心数据结构的具体实现，一旦数据结构的具体实现变了（比如邻接矩阵变成邻接表了），或者遍历方法变了（DFS变成BFS了），就需要把客户端代码的遍历代码全都修改一遍
2. 如果将这部分遍历的逻辑封装到到容器类中，也会导致容器类代码的复杂性。

因此，我们可以将遍历操作拆分到迭代器类中。比如，针对图的遍历，我们就可以定义 DFSIterator、BFSIterator 两个迭代器类，让它们分别来实现深度优先遍历和广度优先遍历，容器类和迭代器之间用组合方式关联。

并且，容器和迭代器都提供了抽象的接口，方便我们在开发的时候，基于接口而非具体的实现编程。当需要切换新的遍历算法的时候，比如，从前往后遍历链表切换成从后往前遍历链表，客户端代码只需要将迭代器类从 LinkedIterator 切换为 ReversedLinkedIterator 即可，其他代码都不需要修改。除此之外，添加新的遍历算法，我们只需要扩展新的迭代器类，也更符合开闭原则。

总结起来，迭代器模式有以下的好处

1. 封装复杂数据结构的遍历代码：简单的数据结构我可以直接用for循环遍历，但是复杂数据结构的遍历代码，没必要在自己的客户端代码里再实现一遍，于是拆分出迭代器接口，容器类和迭代器之间用组合方式关联。
2. 扩展性：我们也不想把遍历方法写在容器类中（容器类更加复杂，变化原因增加，不符合单一职责）我需要更改或添加迭代方式时，只需要扩展新的迭代器类，而不需要去更改其他地方的代码，更符合开闭原则
3. 基于接口编程：容器和迭代器都提供了抽象的接口，方便我们在开发的时候，基于接口而非具体的实现编程。当需要切换新的遍历算法的时候，比如，从前往后遍历链表切换成从后往前遍历链表，客户端代码只需要将迭代器类从 LinkedIterator 切换为 ReversedLinkedIterator 即可，其他代码都不需要修改

ArrayList的迭代器

Java中如果要自己实现迭代器，实现java.util.Iterator类就好了，ArrayList就是这样做的

ArrayList实现了两个迭代器类Itr和ListItr，后者继承了前者，先看看第一个

这里先省略方法的具体实现，看看一个迭代器的主要参数和方法

private class Itr implements Iterator<E> {int cursor;       // 迭代过程中下一个元素的位置，默认从0开始int lastRet = -1; // 一般情况下表示上一次迭代过程中索引的位置；删除一次后：为-1int expectedModCount = modCount; //expectedModCount表示迭代过程中期望的版本号Itr() {}public boolean hasNext() { //查看还有没有值可以迭代}public E next() { //如果有值可以迭代，迭代值是多少}public void remove() { //删除当前迭代的值}public void forEachRemaining(Consumer<? super E> consumer) {}final void checkForComodification() {}
}

常规情况下，遍历一个list的代码，以及删除元素的代码如下

// 获取迭代器并遍历 ArrayList
Iterator<String> iter = list.iterator();
while (iter.hasNext()) {String item = iter.next(); //next的关键无非是cursor如何移动if (item.equals("banana")) {// 使用迭代器删除元素iter.remove(); //cursor指向的是下一个元素的位置，lastRet是cursor的前一个位置，所以remove操作实际上删除的是lastRet指向的元素}
}

需要注意删除操作：

• cursor指向的是下一个元素的位置，lastRet是cursor的前一个位置，所以remove操作实际上删除的是lastRet指向的元素
• 执行remove之后，cursor=lastRet，退回到前一个位置，防止遍历时丢失元素，lastRet=-1
• 这也就导致了remove操作不能连续执行，必须是先执行next操作(会将lastRet重新变为cursor-1)，才能执行一次remove

modCount有什么作用？与一个Fail-Fast 机制有关：

首先ArrayList中有一个modCount属性，所有更改数据结构的操作，add，remove都会将modCount++，可以被视作更改了ArrayList的版本号

另外，迭代器Itr中有属性expectedModCount，初始化为modCount。每次next()都会先检查expectedModCount有没有发生改变，如果改变就抛异常。

也就是说从Itr创建开始，就不允许当前ArrayList有结构上的改变，避免可能存在的错误

private class Itr implements Iterator<E> {int expectedModCount = modCount; //expectedModCount表示迭代过程中期望的版本号public E next() { //如果有值可以迭代，迭代值是多少checkForComodification();}final void checkForComodification() {if (modCount != expectedModCount)throw new ConcurrentModificationException();}
}

那可能会出什么错呢？

一句话总结就是：遍历过程中在当前游标之前（包括当前游标）的位置插入或删除元素，会导致某个元素重复遍历或者丢失遍历

因此，在ArrayList实现的Iterator逻辑中，每次cursor指向的都是下次元素的位置，而lastRet指向最后一次遍历元素的位置
每次remove操作，因为调用了arraylist的remove方法，modCount会自增，这时会将expectedModCount重置为modCount（防止fail-fast），并且将cursor回退为lastRet，避免丢失元素

Fail-Fast 机制通常设计用于停止正常操作，而不是试图继续可能出错的过程。（注意这个并不能防止多线程操作出现异常，只是防止单线程操作，迭代器遍历过程中被其他方式改变了集合结构，那么继续使用迭代器是有可能报异常的，因为从使用者的角度看这不属于使用者的逻辑错误，但是可能会出错，所以在设计上应当主动报异常）

ArrayList还实现了一个迭代器ListIterator

private class ListItr extends Itr implements ListIterator<E> {ListItr(int index) {super();cursor = index;}public boolean hasPrevious() {return cursor != 0;}public int nextIndex() {return cursor;}public int previousIndex() {return cursor - 1;}@SuppressWarnings("unchecked")public E previous() {checkForComodification();int i = cursor - 1;if (i < 0)throw new NoSuchElementException();Object[] elementData = ArrayList.this.elementData;if (i >= elementData.length)throw new ConcurrentModificationException();cursor = i;return (E) elementData[lastRet = i];}public void set(E e) {if (lastRet < 0)throw new IllegalStateException();checkForComodification();try {ArrayList.this.set(lastRet, e);} catch (IndexOutOfBoundsException ex) {throw new ConcurrentModificationException();}}public void add(E e) {checkForComodification();try {int i = cursor;ArrayList.this.add(i, e);cursor = i + 1;lastRet = -1;expectedModCount = modCount;} catch (IndexOutOfBoundsException ex) {throw new ConcurrentModificationException();}}
}

区别：

1.使用范围不同，Iterator可以应用于所有的集合，Set、List和Map和这些集合的子类型。而ListIterator只能用于List及其子类型。

2.ListIterator有add方法，可以向List中添加对象，而Iterator不能。

3.ListIterator和Iterator都有hasNext()和next()方法，可以实现顺序向后遍历，但是ListIterator有hasPrevious()和previous()方法，可以实现逆向（顺序向前）遍历。Iterator不可以。

4.ListIterator可以定位当前索引的位置，nextIndex()和previousIndex()可以实现。Iterator没有此功能。

5.都可实现删除操作，但是ListIterator可以实现对象的修改，set()方法可以实现。Iterator仅能遍历，不能修改。

参考资料

王争. 设计模式之美