一、ArrayList简介
ArrayList顶部有一段很长的注释,大概地介绍了ArrayList。
1.1 原文
/**
* Resizable-array implementation of the <tt>List</tt> interface. Implements
* all optional list operations, and permits all elements, including
* <tt>null</tt>. In addition to implementing the <tt>List</tt> interface,
* this class provides methods to manipulate the size of the array that is
* used internally to store the list. (This class is roughly equivalent to
* <tt>Vector</tt>, except that it is unsynchronized.)
*
* <p>The <tt>size</tt>, <tt>isEmpty</tt>, <tt>get</tt>, <tt>set</tt>,
* <tt>iterator</tt>, and <tt>listIterator</tt> operations run in constant
* time. The <tt>add</tt> operation runs in <i>amortized constant time</i>,
* that is, adding n elements requires O(n) time. All of the other operations
* run in linear time (roughly speaking). The constant factor is low compared
* to that for the <tt>LinkedList</tt> implementation.
*
* <p>Each <tt>ArrayList</tt> instance has a <i>capacity</i>. The capacity is
* the size of the array used to store the elements in the list. It is always
* at least as large as the list size. As elements are added to an ArrayList,
* its capacity grows automatically. The details of the growth policy are not
* specified beyond the fact that adding an element has constant amortized
* time cost.
*
* <p>An application can increase the capacity of an <tt>ArrayList</tt> instance
* before adding a large number of elements using the <tt>ensureCapacity</tt>
* operation. This may reduce the amount of incremental reallocation.
*
* <p><strong>Note that this implementation is not synchronized.</strong>
* If multiple threads access an <tt>ArrayList</tt> instance concurrently,
* and at least one of the threads modifies the list structurally, it
* <i>must</i> be synchronized externally. (A structural modification is
* any operation that adds or deletes one or more elements, or explicitly
* resizes the backing array; merely setting the value of an element is not
* a structural modification.) This is typically accomplished by
* synchronizing on some object that naturally encapsulates the list.
*
* If no such object exists, the list should be "wrapped" using the
* {@link Collections#synchronizedList Collections.synchronizedList}
* method. This is best done at creation time, to prevent accidental
* unsynchronized access to the list:<pre>
* List list = Collections.synchronizedList(new ArrayList(...));</pre>
*
* <p><a name="fail-fast">
* The iterators returned by this class's {@link #iterator() iterator} and
* {@link #listIterator(int) listIterator} methods are <em>fail-fast</em>:</a>
* if the list is structurally modified at any time after the iterator is
* created, in any way except through the iterator's own
* {@link ListIterator#remove() remove} or
* {@link ListIterator#add(Object) add} methods, the iterator will throw a
* {@link ConcurrentModificationException}. Thus, in the face of
* concurrent modification, the iterator fails quickly and cleanly, rather
* than risking arbitrary, non-deterministic behavior at an undetermined
* time in the future.
*
* <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
* as it is, generally speaking, impossible to make any hard guarantees in the
* presence of unsynchronized concurrent modification. Fail-fast iterators
* throw {@code ConcurrentModificationException} on a best-effort basis.
* Therefore, it would be wrong to write a program that depended on this
* exception for its correctness: <i>the fail-fast behavior of iterators
* should be used only to detect bugs.</i>
*
* <p>This class is a member of the
* <a href="{@docRoot}/../technotes/guides/collections/index.html">
* Java Collections Framework</a>.
*
* @author Josh Bloch
* @author Neal Gafter
* @see Collection
* @see List
* @see LinkedList
* @see Vector
* @since 1.2
*/
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
...
}
1.2 翻译
List接口的大小可变数组的实现。实现了所有可选列表操作,并允许包括null在内的所有元素。除了实现List接口外,此类还提供一些方法来操作内部用来存储列表的数组的大小。(此类大致上等同于Vector类,除了此类是不同步的。)
size、isEmpty、get、set、iterator和listIterator操作都以固定时间运行。add操作以分摊的固定时间运行,也就是说,添加n个元素需要O(n)时间。其他所有操作都以线性时间运行(大体上讲)。与用于LinkedList实现的常数因子相比,此实现的常数因子较低。
每个ArrayList实例都有一个容量。该容量是指用来存储列表元素的数组的大小。它总是至少等于列表的大小。随着向ArrayList中不断添加元素,其容量也自动增长。并未指定增长策略的细节,因为这不只是添加元素会带来分摊固定时间开销那样简单。
在添加大量元素前,应用程序可以使用ensureCapacity操作来增加ArrayList实例的容量。这可以减少递增式再分配的数量。
注意,此实现不是同步的。如果多个线程同时访问一个ArrayList实例,而其中至少一个线程从结构上修改了列表,那么它必须保持外部同步。(结构上的修改是指任何添加或删除一个或多个元素的操作,或者显式调整底层数组的大小;仅仅设置元素的值不是结构上的修改。)这一般通过对自然封装该列表的对象进行同步操作来完成。如果不存在这样的对象,则应该使用Collections.synchronizedList方法将该列表“包装”起来。这最好在创建时完成,以防止意外对列表进行不同步的访问:List list = Collections.synchronizedList(new ArrayList(…));
此类的iterator和listIterator方法返回的迭代器是快速失败的:在创建迭代器之后,除非通过迭代器自身的remove或add方法从结构上对列表进行修改,否则在任何时间以任何方式对列表进行修改,迭代器都会抛出ConcurrentModificationException。因此,面对并发的修改,迭代器很快就会完全失败,而不是冒着在将来某个不确定时间发生任意不确定行为的风险。
注意,迭代器的快速失败行为无法得到保证,因为一般来说,不可能对是否出现不同步并发修改做出任何硬性保证。快速失败迭代器会尽最大努力抛出ConcurrentModificationException。因此,为提高这类迭代器的正确性而编写一个依赖于此异常的程序是错误的做法:迭代器的快速失败行为应该仅用于检测bug。
此类是Java Collections Framework的成员。
1.3 一语中的
底层:ArrayList是List接口的大小可变数组的实现。 是否允许null:ArrayList允许null元素。 时间复杂度:size、isEmpty、get、set、iterator和listIterator方法都以固定时间运行,时间复杂度为O(1)。add和remove方法需要O(n)时间。与用于LinkedList实现的常数因子相比,此实现的常数因子较低。 容量:ArrayList的容量可以自动增长。 是否同步:ArrayList不是同步的。 迭代器:ArrayList的iterator和listIterator方法返回的迭代器是 fail-fast 的。
如果小伙伴们不了解”fail-fast”机制,可以参考如下文章:深入浅出fail-fast机制
1.4 线程安全性
对ArrayList进行添加元素的操作的时候是分两个步骤进行的,即第一步先在object[size]的位置上存放需要添加的元素;第二步将size的值增加1。由于这个过程在多线程的环境下是不能保证具有原子性的,因此ArrayList在多线程的环境下是线程不安全的。
具体举例说明:在单线程运行的情况下,如果Size = 0,添加一个元素后,此元素在位置 0,而且Size=1;而如果是在多线程情况下,比如有两个线程,线程 A 先将元素存放在位置0。但是此时 CPU 调度线程A暂停,线程 B 得到运行的机会。线程B也向此ArrayList 添加元素,因为此时 Size 仍然等于 0 (注意哦,我们假设的是添加一个元素是要两个步骤哦,而线程A仅仅完成了步骤1),所以线程B也将元素存放在位置0。然后线程A和线程B都继续运行,都增 加 Size 的值。 那好,现在我们来看看 ArrayList 的情况,元素实际上只有一个,存放在位置 0,而Size却等于 2。这就是“线程不安全”了。
如果非要在多线程的环境下使用ArrayList,就需要保证它的线程安全性,通常有两种解决办法:
第一,使用synchronized关键字; 第二,可以用Collections类中的静态方法synchronizedList();对ArrayList进行调用即可。 第三,也可以使用concurrent并发包下的CopyOnWriteArrayList类。
1.5 优劣分析
优点
ArrayList底层以数组实现,是一种随机访问模式,再加上它实现了RandomAccess接口,因此查找也就是get的时候非常快。 ArrayList在顺序添加一个元素的时候非常方便,只是往数组里面添加了一个元素而已。 根据下标遍历元素,效率高。 根据下标访问元素,效率高。 可以自动扩容,默认为每次扩容为原来的1.5倍。
缺点
插入和删除元素的效率不高。 根据元素下标查找元素需要遍历整个元素数组,效率不高。 线程不安全。
二、定义
我们先来看看ArrayList的定义:
public class ArrayList<E> extends AbstractList<E>
implements List<E>,RandomAccess,Cloneable,java.io.Serializable
从中我们可以了解到:
**ArrayList **:说明ArrayList支持泛型。 extends AbstractList :继承了AbstractList。AbstractList提供List接口的骨干实现,以最大限度地减少“随机访问”数据存储(如ArrayList)实现Llist所需的工作。 **implements List **:实现了List。实现了所有可选列表操作。 implements RandomAccess:表明ArrayList支持快速(通常是固定时间)随机访问。此接口的主要目的是允许一般的算法更改其行为,从而在将其应用到随机或连续访问列表时能提供良好的性能。 implements Cloneable:表明其可以调用clone()方法来返回实例的field-for-field拷贝。 implements java.io.Serializable:表明该类具有序列化功能。
为什么要先继承AbstractList,而让AbstractList先实现List?而不是让ArrayList直接实现List?
这里是有一个思想,接口中全都是抽象的方法,而抽象类中可以有抽象方法,还可以有具体的实现方法,正是利用了这一点,让AbstractList是实现接口中一些通用的方法,而具体的类, 如ArrayList就继承这个AbstractList类,拿到一些通用的方法,然后自己再实现一些自己特有的方法,这样一来,让代码更简洁,就继承结构最底层的类中通用的方法都抽取出来,先一起实现了,减少重复代码。所以一般看到一个类上面还有一个抽象类,应该就是这个作用。
ArrayList的父类AbstractList也实现了List接口,那为什么子类ArrayList还是去实现一遍呢?
collection 的作者Josh说他写这代码的时候觉得这个会有用处,但是其实并没什么用,但因为没什么影响,就一直留到了现在。
ArrayList的类结构图:
如何查看类的完整结构图可以参考如下文章:IDEA如何查看类的完整结构图
三、数据结构
如图所示,ArrayList底层通过数组实现。
一般的时候,我们只需要知道ArrayList的实际大小,但是作为一个优秀的程序员,知道ArrayList数组的容量大小非常重要,如果你想知道如何获取ArrayList的容量大小,可以参考如下文章:Java如何获取ArrayList的容量(elemenData)大小?
四、域的解读
/**
* 初始化默认容量。
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 指定该ArrayList容量为0时,返回该空数组。
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* 当调用无参构造方法,返回的是该数组。刚创建一个ArrayList 时,其内数据量为0。
* 它与EMPTY_ELEMENTDATA的区别就是:该数组是默认返回的,而后者是在用户指定容量为0时返回。
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* 保存添加到ArrayList中的元素。
* ArrayList的容量就是该数组的长度。
* 该值为DEFAULTCAPACITY_EMPTY_ELEMENTDATA 时,当第一次添加元素进入ArrayList中时,数组将扩容值DEFAULT_CAPACITY。
* 被标记为transient,在对象被序列化的时候不会被序列化。
*/
transient Object[] elementData; // non-private to simplify nested class access
/**
* ArrayList的实际大小(数组包含的元素个数)。
* @serial
*/
private int size;
思考:elementData被标记为transient,那么它的序列化和反序列化是如何实现的呢?被标记为transient的属性在对象被序列化的时候不会被保存。ArrayList自定义了它的序列化和反序列化方式。详情请查看writeObject(java.io.ObjectOutputStream s)和readObject(java.io.ObjectOutputStream s)方法。
五、构造方法
ArrayList提供了三种构造方法:
ArrayList(int initialCapacity):构造一个指定容量为capacity的空ArrayList。 ArrayList():构造一个初始容量为 10 的空列表。 ArrayList(Collection<? extends E> c):构造一个包含指定 collection 的元素的列表,这些元素是按照该 collection 的迭代器返回它们的顺序排列的。
5.1 ArrayList( int initialCapacity)
/**
* 构造一个指定初始化容量为capacity的空ArrayList。
*
* @param initialCapacity ArrayList的指定初始化容量
* @throws IllegalArgumentException 如果ArrayList的指定初始化容量为负。
*/
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);
}
}
5.2 ArrayList()
/**
* 构造一个初始容量为 10 的空列表。
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
5.3 ArrayList(Collection<? extends E> c)
/**
* 构造一个包含指定 collection 的元素的列表,这些元素是按照该 collection 的迭代器返回它们的顺序排列的。
*
* @param c 其元素将放置在此列表中的 collection
* @throws NullPointerException 如果指定的 collection 为 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有以下核心方法:
方法名 | 时间复杂度 |
---|---|
get(int index) | O(1) |
add(E e) | O(1) |
add(add(int index, E element)) | O(n) |
remove(int index) | O(n) |
set(int index, E element) | O(1) |
6.1 get( int index)
/**
* 返回list中索引为index的元素
*
* @param index 需要返回的元素的索引
* @return list中索引为index的元素
* @throws IndexOutOfBoundsException 如果索引超出size
*/
public E get(int index) {
//越界检查
rangeCheck(index);
//返回索引为index的元素
return elementData(index);
}
/**
* 越界检查。
* 检查给出的索引index是否越界。
* 如果越界,抛出运行时异常。
* 这个方法并不检查index是否合法。比如是否为负数。
* 如果给出的索引index>=size,抛出一个越界异常
*/
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/**
* 返回索引为index的元素
*/
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
}
从代码中可以看到,因为ArrayList底层是数组,所以它的get方法非常简单,先是判断一下有没有越界,之后就直接通过数组下标来获取元素。get方法的时间复杂度是O(1)。
6.2 add(E e)
/**
* 添加元素到list末尾.
*
* @param e 被添加的元素
* @return true
*/
public boolean add(E e) {
//确认list容量,如果不够,容量加1。注意:只加1,保证资源不被浪费
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
从源码中可以看到,add(E e)有两个步骤:
空间检查,如果有需要进行扩容 插入元素
空间检查和扩容的介绍在下面。
空间的问题解决后,插入过程就显得非常简单。
6.3 扩容方法
/**
* 增加ArrayList容量。
*
* @param minCapacity 想要的最小容量
*/
public void ensureCapacity(int minCapacity) {
// 如果elementData等于DEFAULTCAPACITY_EMPTY_ELEMENTDATA,最小扩容量为DEFAULT_CAPACITY,否则为0
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)? 0: DEFAULT_CAPACITY;
//如果想要的最小容量大于最小扩容量,则使用想要的最小容量。
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
/**
* 数组容量检查,不够时则进行扩容,只供类内部使用。
*
* @param minCapacity 想要的最小容量
*/
private void ensureCapacityInternal(int minCapacity) {
// 若elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA,则取minCapacity为DEFAULT_CAPACITY和参数minCapacity之间的最大值
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
/**
* 数组容量检查,不够时则进行扩容,只供类内部使用
*
* @param minCapacity 想要的最小容量
*/
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 确保指定的最小容量 > 数组缓冲区当前的长度
if (minCapacity - elementData.length > 0)
//扩容
grow(minCapacity);
}
/**
* 分派给arrays的最大容量
* 为什么要减去8呢?
* 因为某些VM会在数组中保留一些头字,尝试分配这个最大存储容量,可能会导致array容量大于VM的limit,最终导致OutOfMemoryError。
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/**
* 扩容,保证ArrayList至少能存储minCapacity个元素
* 第一次扩容,逻辑为newCapacity = oldCapacity + (oldCapacity >> 1);即在原有的容量基础上增加一半。第一次扩容后,如果容量还是小于minCapacity,就将容量扩充为minCapacity。
*
* @param minCapacity 想要的最小容量
*/
private void grow(int minCapacity) {
// 获取当前数组的容量
int oldCapacity = elementData.length;
// 扩容。新的容量=当前容量+当前容量/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);
}
/**
* 进行大容量分配
*/
private static int hugeCapacity(int minCapacity) {
//如果minCapacity<0,抛出异常
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
//如果想要的容量大于MAX_ARRAY_SIZE,则分配Integer.MAX_VALUE,否则分配MAX_ARRAY_SIZE
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
看完了代码,可以对扩容方法总结如下:
进行空间检查,决定是否进行扩容,以及确定最少需要的容量 如果确定扩容,就执行grow(int minCapacity),minCapacity为最少需要的容量 第一次扩容,逻辑为newCapacity = oldCapacity + (oldCapacity >> 1);即在原有的容量基础上增加一半。 第一次扩容后,如果容量还是小于minCapacity,就将容量扩充为minCapacity。 对扩容后的容量进行判断,如果大于允许的最大容量MAX_ARRAY_SIZE,则将容量再次调整为MAX_ARRAY_SIZE。至此扩容操作结束。
6.4 add( int index, E element)
/**
* 在制定位置插入元素。当前位置的元素和index之后的元素向后移一位
*
* @param index 即将插入元素的位置
* @param element 即将插入的元素
* @throws IndexOutOfBoundsException 如果索引超出size
*/
public void add(int index, E element) {
//越界检查
rangeCheckForAdd(index);
//确认list容量,如果不够,容量加1。注意:只加1,保证资源不被浪费
ensureCapacityInternal(size + 1); // Increments modCount!!
// 对数组进行复制处理,目的就是空出index的位置插入element,并将index后的元素位移一个位置
System.arraycopy(elementData, index, elementData, index + 1,size - index);
//将指定的index位置赋值为element
elementData[index] = element;
//实际容量+1
size++;
}
从源码中可以看到,add(E e)有三个步骤:
越界检查 空间检查,如果有需要进行扩容 插入元素
越界检查很简单
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
空间检查和扩容的介绍在上面。
空间的问题解决后,插入过程就显得非常简单。add(int index, E e)需要先对元素进行移动,然后完成插入操作,也就意味着该方法有着线性的时间复杂度,即O(n)。
6.5 remove( int index)
/**
* 删除list中位置为指定索引index的元素
* 索引之后的元素向左移一位
*
* @param index 被删除元素的索引
* @return 被删除的元素
* @throws IndexOutOfBoundsException 如果参数指定索引index>=size,抛出一个越界异常
*/
public E remove(int index) {
//检查索引是否越界。如果参数指定索引index>=size,抛出一个越界异常
rangeCheck(index);
//结构性修改次数+1
modCount++;
//记录索引为inde处的元素
E oldValue = elementData(index);
// 删除指定元素后,需要左移的元素个数
int numMoved = size - index - 1;
//如果有需要左移的元素,就移动(移动后,该删除的元素就已经被覆盖了)
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// size减一,然后将索引为size-1处的元素置为null。为了让GC起作用,必须显式的为最后一个位置赋null值
elementData[--size] = null; // clear to let GC do its work
//返回被删除的元素
return oldValue;
}
/**
* 越界检查。
* 检查给出的索引index是否越界。
* 如果越界,抛出运行时异常。
* 这个方法并不检查index是否合法。比如是否为负数。
* 如果给出的索引index>=size,抛出一个越界异常
*/
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
看完代码后,可以将ArrayList删除指定索引的元素的步骤总结为:
检查索引是否越界。如果参数指定索引index>=size,抛出一个越界异常 将索引大于index的元素左移一位(左移后,该删除的元素就被覆盖了,相当于被删除了)。 将索引为size-1处的元素置为null(为了让GC起作用)。
注意:为了让GC起作用,必须显式的为最后一个位置赋null值。上面代码中如果不手动赋null值,除非对应的位置被其他元素覆盖,否则原来的对象就一直不会被回收。
6.6 set( int index, E element)
/**
* 替换指定索引的元素
*
* @param 被替换元素的索引
* @param element 即将替换到指定索引的元素
* @return 返回被替换的元素
* @throws IndexOutOfBoundsException 如果参数指定索引index>=size,抛出一个越界异常
*/
public E set(int index, E element) {
//检查索引是否越界。如果参数指定索引index>=size,抛出一个越界异常
rangeCheck(index);
//记录被替换的元素
E oldValue = elementData(index);
//替换元素
elementData[index] = element;
//返回被替换的元素
return oldValue;
}
这里可以看到modCount的用处,当modCount发生改变后,立刻抛出ConcurrentModificationException异常。通过之前的分析可以知道当列表内容被修改时modCount会增加。也就是说如果在遍历ArrayList的过程中有其他线程修改了ArrayList,那么将抛出ConcurrentModificationException异常
6.7 indexOf(Object o)
indexOf(Object o)方法的作用是从头开始查找与指定元素相等的元素,如果找到,则返回找到的元素在元素数组中的下标,如果没有找到返回-1。与该方法类似的是lastIndexOf(Object o)方法,该方法的作用是从尾部开始查找与指定元素相等的元素。
查看该方法的源码可知,该方法从需要查找的元素是否为空的角度分为两种情况分别讨论。这也意味着该方法的参数可以是null元素,也意味着ArrayList集合中能够保存null元素。方法实现的逻辑也比较简单,直接循环遍历元素数组,通过equals方法来判断对象是否相同,相同就返回下标,找不到就返回-1。这也解释了为什么要把情况分为需要查找的对象是否为空两种情况讨论,不然的话空对象调用equals方法则会产生空指针异常。
// 从首开始查找数组里面是否存在指定元素
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;
}
6.8 forEach(Consumer<? super E> action)
遍历列表 ,这里我们先来看一下源码是怎么写的:
/**
* The number of times this list has been <i>structurally modified</i>.
* Structural modifications are those that change the size of the
* list, or otherwise perturb it in such a fashion that iterations in
* progress may yield incorrect results.
*
* <p>This field is used by the iterator and list iterator implementation
* returned by the {@code iterator} and {@code listIterator} methods.
* If the value of this field changes unexpectedly, the iterator (or list
* iterator) will throw a {@code ConcurrentModificationException} in
* response to the {@code next}, {@code remove}, {@code previous},
* {@code set} or {@code add} operations. This provides
* <i>fail-fast</i> behavior, rather than non-deterministic behavior in
* the face of concurrent modification during iteration.
*
* <p><b>Use of this field by subclasses is optional.</b> If a subclass
* wishes to provide fail-fast iterators (and list iterators), then it
* merely has to increment this field in its {@code add(int, E)} and
* {@code remove(int)} methods (and any other methods that it overrides
* that result in structural modifications to the list). A single call to
* {@code add(int, E)} or {@code remove(int)} must add no more than
* one to this field, or the iterators (and list iterators) will throw
* bogus {@code ConcurrentModificationExceptions}. If an implementation
* does not wish to provide fail-fast iterators, this field may be
* ignored.
*/
protected transient int modCount = 0;//操作数,since abstract AbstractList.java
@Override
public void forEach(Consumer<? super E> action) {
// 确保不为空
Objects.requireNonNull(action);
final int expectedModCount = modCount;
@SuppressWarnings("unchecked")
final E[] elementData = (E[]) this.elementData;
final int size = this.size;
for (int i=0; modCount == expectedModCount && i < size; i++) {
action.accept(elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
/**
* Checks that the specified object reference is not {@code null}. This
* method is designed primarily for doing parameter validation in methods
* and constructors, as demonstrated below:
* <blockquote><pre>
* public Foo(Bar bar) {
* this.bar = Objects.requireNonNull(bar);
* }
* </pre></blockquote>
*
* @param obj the object reference to check for nullity
* @param <T> the type of the reference
* @return {@code obj} if not {@code null}
* @throws NullPointerException if {@code obj} is {@code null}
*/
public static <T> T requireNonNull(T obj) {//since final class Objects.java
if (obj == null)
throw new NullPointerException();
return obj;
}
6.9 clear()方法
/**
* Removes all of the elements from this list. The list will
* be empty after this call returns.
从列表中删除所有元素。该调用返回后,列表将为空。
*/
public void clear() {
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
这里我们做一个小demo:
package com.uncle;
import java.lang.reflect.Field;
import java.util.ArrayList;
import java.util.HashMap;
public class Main {
public static void main(String[] args) throws Exception {
HashMap hashMap = new HashMap();
ArrayList arrayList = new ArrayList();
Main main = new Main();
arrayList.add(main);
arrayList.add(main);
arrayList.add(main);
arrayList.add(main);
arrayList.add(main);
arrayList.add(main);
arrayList.add(main);
arrayList.add(main);
arrayList.add(main);
arrayList.add(main);
arrayList.add(main);
Class<? extends ArrayList> aClass = arrayList.getClass();
Field elementData = aClass.getDeclaredField("elementData");
elementData.setAccessible(true);
Object[] objects = (Object[]) elementData.get(arrayList);
arrayList.clear();
System.out.println(objects.length);
System.out.println(arrayList.size());
}
}
显然,容量虽然扩容了,但是里面的有效元素全部清空了。
七、ArrayList与迭代器模式
迭代器模式(Iterator Pattern):提供一种方法来访问聚合对象中的各个元素,而不用暴露这个对象的内部表示。
在Java中,ArrayList的迭代器有两种:Iterator和ListIterator。
7.1 Iterator
迭代器是一个用来遍历并选择序列中的对象。Java的Iterator的只能单向移动。
案例
在写如何实现之前,先看一个使用迭代器Iterator小例子:
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
public class Test {
@org.junit.Test
public void test() {
List list = new ArrayList<>();
list.add("1");
list.add("2");
list.add("3");
list.add("4");
Iterator iterator = list.iterator();
while (iterator.hasNext()) {
String str = (String) iterator.next();
System.out.println(str);
iterator.remove();
}
System.out.println(list.size());
}
}
运行结果
1
2
3
4
0
方法
-
iterator(),list.iterator()用来从容器对象中返回一个指向list开始处的迭代器。 -
next(),获取序列中的下个元素。 -
hasNext(),检查序列中向下是否还有元素。 -
remove(),将迭代器最近返回的一个元素删除。这也意味着调用remove()前需要先调用next()。
实现
迭代器模式中有四个角色:
抽象聚合类Aggregate。在ArrayList的Iterator迭代器实现中,没有抽象聚合类。虽然它实现了AbstractList,实现了List,但它向外部提供的创建迭代器的方法iterator()是它自己的。 具体聚合类ConcreteAggregate。在ArrayList的Iterator迭代器实现中,指的是ArrayList。 抽象迭代器Iterator。在ArrayList的Iterator迭代器实现中,指的是Iterator接口。 具体迭代器ConcreteIterator。在ArrayList中的Iterator迭代器实现中,指的是Itr。
ArrayList代码片段
public class ArrayList<E>
{
/**
* 保存添加到ArrayList中的元素。
* ArrayList的容量就是该数组的长度。
* 该值为DEFAULTCAPACITY_EMPTY_ELEMENTDATA 时,当第一次添加元素进入ArrayList中时,数组将扩容值DEFAULT_CAPACITY。
* 被标记为transient,在对象被序列化的时候不会被序列化。
*/
transient Object[] elementData;
// ArrayList的实际大小(数组包含的元素个数)。
private int size;
/**
* 返回一个用来遍历ArrayList元素的Iterator迭代器
*/
public Iterator<E> iterator() {
return new Itr();
}
/**
* AbstractList.Itr的最优化的版本
*/
private class Itr implements Iterator<E> {
int cursor; // 下一个要返回的元素的索引
int lastRet = -1; // 最近的被返回的元素的索引; 如果没有返回-1。
int expectedModCount = modCount;
/**
* 判断是否有下一个元素
*/
public boolean hasNext() {
//如果下一个要返回的元素的索引不等于ArrayList的实际大小,则返回false
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();
}
}
}
Iterator
import java.util.function.Consumer;
public interface Iterator<E> {
boolean hasNext();
E next();
default void remove() {
throw new UnsupportedOperationException("remove");
}
default void forEachRemaining(Consumer<? super E> action) {
Objects.requireNonNull(action);
while (hasNext())
action.accept(next());
}
}
Itr.java
ArrayList的内部类
7.2 ListIterator
ListIterator是一个更加强大的Iterator的子类型。它只能用于各种List类的访问。它最大的优点是可以双向移动。它还可以产生相对于迭代器在列表中指向的当前位置的前一个和后一个元素的索引,并且可以使用set()方法替换它访问过的最后一个元素。
案例
在写如何实现之前,先看一个使用列表迭代器ListIterator的小例子:
import java.util.ArrayList;
import java.util.List;
import java.util.ListIterator;
public class Test {
@org.junit.Test
public void test() {
List list = new ArrayList<>();
list.add("0");
list.add("1");
list.add("2");
list.add("3");
ListIterator iterator = list.listIterator();
System.out.println("--------------------向下遍历--------------------");
while (iterator.hasNext()) {
int nextIndex = iterator.nextIndex();
String next = (String) iterator.next();
//int previousIndex = iterator.previousIndex();
System.out.println("当前元素:"+next+",当前元素索引:"+nextIndex/*+",前一个元素的索引"+previousIndex*/);
}
System.out.println("--------------------向上遍历--------------------");
while (iterator.hasPrevious()) {
int previousIndex = iterator.previousIndex();
String previous = (String) iterator.previous();
System.out.println("当前元素:"+previous+",当前元素索引:"+previousIndex);
}
System.out.println("-----------测试set()和listIterator(n)----------");
System.out.println(list);
iterator = list.listIterator(3);
while(iterator.hasNext()){
iterator.next();
iterator.set("5");
}
System.out.println(list);
}
}
运行结果
-------向下遍历-------
当前元素:0,当前元素索引:0
当前元素:1,当前元素索引:1
当前元素:2,当前元素索引:2
当前元素:3,当前元素索引:3
-------向上遍历-------
当前元素:3,当前元素索引:3
当前元素:2,当前元素索引:2
当前元素:1,当前元素索引:1
当前元素:0,当前元素索引:0
-------测试set()和listIterator(n)-------
[0, 1, 2, 3]
[0, 1, 2, 5]
方法
-
listIterator(),list.iterator()用来从容器对象中返回一个指向list开始处的迭代器。 -
listIterator(n),list.iterator()用来从容器对象中返回一个指向列表索引为n的迭代器。 -
next(),获取序列中的下个元素,运行后索引+1。 -
previous(),获取序列中的上个元素,运行后索引-1。 -
nextIndex,获取序列中的下个元素的索引。 -
previousIndex,获取序列中的下个元素的索引。 -
hasNext(),检查序列中向下是否还有元素。 -
hasPrevious(),检查序列中向上是否还有元素。 -
remove(),从列表中删除next()或previous()返回的最后一个元素。这也意味着调用remove()前需要先调用next()或者previous()。 -
add(E e): 将指定的元素插入列表,插入位置为迭代器当前位置之前。 -
set(E e):从列表中将next()或previous()返回的最后一个元素返回的最后一个元素更改为指定元素e。
实现
迭代器模式中有四个角色:
抽象聚合类Aggregate。在ArrayList的ListIterator迭代器实现中,没有抽象聚合类。虽然它实现了AbstractList,实现了List,但它向外部提供的创建迭代器的方法listIterator()是它自己的。 具体聚合类ConcreteAggregate。在ArrayList的ListIterator迭代器实现中,指的是ArrayList。 抽象迭代器Iterator。在ArrayList的ListIterator迭代器实现中,指的是ListIterator。 具体迭代器ConcreteIterator。在ArrayList中的ListIterator迭代器实现中,指的是ListItr。
ArrayList代码片段
public class ArrayList<E>
{
/**
* 保存添加到ArrayList中的元素。
* ArrayList的容量就是该数组的长度。
* 该值为DEFAULTCAPACITY_EMPTY_ELEMENTDATA 时,当第一次添加元素进入ArrayList中时,数组将扩容值DEFAULT_CAPACITY。
* 被标记为transient,在对象被序列化的时候不会被序列化。
*/
transient Object[] elementData;
// ArrayList的实际大小(数组包含的元素个数)。
private int size;
/**
* 返回一个一开始就指向列表索引为index的元素处的ListIterator
*
* @throws IndexOutOfBoundsException
*/
public ListIterator<E> listIterator(int index) {
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("Index: "+index);
return new ListItr(index);
}
/**
* 返回一个一开始就指向列表索引为0的元素处的ListIterator
*
* @see #listIterator(int)
*/
public ListIterator<E> listIterator() {
return new ListItr(0);
}
/**
* AbstractList.ListItr的最优化版本
*/
private class ListItr extends Itr implements ListIterator<E> {
//用来从list中返回一个指向list索引为index的元素处的迭代器
ListItr(int index) {
super();
cursor = index;
}
//获取list中的上个元素
public boolean hasPrevious() {
return cursor != 0;
}
//获取list中的下个元素的索引
public int nextIndex() {
return cursor;
}
//获取list中的上个元素的索引
public int previousIndex() {
return cursor - 1;
}
//获取list中的上个元素
@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];
}
//从列表中将next()或previous()返回的最后一个元素返回的最后一个元素更改为指定元素e
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();
}
}
}
}
Iterator
import java.util.function.Consumer;
public interface Iterator<E> {
boolean hasNext();
E next();
default void remove() {
throw new UnsupportedOperationException("remove");
}
default void forEachRemaining(Consumer<? super E> action) {
Objects.requireNonNull(action);
while (hasNext())
action.accept(next());
}
}
ListItr.java
ArrayList的内部类。
八、阿里面试实战
7.1 ArrayList如何删除指定元素?
这是一个很麻烦的面试题,很考验对源码的认识和理解,我们来慢慢的剖析一下。
为了大家能够更好的理解ArrayList,以及这道面试题,推荐大家看一下这篇文章:ArrayList与迭代器模式
如果使用常规的思想:
public class TestListMain {
public static void main(String[] args) {
List<String> result = new ArrayList<>();
result.add("a");
result.add("b");
result.add("c");
result.add("d");
for (String s : result) {
if ("b".equals(s)) {
result.remove("b");
}
}
}
}
可是这样就会抛出异常:既然从源代码分析不出来,我们就看下源代码编译后的class文件中的内容是怎样的吧,毕竟class文件才是JVM真正执行的代码,不看不知道,一看吓一跳,JDK原来是这么玩的。原来如此,我们原始代码中的for-each语句,编译后的实际是以迭代器来代替执行的。
public class TestListMain {
public TestListMain() {
}
public static void main(String[] args) {
List<String> result = new ArrayList();
result.add("a");
result.add("b");
result.add("c");
result.add("d");
//创建迭代器
Iterator var2 = result.iterator();
while(var2.hasNext()) {
String s = (String)var2.next();
if ("b".equals(s)) {
result.remove("b");
}
}
}
}
通过ArrayList创建的Itr这个内部类迭代器,于是for-each循环就转化成了迭代器加while循环的方式,原来看上去的for-each循环被挂羊头卖狗肉了。
public Iterator<E> iterator() {
return new Itr();
}
Itr这个内部类迭代器,通过判断hasNext()来判断迭代器是否有内容,而next()方法则获取迭代器中的内容。
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;
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];
}
...
}
大致的过程如下所示:
真正抛异常的地方是这个检测方法, 当modCount与expectedModCount不相等的时候直接抛出异常了。那我们要看下modCount以及expectedModCount分别是什么。这里的modCount代表ArrayList的修改次数,而expectedModCount代表的是迭代器的修改次数,在创建Itr迭代器的时候,将modCount赋值给了expectedModCount,因此在本例中一开始modCount和expectedModCount都是4(添加了四次String元素)。但是在获取到b元素之后,ArrayList进行了remove操作,因此modCount就累加为5了。因此在进行检查的时候就出现了不一致,最终导致了异常的产生。到此我们找到了抛异常的原因,循环使用迭代器进行循环,但是操作元素却是使用的ArrayList操作,因此迭代器在循环的时候发现元素被修改了所以抛出异常。
我们再来思考下,为什么要有这个检测呢?这个异常到底起到什么作用呢?我们先来开下ConcurrentModificationException的注释是怎么描述的。简单理解就是不允许一个线程在修改集合,另一个线程在集合基础之上进行迭代。一旦检测到了这种情况就会通过fast-fail机制,抛出异常,防止后面的不可知状况。
/**
***
* For example, it is not generally permissible for one thread to modify a Collection
* while another thread is iterating over it. In general, the results of the
* iteration are undefined under these circumstances. Some Iterator
* implementations (including those of all the general purpose collection implementations
* provided by the JRE) may choose to throw this exception if this behavior is
* detected. Iterators that do this are known as <i>fail-fast</i> iterators,
* as they fail quickly and cleanly, rather that risking arbitrary,
* non-deterministic behavior at an undetermined time in the future.
***
**/
public class ConcurrentModificationException extends RuntimeException {
...
}
回顾整个过程如何正确的删除既然抛异常的原因是循环使用了迭代器,而删除使用ArrayList导致检测不通过。那么我们就循环使用迭代器,删除也是用迭代器,这样就可以保证一致了。
public class TestListMain {
public static void main(String[] args) {
List<String> result = new ArrayList<>();
result.add("a");
result.add("b");
result.add("c");
result.add("d");
Iterator<String> iterator = list.iterator();
while (iterator .hasNext()) {
String str = iterator.next();
if ("b".equals(str)) {
iterator.remove();
}
}
}
7.3 为啥线程不安全还使用ArrayList呢?
因为在我们正常得使用场景中,都是用来查询的,不会涉及太频繁的增删,如果涉及到频繁的增删,可以使用LinkedList,如果需要线程安全的就是可以使用Vector,CopyOrWriteArrayList
7.4 1.7和1.8版本初始化的区别
1.7的时候是初始化就创建一个容量为10的数组,1.8后是初始化先创建一个空数组,第一次add时才扩容为10
7.5 ArrayList在增删的时候是怎么做的?(为什么慢)
ArrayList有指定index(索引下标)新增,也有尾部新增,但是都有校验长度的判断ensureCapacityInternal,就是说如果⻓度不够,是需要扩容的。在扩容的时候,1.7是取余,1.8是位运算,右移⼀位,其实就是除以2这个操作。
//尾插add方法
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
//index(索引)插入,指定位置新增的时候,在校验之后的操作很简单,就是数组的copy
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++;
}
//真正扩容
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);
}
//删除
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。
7.6 ArrayList是线程安全的么?
不是,可以用Vector,Collections.synchronizedList(),原理都是給方法套个synchronized, CopyOnWriteArrayList
7.7 ArrayList⽤来做队列合适么?
队列⼀般是FIFO(先⼊先出)的,如果⽤ArrayList做队列,就需要在数组尾部追加数据,数组头部删除数组,反过来也可以。但是⽆论如何总会有⼀个操作会涉及到数组的数据搬迁,这个是⽐较耗费性能的。结论:ArrayList不适合做队列。
7.8 那数组适合⽤来做队列么?
数组是⾮常合适的。⽐如ArrayBlockingQueue内部实现就是⼀个环形队列,它是⼀个定⻓队列,内部是⽤⼀个定⻓数组来实现的。另外著名的Disruptor开源Library也是⽤环形数组来实现的超⾼性能队列,具体原理不做解释,⽐较复杂。简单点说就是使⽤两个偏移量来标记数组的读位置和写位置,如果超过⻓度就折回到数组开头,前提是它们是定⻓数组。
7.9 ArrayList的遍历和LinkedList遍历性能⽐较如何?
ArrayList要比LinkedList快得多,ArrayList遍历最大的优势在于内存的连续性,CPU的内部缓存结构会缓存连续的内存片段,可以大幅降低读取内存的性能开销。
7.10 再理解ArrayList数组扩容
//详细扩容
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);
}
7.11 Java如何获取ArrayList的容量(elementData)大小?
相信你深入解读ArrayList源码之后,一定会知道ArrayList是这样的:也就是说,elemenData数组的长度就是ArrayList的容量。更为关键的是,我们无法通过ArrayList的方法得到elementData数组的信息。
解决办法
虽然我们无法通过ArrayList的方法得到elementData数组的信息,但是我们可以通过反射来获取ArrayList的内部私有属性。
案例一
package com.uncle;
import java.lang.reflect.Field;
import java.util.ArrayList;
public class Main {
public static void main(String[] args) throws Exception {
ArrayList arrayList = new ArrayList();
Main main = new Main();
arrayList.add(main);
Class<? extends ArrayList> aClass = arrayList.getClass();
Field elementData = aClass.getDeclaredField("elementData");
elementData.setAccessible(true);
Object[] objects = (Object[]) elementData.get(arrayList);
System.out.println(objects.length);//10
}
}
我们通过无参构造方法创建ArrayList集合,默认容量为10。
案例二
package com.uncle;
import java.lang.reflect.Field;
import java.util.ArrayList;
public class Main {
public static void main(String[] args) throws Exception {
ArrayList arrayList = new ArrayList(3);
Main main = new Main();
arrayList.add(main);
Class<? extends ArrayList> aClass = arrayList.getClass();
Field elementData = aClass.getDeclaredField("elementData");
elementData.setAccessible(true);
Object[] objects = (Object[]) elementData.get(arrayList);
System.out.println(objects.length);//3
}
}
我们通过有参构造方法创建ArrayList集合,默认容量为3。
案例三
package com.uncle;
import java.lang.reflect.Field;
import java.util.ArrayList;
public class Main {
public static void main(String[] args) throws Exception {
ArrayList arrayList = new ArrayList();
Main main = new Main();
arrayList.add(main);
arrayList.add(main);
arrayList.add(main);
arrayList.add(main);
arrayList.add(main);
arrayList.add(main);
arrayList.add(main);
arrayList.add(main);
arrayList.add(main);
arrayList.add(main);
arrayList.add(main);
Class<? extends ArrayList> aClass = arrayList.getClass();
Field elementData = aClass.getDeclaredField("elementData");
elementData.setAccessible(true);
Object[] objects = (Object[]) elementData.get(arrayList);
System.out.println(objects.length);//15
}
}
我们通过无参构造方法创建ArrayList集合,默认容量为10,当我们新增11个时候,数组扩容默认容量10的1.5倍,结果为15。
原文始发于微信公众号(步尔斯特):ArrayList源码解读—Java8版本
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
文章由极客之音整理,本文链接:https://www.bmabk.com/index.php/post/35860.html