前言
2022/11/2
路漫漫其修远兮,吾将上下而求索
本文是根据jdk学习所做笔记
仅供学习交流使用,转载注明出处
推荐
JDK API 1.6 中文版
说明
以下内容是结合很多资料进行编写的
源码为jdk1.8的
斜体样式 为自己的思考
下划线为自己所画的重点
ArrayList类
基本信息
java.util
类 ArrayList< E>
java.lang.Object
继承者 java.util.AbstractCollection< E>
继承者 java.util.AbstractList< E>
继承者 java.util.ArrayList< E>
所有已实现的接口:
Serializable, Cloneable, Iterable< E>, Collection< E>, List< E>, RandomAccess
直接已知子类:
AttributeList, RoleList, RoleUnresolvedList
public class ArrayList< E>
extends AbstractList< E>
implements List< E>, RandomAccess, Cloneable, SerializableList
接口的大小可变数组的实现。实现了所有可选列表操作,并允许包括 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.2
另请参见:
Collection, List, LinkedList, Vector, Collections.synchronizedList(List), 序列化表格
字段摘要
从类 java.util.AbstractList 继承的字段
modCount
构造方法摘要
ArrayList()
构造一个初始容量为 10 的空列表。
ArrayList(Collection<? extends E> c)
构造一个包含指定 collection 的元素的列表,这些元素是按照该 collection 的迭代器返回它们的顺序排列的。
ArrayList(int initialCapacity)
构造一个具有指定初始容量的空列表。
方法摘要
boolean add(E e)
将指定的元素添加到此列表的尾部。
boolean add(E e)
将指定的元素添加到此列表的尾部。
void add(int index, E element)
将指定的元素插入此列表中的指定位置。
boolean addAll(Collection<? extends E> c)
按照指定 collection 的迭代器所返回的元素顺序,将该 collection 中的所有元素添加到此列表的尾部。
boolean addAll(int index, Collection<? extends E> c)
从指定的位置开始,将指定 collection 中的所有元素插入到此列表中。
void clear()
移除此列表中的所有元素。
Object clone()
返回此 ArrayList 实例的浅表副本。
boolean contains(Object o)
如果此列表中包含指定的元素,则返回 true。
void ensureCapacity(int minCapacity)
如有必要,增加此 ArrayList 实例的容量,以确保它至少能够容纳最小容量参数所指定的元素数。
E get(int index)
返回此列表中指定位置上的元素。
int indexOf(Object o)
返回此列表中首次出现的指定元素的索引,或如果此列表不包含元素,则返回 -1。
boolean isEmpty()
如果此列表中没有元素,则返回 true
int lastIndexOf(Object o)
返回此列表中最后一次出现的指定元素的索引,或如果此列表不包含索引,则返回 -1。
E remove(int index)
移除此列表中指定位置上的元素。
boolean remove(Object o)
移除此列表中首次出现的指定元素(如果存在)。
protected void removeRange(int fromIndex, int toIndex)
移除列表中索引在 fromIndex(包括)和 toIndex(不包括)之间的所有元素。
E set(int index, E element)
用指定的元素替代此列表中指定位置上的元素。
int size()
返回此列表中的元素数。
Object[] toArray()
按适当顺序(从第一个到最后一个元素)返回包含此列表中所有元素的数组。
T[]
toArray(T[] a)
按适当顺序(从第一个到最后一个元素)返回包含此列表中所有元素的数组;返回数组的运行时类型是指定数组的运行时类型。
void trimToSize()
将此 ArrayList 实例的容量调整为列表的当前大小。
从类 java.util.AbstractList 继承的方法
equals, hashCode, iterator, listIterator, listIterator, subList
从类 java.util.AbstractCollection 继承的方法
containsAll, removeAll, retainAll, toString
从类 java.lang.Object 继承的方法
finalize, getClass, notify, notifyAll, wait, wait, wait
从接口 java.util.List 继承的方法
containsAll, equals, hashCode, iterator, listIterator, listIterator, removeAll, retainAll, subList
字段详细信息
java.util.AbstractList
modCount
protected transient int modCount已从结构上修改 此列表的次数。从结构上修改是指更改列表的大小,或者打乱列表,从而使正在进行的迭代产生错误的结果。
此字段由 iterator 和 listIterator 方法返回的迭代器和列表迭代器实现使用。如果意外更改了此字段中的值,则迭代器(或列表迭代器)将抛出 ConcurrentModificationException 来响应 next、remove、previous、set 或 add 操作。在迭代期间面临并发修改时,它提供了快速失败 行为,而不是非确定性行为。
子类是否使用此字段是可选的。如果子类希望提供快速失败迭代器(和列表迭代器),则它只需在其 add(int, E) 和 remove(int) 方法(以及它所重写的、导致列表结构上修改的任何其他方法)中增加此字段。对 add(int, E) 或 remove(int) 的单个调用向此字段添加的数量不得超过 1,否则迭代器(和列表迭代器)将抛出虚假的 ConcurrentModificationExceptions。如果某个实现不希望提供快速失败迭代器,则可以忽略此字段。
/** * 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;
构造方法详细信息
ArrayList
public ArrayList(int initialCapacity)构造一个具有指定初始容量的空列表。
参数:
initialCapacity - 列表的初始容量
抛出:
IllegalArgumentException - 如果指定的初始容量为负
ArrayList
public ArrayList()构造一个初始容量为 10 的空列表。
ArrayList
public ArrayList(Collection<? extends E> c)构造一个包含指定 collection 的元素的列表,这些元素是按照该 collection 的迭代器返回它们的顺序排列的。
参数:
c - 其元素将放置在此列表中的 collection
抛出:
NullPointerException - 如果指定的 collection 为 null
方法详细信息
trimToSize
public void trimToSize()
将此 ArrayList 实例的容量调整为列表的当前大小。应用程序可以使用此操作来最小化 ArrayList 实例的存储量。
/** * Trims the capacity of this <tt>ArrayList</tt> instance to be the * list's current size. An application can use this operation to minimize * the storage of an <tt>ArrayList</tt> instance. */ public void trimToSize() { modCount++; if (size < elementData.length) { elementData = (size == 0) ? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size); } }
ensureCapacity
public void ensureCapacity(int minCapacity)
如有必要,增加此 ArrayList 实例的容量,以确保它至少能够容纳最小容量参数所指定的元素数。
参数:
minCapacity - 所需的最小容量
/** * Increases the capacity of this <tt>ArrayList</tt> instance, if * necessary, to ensure that it can hold at least the number of elements * specified by the minimum capacity argument. * * @param minCapacity the desired minimum capacity */ public void ensureCapacity(int minCapacity) { int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) // any size if not default element table ? 0 // larger than default for default empty table. It's already // supposed to be at default size. : DEFAULT_CAPACITY; if (minCapacity > minExpand) { ensureExplicitCapacity(minCapacity); } }
private void ensureExplicitCapacity(int minCapacity) { modCount++; // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity); }
/** * 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;
/** * 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; }
add
public boolean add(E e)
将指定的元素添加到此列表的尾部。
指定者:
接口 Collection 中的 add
指定者:
接口 List 中的 add
覆盖:
类 AbstractList 中的 add
参数:
e - 要添加到此列表中的元素
返回:
true(按照 Collection.add(E) 的指定)
/** * 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; }
remove
public boolean remove(Object o)
移除此列表中首次出现的指定元素(如果存在)。如果列表不包含此元素,则列表不做改动。更确切地讲,移除满足 (o==null ? get(i)==null : o.equals(get(i))) 的最低索引的元素(如果存在此类元素)。如果列表中包含指定的元素,则返回 true(或者等同于这种情况:如果列表由于调用而发生更改,则返回 true)。
指定者:
接口 Collection 中的 remove
指定者:
接口 List 中的 remove
覆盖:
类 AbstractCollection 中的 remove
参数:
o - 要从此列表中移除的元素(如果存在)
返回:
如果此列表包含指定的元素,则返回 true
/** * 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; }
/** * Checks if the given index is in range. If not, throws an appropriate * runtime exception. This method does *not* check if the index is * negative: It is always used immediately prior to an array access, * which throws an ArrayIndexOutOfBoundsException if index is negative. */ private void rangeCheck(int index) { if (index >= size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); }
iterator
public Iterator iterator()返回以恰当顺序在此列表的元素上进行迭代的迭代器。
此实现返回 iterator 接口的一个直接实现,具体取决于底层实现列表的 size()、get(int) 和 remove(int) 方法。
注意,除非重写列表的 remove(int) 方法,否则此方法返回的迭代器将抛出一个 UnsupportedOperationException 来响应其 remove 方法。
根据 (protected) modCount 字段规范中的描述,在面临并发修改时,可以使此实现抛出运行时异常。
指定者:
接口 Iterable 中的 iterator
指定者:
接口 Collection 中的 iterator
指定者:
接口 List 中的 iterator
指定者:
类 AbstractCollection 中的 iterator
返回:
在此 collection 中的元素上进行迭代的迭代器。
另请参见:
modCount
/** * 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(); }
/** * 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(); } }
总结
关键词:
- ensureCapacity
- 不同步的
- public ArrayList()
- 构造一个初始容量为 10 的空列表。
- add
- remove
- iterator
- 快速失败
最后
开源=为爱发电