- 成员变量
- 序列化号
private static final long serialVersionUID = 8683452581122892189L;
2.默认初始化容量 10
private static final int DEFAULT_CAPACITY = 10;
3.用于空实例的共享空数组实例
当ArrayList的构造方法中显示指出ArrayList的数组长度为0时,类内部将
EMPTY_ELEMENTDATA
这个空对象数组赋给elemetData数组。
private static final Object[] EMPTY_ELEMENTDATA = {};
4.用于默认大小的空实例的共享空数组实例。
将其与EMPTY_ELEMENTDATA
区分开来,以了解在添加第一个元素时应该扩充多少。当ArrayList的构造方法中没有显示指出ArrayList的数组长度时,类内部使用默认缺省时对象数组为DEFAULTCAPACITY_EMPTY_ELEMENTDATA
。
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
5.存储ArrayList元素的数组缓冲区。
ArrayList的容量是这个数组缓冲区的长度。当添加第一个元素时,任何带有elementData
==DEFAULTCAPACITY_EMPTY_ELEMENTDATA
的空ArrayList都将被扩展为DEFAULT_CAPACITY
。
ArrayList的底层数据结构,只是一个对象数组,用于存放实际元素,并且被标记为transient
,也就意味着在序列化的时候此字段是不会被序列化
transient Object[] elementData;
6.大小
实际ArrayList中存放的元素的个数,默认时为0个元素。
private int size;
7.要分配的数组的最大大小。
一些jvm在数组中保留一些标题词。
试图分配更大的数组可能会导致OutOfMemoryError:
请求的数组大小超过VM限制
java int 的最大值Integer.MAX_VALUE
是2147483647
ArrayList中的对象数组的最大数组容量为Integer.MAX_VALUE – 8
。
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
- 构造方法
1 无参构造
/**
* Constructs an empty list with an initial capacity of ten.
* 构造一个初始容量为10的空列表。
* 在该方法中没有对数组长度进行设置,后续在add方法中才去进行扩容
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
2 有参构造_传入容量大小
/**
* 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) { // 初始容量大于0
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
// 将EMPTY_ELEMENTDATA空对象数组赋给elementData。
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
3 有参构造_传入集合
/**
* 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)
// 这个注释,参见bug6260652,toArray方法确实有时候返回的不是Obdect[]
// List<String> strList= Arrays.asList("abc");返回的结果是String[]
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
解析:
第一步,将参数中的集合转化为数组赋给elementData;
第二步,判断参数集合转换后的数组长度是否为0。并把该数组长度的大小赋值给size。
第三步,如果该数组长度为0,则设置元素数组为空,即将EMPTY_ELEMENTDATA空对象数组赋给elementData;
第四步,如果该数组长度不为0,接下来判断是否成功将参数集合转化为Object类型的数组,
如果转化成Object类型的数组成功,则将数组进行复制,转化为Object类型的数组。
- 方法
1 调整容量大小
将这个ArrayList实例的容量调整为列表的当前大小。
可以使用此操作最小化ArrayList实例的存储。
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
//elementData:要复制的数组;size:要复制的长度
: Arrays.copyOf(elementData, size);
}
}
这个modCount是父类抽象类的方法,防止在迭代过程中并发修改的不确定性行为。
2.预先设置list的大小
每当向数组中添加元素时,都要去检查添加后元素的个数是否会超出当前数组的长度,
如果超出,数组将会进行扩容,以满足添加数据的需求。
每次数组容量的增长大约是其原容量的1.5倍。对数组扩容是要进行数组拷贝的,这就会浪费大量的时间。如果已经预知容器可能会装多少元素,最好显式的调用ensureCapacity这个方法一次性扩容到位。
public void ensureCapacity(int minCapacity) {
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
// any size if not default element table
// 任何大小,如果不是默认的元素表
// 判断需要扩容的数组是否为默认空实例(空数组)
// 如果不为默认空实例,则变量等于0.为默认空实例则变量等于数组默认容量 10
? 0
// larger than default for default empty table. It's already
// supposed to be at default size.
: DEFAULT_CAPACITY;
// 如果该数组是默认空实例,则指定变量minExpand = DEFAULT_CAPACITY:10
// 因此,当期望扩容的量小于10 的时候,就不需要扩容
// 因为默认空实例的默认容量就是10,已经满足期望扩容的量
if (minCapacity > minExpand) {
// 如果需要扩容的量大于定义的变量,则继续判断是否需要扩容
ensureExplicitCapacity(minCapacity);
}
}
3 添加方法
将指定的元素附加到此列表的末尾。
public boolean add(E e) {
// 确保添加元素成功的最小集合容量
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
// 确定集合内部容量。
// 这个方法很有意思,先计算容量大小,再确定是否要进行扩容,
// 最终达成预先设置list的大小。与2方法相似
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
// 计算容量
// 如果当前集合elementData对象是默认空实例DEFAULTCAPACITY_EMPTY_ELEMENTDATA
// 则将参数minCapacity和DEFAULT_CAPACITY比较,取最大
// 否则取参数minCapacity
private static int calculateCapacity(Object[] elementData, int minCapacity) {
// 如果这个elementData 是默认大小的空实例的共享空数组实例,
// 那么参数minCapacity容量和默认值10比较,取最大值
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
// 否则取参数minCapacity
return minCapacity;
}
// 确定是否需要扩容
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
// 如果指定容量大于当前集合的长度,就要扩容
if (minCapacity - elementData.length > 0)
// 真正的扩容方法
grow(minCapacity);
}
// 真正的扩容方法
private void grow(int minCapacity) {
// overflow-conscious code 获得旧的容量大小值
int oldCapacity = elementData.length;
// 新的容量 = 旧的容量 + (旧的容量 / 2) 也就是大概扩容1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果新的容量比期望容量小,那么期望容量为新的容量
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 如果新的容量超过最大范围,则调用hugeCapacity方法去决定新的容量的大小
// private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
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);
}
// 确保不小于0并且不超过最大容量
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
//Integer.MAX_VALUE - 8;
MAX_ARRAY_SIZE;
}
/**
* Arrays的方法
* Copies the specified array, truncating or padding with nulls (if necessary)
* so the copy has the specified length. For all indices that are
* valid in both the original array and the copy, the two arrays will
* contain identical values. For any indices that are valid in the
* copy but not the original, the copy will contain <tt>null</tt>.
* Such indices will exist if and only if the specified length
* is greater than that of the original array.
* The resulting array is of exactly the same class as the original array.
*
* @param <T> the class of the objects in the array
* @param original the array to be copied
* @param newLength the length of the copy to be returned
* @return a copy of the original array, truncated or padded with nulls
* to obtain the specified length
* @throws NegativeArraySizeException if <tt>newLength</tt> is negative
* @throws NullPointerException if <tt>original</tt> is null
* @since 1.6
*/
@SuppressWarnings("unchecked")
public static <T> T[] copyOf(T[] original, int newLength) {
return (T[]) copyOf(original, newLength, original.getClass());
}
/**
* Arrays的方法
* Copies the specified array, truncating or padding with nulls (if necessary)
* so the copy has the specified length. For all indices that are
* valid in both the original array and the copy, the two arrays will
* contain identical values. For any indices that are valid in the
* copy but not the original, the copy will contain <tt>null</tt>.
* Such indices will exist if and only if the specified length
* is greater than that of the original array.
* The resulting array is of the class <tt>newType</tt>.
*
* @param <U> the class of the objects in the original array
* @param <T> the class of the objects in the returned array
* @param original the array to be copied
* @param newLength the length of the copy to be returned
* @param newType the class of the copy to be returned
* @return a copy of the original array, truncated or padded with nulls
* to obtain the specified length
* @throws NegativeArraySizeException if <tt>newLength</tt> is negative
* @throws NullPointerException if <tt>original</tt> is null
* @throws ArrayStoreException if an element copied from
* <tt>original</tt> is not of a runtime type that can be stored in
* an array of class <tt>newType</tt>
* @since 1.6
*/
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
@SuppressWarnings("unchecked")
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
return copy;
}
/**
* System的方法
* Copies an array from the specified source array, beginning at the
* specified position, to the specified position of the destination array.
* A subsequence of array components are copied from the source
* array referenced by <code>src</code> to the destination array
* referenced by <code>dest</code>. The number of components copied is
* equal to the <code>length</code> argument. The components at
* positions <code>srcPos</code> through
* <code>srcPos+length-1</code> in the source array are copied into
* positions <code>destPos</code> through
* <code>destPos+length-1</code>, respectively, of the destination
* array.
* <p>
* If the <code>src</code> and <code>dest</code> arguments refer to the
* same array object, then the copying is performed as if the
* components at positions <code>srcPos</code> through
* <code>srcPos+length-1</code> were first copied to a temporary
* array with <code>length</code> components and then the contents of
* the temporary array were copied into positions
* <code>destPos</code> through <code>destPos+length-1</code> of the
* destination array.
* <p>
* If <code>dest</code> is <code>null</code>, then a
* <code>NullPointerException</code> is thrown.
* <p>
* If <code>src</code> is <code>null</code>, then a
* <code>NullPointerException</code> is thrown and the destination
* array is not modified.
* <p>
* Otherwise, if any of the following is true, an
* <code>ArrayStoreException</code> is thrown and the destination is
* not modified:
* <ul>
* <li>The <code>src</code> argument refers to an object that is not an
* array.
* <li>The <code>dest</code> argument refers to an object that is not an
* array.
* <li>The <code>src</code> argument and <code>dest</code> argument refer
* to arrays whose component types are different primitive types.
* <li>The <code>src</code> argument refers to an array with a primitive
* component type and the <code>dest</code> argument refers to an array
* with a reference component type.
* <li>The <code>src</code> argument refers to an array with a reference
* component type and the <code>dest</code> argument refers to an array
* with a primitive component type.
* </ul>
* <p>
* Otherwise, if any of the following is true, an
* <code>IndexOutOfBoundsException</code> is
* thrown and the destination is not modified:
* <ul>
* <li>The <code>srcPos</code> argument is negative.
* <li>The <code>destPos</code> argument is negative.
* <li>The <code>length</code> argument is negative.
* <li><code>srcPos+length</code> is greater than
* <code>src.length</code>, the length of the source array.
* <li><code>destPos+length</code> is greater than
* <code>dest.length</code>, the length of the destination array.
* </ul>
* <p>
* Otherwise, if any actual component of the source array from
* position <code>srcPos</code> through
* <code>srcPos+length-1</code> cannot be converted to the component
* type of the destination array by assignment conversion, an
* <code>ArrayStoreException</code> is thrown. In this case, let
* <b><i>k</i></b> be the smallest nonnegative integer less than
* length such that <code>src[srcPos+</code><i>k</i><code>]</code>
* cannot be converted to the component type of the destination
* array; when the exception is thrown, source array components from
* positions <code>srcPos</code> through
* <code>srcPos+</code><i>k</i><code>-1</code>
* will already have been copied to destination array positions
* <code>destPos</code> through
* <code>destPos+</code><i>k</I><code>-1</code> and no other
* positions of the destination array will have been modified.
* (Because of the restrictions already itemized, this
* paragraph effectively applies only to the situation where both
* arrays have component types that are reference types.)
*
* @param src the source array.
* @param srcPos starting position in the source array.
* @param dest the destination array.
* @param destPos starting position in the destination data.
* @param length the number of array elements to be copied.
* @exception IndexOutOfBoundsException if copying would cause
* access of data outside array bounds.
* @exception ArrayStoreException if an element in the <code>src</code>
* array could not be stored into the <code>dest</code> array
* because of a type mismatch.
* @exception NullPointerException if either <code>src</code> or
* <code>dest</code> is <code>null</code>.
*/
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);
扩容机制:
第一,在add()方法中调用ensureCapacityInternal(size + 1)方法来确定集合确保添加元素成功的最小集合容量minCapacity的值。参数size+1,代表集合添加元素成功后,集合中的实际元素个数。
在ensureCapacityInternal方法中,首先判断elementData是否为默认的空数组,如果是,minCapacity为minCapacity与集合默认容量大小中的较大值。否则直接返回minCapacity
第二,调用ensureExplicitCapacity(minCapacity)方法来确定集合为了确保添加元素成功是否需要对现有的元素数组进行扩容。首先将结构性修改计数器modCount加一;然后判断minCapacity与当前元素数组的长度的大小,如果minCapacity比当前元素数组的长度的大的时候则需要扩容,进入第三阶段。
第三,如果需要对现有的元素数组进行扩容,则调用grow(minCapacity)方法,参数minCapacity表示集合为了确保添加元素成功的最小容量。在扩容的时候,首先将原元素数组的长度增大1.5倍(oldCapacity + (oldCapacity >> 1)),然后对扩容后的容量与minCapacity进行比较:
①新容量小于minCapacity,则将minCapacity设为新容量;
②新容量大于minCapacity,则指定新容量。
③最后将旧数组拷贝到扩容后的新数组中。
- 下面分析用无参构造函数实例并添加元素都做了些什么
- List list = new ArrayList<>();
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* Constructs an empty list with an initial capacity of ten.
* 构造一个初始容量为10的空列表。
* 在该方法中没有对数组长度进行设置,后续在add方法中才去进行扩容
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
首先是先构建一个初始容量为10的空的列表,即:this.elementData = {};
- list.add("a");
再次把代码贴下来方便查看
private int size;
public boolean add(E e) { // e = "a"
// 第一步:确保添加元素成功的最小集合容量
ensureCapacityInternal(size + 1); // size + 1 = 0 + 1 = 1
elementData[size++] = e;
return true;
}
// 第二步:确定集合内部容量。
private void ensureCapacityInternal(int minCapacity) { // minCapacity = 1
// ensureExplicitCapacity(calculateCapacity( {} , 1 ));
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
// 第三步:计算容量
private static int calculateCapacity(Object[] elementData, int minCapacity) { // {} , 1
// 这个elementData 是默认大小的空实例的共享空数组实例 {},
// DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// DEFAULT_CAPACITY = 10, minCapacity = 1;
// 所以指定的minCapacity容量和默认值10比较,取最大值 10
// 并返回给 ensureExplicitCapacity
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
// 否则取传入的minCapacity
return minCapacity;
}
// 第四步:确定是否需要扩容
// 拿到 minCapacity = calculateCapacity 返回的 10
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
// 指定容量大于当前集合的长度,所以要扩容
if (minCapacity - elementData.length > 0) // 10 - 0
// 真正的扩容方法
grow(minCapacity); // minCapacity = 10
}
// 第五步:真正的扩容方法
private void grow(int minCapacity) { // 扩容指定容量 minCapacity = 10
// overflow-conscious code 获得旧的容量大小值
int oldCapacity = elementData.length; // 该元素是空集合,所以长度是 0;
// 新的容量 = 旧的容量 + (旧的容量 / 2) 因为实际上是位运算,即大概扩容1.5倍
// newCapacity = 0 + (0 / 2) = 0;
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 新的容量 0 比期望容量 10 小,那么期望容量 10 为新的容量
if (newCapacity - minCapacity < 0) // 0 - 10
newCapacity = minCapacity; // newCapacity = 10
// 如果新的容量超过最大范围,则调用hugeCapacity方法去决定新的容量的大小
// private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
// 10 - Integer.MAX_VALUE - 8;肯定是小于0,所以不走这个方法体
if (newCapacity - MAX_ARRAY_SIZE > 0)
// 注意传参的是指定容量,也就是指定容量与最大容量比较
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
// 最后走到这个方法:调用 Arrays.copyOf 方法进行数组拷贝。
elementData = Arrays.copyOf(elementData, newCapacity); // {},10
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
//Integer.MAX_VALUE - 8;
MAX_ARRAY_SIZE;
}
// Arrays的copyOf方法
public static <T> T[] copyOf(T[] original, int newLength) { // {},10
// copyOf( { }, 10, Object类型 );
return (T[]) copyOf(original, newLength, original.getClass());
}
public static <T,U> T[] copyOf(U[] original, int newLength,
Class<? extends T[]> newType) { // { }, 10, Object类型
@SuppressWarnings("unchecked")
T[] copy = ((Object)newType == (Object)Object[].class) // 是Object类型,所以能够转换成功
// 因此创建新的数组,且指定长度为10
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
// 然后走 System.arraycopy 方法,旧数组元素拷贝到新数组上
// System.arraycopy({}, 0, new Object[10], 0, Math.min(0, 10));
// 截取的个数这样取值 Math.min(original.length, newLength)
// 表示要同时满足:1 源数组的总数范围内,2 目标数组的容量范围内
// 如果源数组的总数长过目标数组的容量,源数组超出的部分将不拷贝
// 如果目标数组的容量大于源数组的总数,目标数组超出的部分为null
// 如果目标数组原本有值,则超出部分的值不变
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
return copy;
}
// System.arraycopy 方法
// System.arraycopy({}, 0, new Object[10], 0, 0);
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);
System.arraycopy 方法解释:
src:源数组;
srcPos:源数组要复制的起始位置;
dest:目的数组;
destPos:目的数组放置的起始位置;
length:复制的长度。
注意:src and dest都必须是同类型或者可以进行转换类型的数组.
比如 :
int arry1[] = { 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 };
int arry2[] = { 15, 25, 35, 45, 55, 65, 75, 85, 95, 105 };
source_arr = arry1;
sourcePos = 3;
dest_arr = arry2;
destPos = 5;
len = 4;
System.arraycopy(source_arr, sourcePos, dest_arr, destPos, len);
// System.arraycopy(arry1, 3, arry2, 5, 4);
// 意思是截取arry1从下标为3开始4个元素:40, 50, 60, 70
// 把它们放到arry2的下标为5的位置及其后面(覆盖掉原索引位的值)
System.out.print("final dest_array : ");
for (int i = 0; i < arry2.length; i++)
System.out.print(arry2[i] + " ");
}
结果:
final dest_array : 15 25 35 45 55 40 50 60 70 105
4 获取当前集合大小
public int size() {
return size;
}
5 判断集合是否为空
public boolean isEmpty() {
return size == 0;
}
6 判断元素对象是否存在集合当中
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
7 从头开始循环遍历,找到集合相同的元素
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;
}
8 尾部循环遍历,找到集合相同的元素
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;
}
9 浅拷贝(元素本身不会被复制)
public Object clone() {
try {
ArrayList<?> v = (ArrayList<?>) super.clone();
v.elementData = Arrays.copyOf(elementData, size);
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError(e);
}
}
10 集合转换成数组_无参
// 和扩容方法grow最后调用的方法是相同的:Arrays.copyOf(elementData, newCapacity);
// 但是传入的参数不同,grow方法传入的是指定大小,它传入的是元素实际个数size
// 返回的数组将是“安全的”,因为toArray()返回的是一个新的数组对象,List不维护对它的引用。
// 换句话说,这个方法必须分配一个新数组。
// 因此,调用者可以自由地修改返回的数组,
// 不会影响到list本身原来存储的元素值,并且不会影响到其他toArray()方法获得的数组。
// 此方法充当基于数组和基于集合的api之间的桥梁。
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
但是,如果该集合里面有其它自定义类型的元素,例如一个person类,如果对这个对象元素内容修改,则会影响到List本身的内容,导致toArray()返回的所有数组中的内容都发生改变(原理参考Cloneable接口的深浅拷贝,即List存储的只是该对象的地址指针,实际并没有对该对象进行拷贝)
- 再贴出拷贝方法具体实现
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
public static <T> T[] copyOf(T[] original, int newLength) {
return (T[]) copyOf(original, newLength, original.getClass());
}
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
@SuppressWarnings("unchecked")
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
return copy;
}
public static Object newInstance(Class<?> componentType, int length)
throws NegativeArraySizeException {
return newArray(componentType, length);
}
private static native Object newArray(Class<?> componentType, int length)
throws NegativeArraySizeException;
System.arraycopy 方法解释:
src:源数组;
srcPos:源数组要复制的起始位置;
dest:目的数组;
destPos:目的数组放置的起始位置;
length:复制的长度。
注意:src and dest都必须是同类型或者可以进行转换类型的数组.
比如 :
int arry1[] = { 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 };
int arry2[] = { 15, 25, 35, 45, 55, 65, 75, 85, 95, 105 };
source_arr = arry1;
sourcePos = 3;
dest_arr = arry2;
destPos = 5;
len = 4;
System.arraycopy(source_arr, sourcePos, dest_arr, destPos, len);
// System.arraycopy(arry1, 3, arry2, 5, 4);
// 意思是截取arry1从下标为3开始4个元素:40, 50, 60, 70
// 把它们放到arry2的下标为5的位置及其后面(覆盖掉原索引位的值)
System.out.print("final dest_array : ");
for (int i = 0; i < arry2.length; i++)
System.out.print(arry2[i] + " ");
}
结果:
final dest_array : 15 25 35 45 55 40 50 60 70 105
11 集合转换成数组_有参
@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,size就是list集合中元素的个数,
// 这个null值可以使得toArray(T[] a)方法调用者可以判断null后面已经没有list元素了。
a[size] = null;
// 数组长度等于集合长度
return a;
}
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
@SuppressWarnings("unchecked")
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
return copy;
}
两个方法简单总结:
1.toArray()无参方法,可以直接将集合转换成Object数组进行返回(返回List中所有元素构成的数组,并且数组类型是Object[]。)
2.toArray(T[] a)有参方法,需要传入一个数组作为参数,并通过泛型T的方式定义参数,所返回的数组类型就是调用集合者的泛型,所以自己无需再转型;但是根据传入数组的长度与集合的实际长度的关系,会有不同的处理;
a:数组长度不小于集合长度,直接拷贝,不会产生新的数组对象;
b:数组长度小于集合长度,会创建一个与集合长度相同的新数组,将集合的数据拷贝到新数组并将新数组的引用返回。如果a数组还有剩余的空间,则在a[size]放置一个null,size就是list中元素的个数,这个null值可以使得toArray(T[] a)方法调用者可以判断null后面已经没有list元素了。
c:两种情况的拷贝方式是一样的,只是有一种情况会产生新的数组实例
12 位置访问
E elementData(int index) {
return (E) elementData[index];
}
13 返回指定位置的元素
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
14 将集合中指定位置的元素替换为指定元素。返回的是被修改前的元素
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
15 将指定元素插入到列表中的指定位置。如果该索引处以及后面都有元素,那么将它们索引都往后移一位
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
// elementData = Arrays.copyOf(elementData, newCapacity); // size + 1
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
// 由add和addAll使用的rangeCheck的一个版本。
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
// System.arraycopy是一个原生的方法,用于数组间的复制,延伸功能完成数组替换
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);
5个参数,
第一个参数是要被复制的数组
第二个参数是被复制的数字开始复制的下标
第三个参数是目标数组,也就是要把数据放进来的数组
第四个参数是从目标数据第几个下标开始放入数据
第五个参数表示从被复制的数组中拿几个数值放到目标数组中
- 再贴出确保容量的具体实现
// 确定集合内部容量。
// 这个方法很有意思,先计算容量大小,再确定是否要进行扩容,
// 最终达成预先设置list的大小。与2方法相似(预先设置list的大小)
private void ensureCapacityInternal(int minCapacity) { // size + 1
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
// 计算容量
// 如果当前集合elementData对象是默认空实例DEFAULTCAPACITY_EMPTY_ELEMENTDATA
// 则将参数minCapacity和DEFAULT_CAPACITY比较,取最大
// 否则取参数minCapacity
private static int calculateCapacity(Object[] elementData, int minCapacity) {
// 如果这个elementData 是默认大小的空实例的共享空数组实例,
// 那么参数minCapacity容量和默认值10比较,取最大值
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
// 否则取参数minCapacity
return minCapacity; // size + 1
}
// 确定是否需要扩容
private void ensureExplicitCapacity(int minCapacity) { // size + 1
modCount++;
// overflow-conscious code
// 如果指定容量大于当前集合的长度,就要扩容
if (minCapacity - elementData.length > 0)
// 真正的扩容方法
grow(minCapacity); // size + 1
}
// 真正的扩容方法
private void grow(int minCapacity) { // size + 1
// overflow-conscious code 获得旧的容量大小值
int oldCapacity = elementData.length;
// 新的容量 = 旧的容量 + (旧的容量 / 2) 也就是大概扩容1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果新的容量比期望容量小,那么期望容量为新的容量
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity; // size + 1
// 如果新的容量超过最大范围,则调用hugeCapacity方法去决定新的容量的大小
// private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
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); // size + 1
}
// 确保不小于0并且不超过最大容量
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
//Integer.MAX_VALUE - 8;
MAX_ARRAY_SIZE;
}
public static <T> T[] copyOf(T[] original, int newLength) { // size + 1
return (T[]) copyOf(original, newLength, original.getClass());
}
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
@SuppressWarnings("unchecked")
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
return copy;
}
16 删除的代码因为不涉及到扩容,所以比起add较为简单,首先会检查数组是否下标越界,然后会获取指定位置的元素,接着进行数据的搬移,将--size位置的元素置成null,让GC进行回收。最后将目标元素返回即可。
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;
}
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
}
17 清空元素
public void clear() {
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
18 将指定集合中的所有元素按照指定集合的迭代器返回它们的顺序追加到此列表的末尾
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
19 删除指定范围的元素
protected void removeRange(int fromIndex, int toIndex) {
modCount++;
int numMoved = size - toIndex;
System.arraycopy(elementData, toIndex, elementData, fromIndex,
numMoved);
// clear to let GC do its work
int newSize = size - (toIndex-fromIndex);
for (int i = newSize; i < size; i++) {
elementData[i] = null;
}
size = newSize;
}
20 从该列表中删除指定集合中包含的所有元素
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, false);
}
public static <T> T requireNonNull(T obj) {
if (obj == null)
throw new NullPointerException();
return obj;
}
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;
}
分析批量删除方法都做了啥:
1.Objects.requireNonNull(c);判断非空
2.return batchRemove(c, false);调用私有方法去删除
3.来到 batchRemove(Collection<?> c, boolean complement)
说明两个参数:
Collection<?> c = c;要删除的集合
boolean complement = false;
是作为elementData数组元素不在集合c的标志。(即需要保留的数组元素)
当complement为true时,求list中与collection的并集。
当complement为false时,求list与collection的差集。
4.final Object[] elementData = this.elementData;被final修饰的变量,不可变的是变量的引用,而不是变量的内容
5.boolean modified = false;
6.遍历数组elementData
if (c.contains(elementData[r]) == complement)
表示elementData[r]不在要删除的集合内,则把这些需要保留的元素elementData[r],重置到数组本身(从0开始)elementData[w++]
7.接下来走finally方法
r != size;表示判断r是否会等于size。如果说前面的代码不停止的话,那么最后r会将ArrayList里面的元素全部遍历完毕,最后r的值会等于size的值,并且跳出前面那个for循环。
如果r不等于size:
System.arraycopy(elementData, r,elementData, w, size - r);
表示elementData从r索引开始,截取size-r个元素,然后把截取的所有元素从w开始赋值到elementData
也就是说,如果数组elementData没有遍历完就跳出了循环,把剩下没遍历完的当作不需要删除的数组元素,放到保留的数组元素的数组后面。
如果r等于size:
继续判断,如果w不等于size:
也就是说,原数组elementData已经遍历完,w不等于size表示集合c存在要删除的数组元素
则从w开始遍历,即在w往后的元素都置空elementData[i] = null;让GC去工作
8.modCount += size - w;
9.修改数组大小:size = w;
10.modified = true;
11.最后返回modified
- 小结:
finally里面的代码块是暂存作用,为什么只有(r!=size)的时候才去执行里面的代码块?明明try代码块里面的r最后肯定会是r=size才会跳出for循环的。那么为什么后面也要设置一个(w!=size)的判定呢?我们假设前面的直接走完了,并没有走(r!=size)里面的代码,此时有两种情况,
刚好w=size,没有执行(w!=size)里面的代码,
此时modified=false,我们就知道,ArrayList里面的数据并没有发生改动。
另外一种情况,执行了(w!=size)里面的代码,最后size=w。
什么情况会中断for循环呢?
writeObject方法,传递的参数是一个ObjectOutputStream对象,这是一个写入流,在注释中也对这个方法进行了解释,将ArrayList的状态保存进流里面。
此时,我们多次看到过的modCount就起到作用了,先定义了一个expectedModCount用来保存它。然后执行默认的序列化操作,然后将大小写入进去,然后通过for循环把所有元素按照正确的顺序写入进去。
每当ArrayList里面的内容被改动过的时候,modCount都会增加,if (modCount != expectedModCount)的判断是为了确保,当把ArrayList里面的数据写入流里面的时候是最新数据。如果在写入流的过程中,数据发生了变化,那么这个数据就不是最新的数据,那么就抛出错误ConcurrentModificationException()。
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
// Write out element count, and any hidden stuff
int expectedModCount = modCount;
s.defaultWriteObject();
// Write out size as capacity for behavioural compatibility with clone()
s.writeInt(size);
// Write out all elements in the proper order.
for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
21 保留集合的所有元素
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;
}
分析它都做了啥:
1.调用的方法跟removeAll调用的一样:batchRemove
2.但是,传入的一个参数不一样,就是complement这里为true;表示该集合c的元素需要保留
3.那么,遍历数组元素,if (c.contains(elementData[r]) == complement)表示该元素在集合内:
则把这些需要保留的元素elementData[r],重置到数组本身(从0开始)elementData[w++]
【因此可以分析得出,无论是removeAll还是retainAll,都是通过控制complement为true或者false来筛选出需要保留的元素重置到elementData[w++]】
4.接下来的步骤和removeAll的分析一致,就不做赘述