ArrayList源码解析
相信写Java代码不久就会接触到ArrayList,这是个容器类，我们在使用的时候觉得这个容器好像是无限大的一样，我们可以不断的操作它(add、get、remove)，其实它的内部实现是基于数组的，这篇文章就是介绍其内部原理。了解原理后，我们在使用的时候可以根据实际情况来配置它，让它拥有更好的性能和更少的内存占用。
ArrayList类主要字段
private static final long serialVersionUID = 8683452581122892189L;
/**
* Default initial capacity.
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* Shared empty array instance used for empty instances.
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* Shared empty array instance used for default sized empty instances. We
* distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
* first element is added.
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* The array buffer into which the elements of the ArrayList are stored.
* The capacity of the ArrayList is the length of this array buffer. Any
* empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
* will be expanded to DEFAULT_CAPACITY when the first element is added.
*/
transient Object[] elementData; // non-private to simplify nested class access
/**
* The size of the ArrayList (the number of elements it contains).
*
* @serial
*/
private int size;
/**
* The maximum size of array to allocate.
* Some VMs reserve some header words in an array.
* Attempts to allocate larger arrays may result in
* OutOfMemoryError: Requested array size exceeds VM limit
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
复制代码
从这个字段结构，我们得到以下信息：
- ArrayList内部主要是使用Object[] elementData来存储我们添加的数据。
- size字段记录当前List已经存储的数据的个数。
- DEFAULT_CAPACITY字段标记默认初始化ArrayList时分配的数组的长度。
- EMPTY_ELEMENTDATA和DEFAULTCAPACITY_EMPTY_ELEMENTDATA是定义的两个空数组，为什么要使用两个呢？下面我们会分析原因。
ArrayList相关方法解析
下面我们通过我们使用ArrayList时常用的方法来慢慢分析它的源码。
构造函数
/**
* Constructs an empty list with the specified initial capacity.
*
* @param initialCapacity the initial capacity of the list
* @throws IllegalArgumentException if the specified initial capacity
* is negative
*/
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);
}
}
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
*
* @param c the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null'
*/
public ArrayList(Collection<? extends E> c) {
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;
}
}
复制代码
ArrayList构造函数一共有3个：
- 我们最常用的new ArrayList()其实只是把elementData指向了默认空数组而已(DEFAULTCAPACITY_EMPTY_ELEMENTDATA)。
- initialCapacity容量的构造函数源码也很简单，如果initialCapacity>0就创建一个initialCapacity容量的数组，如果initialCapacity==0，elementData只是指向EMPTY_ELEMENTDATA。
-
最后的构造函数是使用Collection集合来初始化ArrayList。先将Collection集合转化成数组，然后根据size来执行不同的操作。如果转化后的数组不是Object类型的，就重新创建一个size大小的数组。
下面我们就从常用的方法来一步步解读ArrayList的源码。
add方法
/**
* Appends the specified element to the end of this list.
*
* @param e element to be appended to this list
* @return <tt>true</tt> (as specified by {@link Collection#add})
*/
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
/**
* Inserts the specified element at the specified position in this
* list. Shifts the element currently at that position (if any) and
* any subsequent elements to the right (adds one to their indices).
*
* @param index index at which the specified element is to be inserted
* @param element element to be inserted
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
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++;
}
复制代码
从上面我们看到，add(E e)方法直接将元素添加到数组末尾。而add(int index,E element)方法将元素添加到指定的index位置，当然原先index后面的元素需要调整位置(都往后挪一个位置)。
我们从上面的源码中看到ensureCapacityInternal方法，继续往下看源码：
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
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);
}
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：
我们先看ensureCapacityInternal方法。第一步：如果elementData指向DEFAULTCAPACITY_EMPTY_ELEMENTDATA，那么就扩容数组到DEFAULT_CAPACITY(10)。通过这一步我们知道只有我们new ArrayList()的时，elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA条件才会成立。第二步：我们根据流程ensureCapacityInternal-->ensureExplicitCapacity-->grow，我们知道这种情况下ArrayList会创建一个长度为10的数组。 情况2：
上面分析ArrayList构造器时，elementData也会指向EMPTY_ELEMENTDATA空数组。只有new ArrayList(0)或者new ArrayList(空集合)才会成立。这种情况下，我们根据ensureCapacityInternal-->ensureExplicitCapacity-->grow流程来看，这时候分配的数组很小(占用内存小),这是保守的内存分配策略。 总结：
通过上面的分析，我们知道了DEFAULTCAPACITY_EMPTY_ELEMENTDATA和EMPTY_ELEMENTDATA两个空数组的不同用途。前者默认创建10个元素的数组，然后在这个基础上进行扩容。后者是比较保守的内存分配策略，数据扩容比较缓慢。
grow方法解析
grow方法是整个ArrayList扩容的核心，下面我们来看下其源码：
/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
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);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
复制代码
我们看到ArrayList默认扩容大小是原大小的1.5倍。下面逻辑依次是判断一些边界的情况：
- 如果newCapacity小于minCapacity，那么就将数组大小调整为minCapacity大小。
- 如果minCapacity的值在MAX_ARRAY_SIZE和Integer.MAX_VALUE之间，那么新数组分配Integer.MAX_VALUE大小，否则分配MAX_ARRAY_SIZE。
contains,indexOf,lastIndexOf相关检索方法
/**
* Returns <tt>true</tt> if this list contains the specified element.
* More formally, returns <tt>true</tt> if and only if this list contains
* at least one element <tt>e</tt> such that
* <tt>(o==null ? e==null : o.equals(e))</tt>.
*
* @param o element whose presence in this list is to be tested
* @return <tt>true</tt> if this list contains the specified element
*/
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
/**
* Returns the index of the first occurrence of the specified element
* in this list, or -1 if this list does not contain the element.
* More formally, returns the lowest index <tt>i</tt> such that
* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
* or -1 if there is no such index.
*/
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
/**
* Returns the index of the last occurrence of the specified element
* in this list, or -1 if this list does not contain the element.
* More formally, returns the highest index <tt>i</tt> such that
* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
* or -1 if there is no such index.
*/
public int lastIndexOf(Object o) {
if (o == null) {
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
复制代码
这些方法逻辑都比较清晰，就是循环遍历，找出符合条件的元素而已。
toArray方法
这个方法有时我们需要用到，它是将ArrayList转化成数组。下面我们来看其源码：
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
if (a.length < size)
// Make a new array of a's runtime type, but my contents:'
return (T[]) Arrays.copyOf(elementData, size, a.getClass());
System.arraycopy(elementData, 0, a, 0, size);
if (a.length > size)
a[size] = null;
return a;
}
复制代码
通过Arrays.copyOf和System.arraycopy方法，ArrayList将elementData数组中的数据拷贝到新数组，然后返回。System.arraycopy方法效率很高，其内部使用C/C++(设置会使用汇编)，我们平时开发的时候，有数组拷贝，也应该使用这些方法。
get/set方法
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
}
/**
* Returns the element at the specified position in this list.
*
* @param index index of the element to return
* @return the element at the specified position in this list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
/**
* Replaces the element at the specified position in this list with
* the specified element.
*
* @param index index of the element to replace
* @param element element to be stored at the specified position
* @return the element previously at the specified position
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
复制代码
逻辑比较简单，不做详细介绍。
remove方法
/**
* Removes the element at the specified position in this list.
* Shifts any subsequent elements to the left (subtracts one from their
* indices).
*
* @param index the index of the element to be removed
* @return the element that was removed from the list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
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;
}
/**
* Removes the first occurrence of the specified element from this list,
* if it is present. If the list does not contain the element, it is
* unchanged. More formally, removes the element with the lowest index
* <tt>i</tt> such that
* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>
* (if such an element exists). Returns <tt>true</tt> if this list
* contained the specified element (or equivalently, if this list
* changed as a result of the call).
*
* @param o element to be removed from this list, if present
* @return <tt>true</tt> if this list contained the specified element
*/
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 remove method that skips bounds checking and does not
* return the value removed.
*/
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
}
复制代码
逻辑还是比较清晰的，只是remove(index)/或者remove(object)后，需要调用System.arraycopy来高效的移动index后面的数组，让其可以填充位置。
removeAll/retainAll方法
有的朋友可能没有用过这两个方法，下面我们通过一个小栗子来看一下这两个方法到底是什么，请看代码：
ArrayList<String> list=new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");
list.add("D");
list.add("E");
list.add("F");
ArrayList<String> list1=new ArrayList<>();
list1.add("C");
list1.add("D");
//list.removeAll(list1);
//[A, B, E, F]
System.out.println(list);
list.retainAll(list1);
//[C，D]
System.out.println(list);
复制代码
从结果我们可以看出，removeAll方法是计算两个集合的差集，retainAll计算两个集合的交集。下面我们通过源码来分析：
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, false);
}
public boolean retainAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, true);
}
private boolean batchRemove(Collection<?> c, boolean complement) {
final Object[] elementData = this.elementData;
int r = 0, w = 0;
boolean modified = false;
try {
for (; r < size; r++)
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r];
} finally {
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws.
if (r != size) {
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
if (w != size) {
// clear to let GC do its work
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
size = w;
modified = true;
}
}
return modified;
}
复制代码
我们看到，这边设计比较精妙，通过一个boolean值，将取差值和取交集的方法整合为一个方法。batchRemove方法的代码设计实现还是很不错的，核心的逻辑就是try语句块里面的for循环，finally语句块里面主要是数据拷贝及特殊值的处理。
迭代器
Java集合在设计的时候就是支持迭代器的。下面我们来看看ArrayList里面迭代器的相关部分。
获取迭代器对象
/**
* Returns an iterator over the elements in this list in proper sequence.
*
* <p>The returned iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
*
* @return an iterator over the elements in this list in proper sequence
*/
public Iterator<E> iterator() {
return new Itr();
}
复制代码
我们看到默认返回的是一个Itr对象，熟悉Java集合层次结构(类继承结构)的朋友，可能知道ArrayList的基类AbstractList里面就有一个内部类Itr。现在ArrayList内部重新实现了一个优化版本的Itr类，我们来看源码：
/**
* An optimized version of AbstractList.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
int expectedModCount = modCount;
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];
}
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();
}
}
@Override
@SuppressWarnings("unchecked")
public void forEachRemaining(Consumer<? super E> consumer) {
Objects.requireNonNull(consumer);
final int size = ArrayList.this.size;
int i = cursor;
if (i >= size) {
return;
}
final Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length) {
throw new ConcurrentModificationException();
}
while (i != size && modCount == expectedModCount) {
consumer.accept((E) elementData[i++]);
}
// update once at end of iteration to reduce heap write traffic
cursor = i;
lastRet = i - 1;
checkForComodification();
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
复制代码
从上面的源代码中，迭代器只提供基本的向后遍历、删除等功能。这样我们在遍历ArrayList的时候，还可以使用迭代器来进行遍历(当然for(E e : elements)这种写法会被编译期自动转化成迭代器的调用)。
ListItr迭代器
继续往下研究ArrayList的源代码，我们会发现ArrayList内部还实现了ListItr的迭代器。这个迭代器除了提供向后遍历功能外，还提供了向前遍历，增加、设置等功能。是一个功能比较全的迭代器实现。我们看下源码：
/**
* An optimized version of AbstractList.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这个迭代器里面很多操作都是直接调用的ArrayList类的方法，它只是做了一层封装。
ConcurrentModificationException异常出现的原因及解决方法
有的朋友在遍历ArrayList集合的时候可能遇到过这个异常，这个异常时ArrayList类设计的快速失败机制导致的，这个异常认为集合在遍历的时候，做出了修改。我下面这个例子就出现了这个异常，一起来看下：
ArrayList<String> list=new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");
list.add("D");
list.add("E");
list.add("F");
for(String item : list) {
System.out.println(item);
list.remove(item);
}
//或者
/*
Iterator<String> iterator=list.iterator();
while (iterator.hasNext()) {
String string = (String) iterator.next();
System.out.println(string);
list.remove(string);
}
*/
Exception in thread "main" java.util.ConcurrentModificationException
at java.util.ArrayList$Itr.checkForComodification(Unknown Source)
at java.util.ArrayList$Itr.next(Unknown Source)
at com.learn.example.RunMain.main(RunMain.java:42)
复制代码
下面两种遍历方式都会导致异常的发生，下面我们来看下原因。上面介绍过第一种foreach循环写法编译后就是迭代器。我们直接看迭代器。
@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();
}
复制代码
我们看到next()方法第一行会调用checkForComodification()方法，我们看到如果modCount和expectedModCount不相等的话，就会抛出这个异常。我们上面再看Itr源码的时候看到expectedModCount刚开始赋值的是ArrayList类里面的modCount变量。下面list.remove(o)这个方法里面会让modCount++。源码如下：
/*
* Private remove method that skips bounds checking and does not
* return the value removed.
*/
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
}
复制代码
这样的话就会导致Itr内部的expectedModCount和ArrayList的modCount不一致，从而抛出这个异常。那么我们如何解决呢？只需要让modCount不增加，让它的值与expectedModCount同步即可。Itr内部也有remove方法，我们调用这个方法即可。
Iterator<String> iterator=list.iterator();
while (iterator.hasNext()) {
String string = (String) iterator.next();
System.out.println(string);
iterator.remove();
}
复制代码
总结
- ArrayList内部是Object[]数组，然后使用的时候进行动态扩容。
- ArrayList默认会分配10个元素的数组，然后在此基础上进行扩容，每次新的扩容后的数组长度是原数组长度的1.5倍。如果你大概知道集合的容量，可以指定初始化值，减少扩容带来性能损耗。
- ArrayList适合查询多，操作少的场景(因为操作过后，绝大部分情况下需要挪动数组位置)。
- ArrayList集合不是线程安全的，在多线程环境下需要加锁或者使用并发安全的容器。
正文到此结束
热门推荐
相关文章
近期评论
-
666
-
文章和留言都翻到11页了 没有OOM
-
-
朋友，翻页到11页，及以后，会出现OOM，无法访问
-
-
-
-
版本号是多少，你可以下载哪个代码仓库，jdk选1.8 直接跑就行
-
-
Loading...
![[HBLOG]公众号](https://www.liuhaihua.cn/img/qrcode_gzh.jpg)
