一般般帅
上一篇:String详解
ArrayList详解
1816 2017-09-17 2020-06-25
前言：在看完最常用的String后，我们来看下ArrayList的实现。
一、类结构
1、概述
// 依次实现了List接口、随机访问接口、可克隆接口和序列号接口
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
// 默认的初始容量，下面的一大串英文我们先不管（其实从命名上来看猜得出些端倪）
private static final int DEFAULT_CAPACITY = 10;
// 空集合
private static final Object[] EMPTY_ELEMENTDATA = {};
// 默认空集合
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 存储数组
transient Object[] elementData; // non-private to simplify nested class access
// 列表大小
private int size;
// 记录列表大小改变次数，判断是否在高并发情况下出现脏数据
// 不符合预期，将会抛出ConcurrentModificationException异常
protected transient int modCount = 0;
// 其他略
}
通过上面我们知道：
- 类的声明都是些常规性的，继承自AbstractList，实现子类特定操作及特性。
- 内部是维护着一个Object[]对象数组，默认初始化容量是10，值得注意的是上面出现了transient 关键字。
2、为什么是Object[]
不是泛型数组T[]是有原因的，简单的解释就是T[]在JVM内部本质就是Object[]，从T[]到Object[]转换过程中存在类型擦除。在编译时期，编译器可能会错过某些潜在的错误检查。详细解释，请自行参看博客：泛型详解。
3、为什么是transient
我们知道，ArrayList里面维护的是一个数组，这是清晰的。但实际情况下，elementData的大小往往比列表的大小要大，即elementData.length > size。所以为了防止浪费内存（或优化存储），被声明为transient，即不可被序列化，但也只是针对这个存储数组，对于类本身，它实现了自身的特定序列号方法。
二、构造方法
有三个构造方法，如下：
- 无参构造方法，代码如下
public ArrayList() {
// 说明DEFAULTCAPACITY_EMPTY_ELEMENTDATA是默认的空数组存储对象
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
- 数值参数构造方法，代码如下
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
// 说明EMPTY_ELEMENTDATA是参数为0时的空数组存储对象
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
- 序列接口对象参数的构造方法，代码如下
public ArrayList(Collection<? extends E> c) {
// 这个方法是前面分析过的，任意Collection都可以向数组转换
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;
}
}
三、add方法
用得最多的莫过于是add方法，来看代码实现：
public boolean add(E e) {
// 先检查添加元素后的size大小，是否需要扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
// 这一步是验证10 或 size+1，进行扩容操作
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) {
// 列表大小改变，记录加1
modCount++;
// 需要扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);// 等于1.5oldCapacity
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)// 如果超出了Integer的最大值2147483647，即2的32次方-1
newCapacity = hugeCapacity(minCapacity);
// 这个方法不深究，大概知道是复制一份elementData，容量变为newCapacity
elementData = Arrays.copyOf(elementData, newCapacity);
}
// 说明ArrayList可存储的数量是有限的
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
小结：既然内部维护的是一个数组对象，那我们是很熟悉的，这里的复杂点是对于扩容的处理。
四、其他方法
1、get方法
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
// 常规代码
E elementData(int index) {
return (E) elementData[index];
}
2、remove方法
public E remove(int index) {// 假设size为5，值为12345，remove(2)即中间那,3
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;// 5-2-1 = 2
if (numMoved > 0)// arraycopy(el, 3, el, 2, 2)即把34复制为45，现在是12455
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work让GC回收
return oldValue;
}
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);
3、另一个add方法
public void add(int index, E element) {// 假设size为5，值为12345，add(2, 0)即120345
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
// arraycopy(el, 3, el, 4, 2)即把45复制为345，现在是123345
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;// 120345
size++;
}
五、迭代器
1、概述
先简单介绍一下迭代器模式（Iterator Pattern）的概念：提供一种方法来访问聚合对象，而不用暴露这个对象的内部表示，通俗的说法就是，可以通过方法迭代返回内部的全部对象，如常见的hasNext（）和next（）方法。我们通过下面一段代码，来看下迭代器有什么好处
ArrayList<String> list = new ArrayList<>();
list.add("1");
list.add("2");
list.add("3");
list.add("4");
Iterator it = list.iterator();// 也可以是list.listIterator()
for (String temp : list) {
temp = null;// 说明foreach语法是基于迭代器的实现，只能用于遍历
}
while (it.hasNext()) {
System.out.print(it.next() + " ");// 由于是方法，只能遍历，不能对list内部数组进行操作
}
for (int i = 0; i < list.size() ; i++) {
System.out.print(list.get(i) + " ");// 速度比迭代器要快，迭代器是此基础上加上了一些逻辑判断
}
while (it.hasNext()) {
it.remove();// 不能进入
}
System.out.println(list.size());// 仍为4，说明迭代器内部有一个数组坐标，且此时已到末尾
下面我们看下两个迭代器的具体实现
2、Itr内部类
核心代码如下
private class Itr implements Iterator<E> {
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
public boolean hasNext() {
return cursor != size;
}
@SuppressWarnings("unchecked")
public E next() {
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];
}
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet);// 调用ArrayList中的remove方法，而不是内部类中的方法
cursor = lastRet;
lastRet = -1;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
}
2、ListItr内部类
核心代码如下
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();
}
}
}
从上面我们可以看出ListItr内部类是Itr内部类的升级版，在遍历的同时允许对内部对象进行操作，是一个补充。
六、比较
1、与Vertor相比
| - | ArrayList | Vector |
|---|---|---|
| 内部实现方式 | 基于Object[]数组 | 基于Object[]数组 |
| 线程是否安全 | 不安全，没有synchronized关键字 | 安全，但牺牲了性能 |
| 容量增长方式 | 默认增加为原来的50% | 默认一倍，可以指定增长因子 |
| 其他方面 | 大致一样 | 大致一样 |
2、与LinkedList相比
| - | ArrayList | LinkedList |
|---|---|---|
| 内部实现方式 | 基于Object[]数组 | 内部类Node |
| 线程是否安全 | 不安全，没有synchronized关键字 | 不安全 |
| 元素访问 | 支持随机访问，快 | 不支持随机，只能链式访问，慢 |
| 插入、删除操作 | 慢，需要维护内部数组 | 快，指针的引用切换 |
总访问次数: 398次, 一般般帅 创建于 2017-09-17, 最后更新于 2020-06-25
欢迎关注微信公众号，第一时间掌握最新动态！