共计 18489 个字符，预计需要花费 47 分钟才能阅读完成。
ArrayList 简介
ArrayList 的底层是数组队列，相当于动静数组。与 Java 中的数组相比，它的容量能动静增长。在增加大量元素前，应用程序能够应用 ensureCapacity 操作来减少 ArrayList 实例的容量。这能够缩小递增式再调配的数量。
ArrayList继承于 AbstractList，实现了 List, RandomAccess, Cloneable, java.io.Serializable 这些接口。
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable{}
复制代码RandomAccess是一个标记接口 (空接口)，表明实现这个这个接口的 List 汇合是反对 疾速随机拜访 的。在ArrayList中，咱们即能够通过元素的序号疾速获取元素对象，这就是疾速随机拜访。(起因是：底层是应用 Object[]数组存储数据的)ArrayList实现了Cloneable接口，即笼罩了函数clone()，能被克隆。ArrayList实现了java.io.Serializable接口，这意味着ArrayList反对序列化，能通过序列化去传输。
《2020 最新 Java 根底精讲视频教程和学习路线！》
ArrayList 外围源码解读
JDK1.8 版本
package java.util;
import java.util.function.Consumer;
import java.util.function.Predicate;
import java.util.function.UnaryOperator;
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
private static final long serialVersionUID = 8683452581122892189L;
/**
* 默认初始容量大小
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 空数组（用于空实例）。*/
private static final Object[] EMPTY_ELEMENTDATA = {};
// 用于默认大小空实例的共享空数组实例。// 咱们把它从 EMPTY_ELEMENTDATA 数组中辨别进去，以晓得在增加第一个元素时容量须要减少多少。private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* 保留 ArrayList 数据的数组
*/
transient Object[] elementData; // non-private to simplify nested class access
/**
* ArrayList 所蕴含的元素个数
*/
private int size;
/**
* 带初始容量参数的构造函数（用户能够在创立 ArrayList 对象时本人指定汇合的初始大小）*/
public ArrayList(int initialCapacity) {if (initialCapacity > 0) {
// 如果传入的参数大于 0，创立 initialCapacity 大小的数组
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
// 如果传入的参数等于 0，创立空数组
this.elementData = EMPTY_ELEMENTDATA;
} else {
// 其余状况，抛出异样
throw new IllegalArgumentException("Illegal Capacity:"+
initialCapacity);
}
}
/**
* 默认无参构造函数
*DEFAULTCAPACITY_EMPTY_ELEMENTDATA 为 0. 初始化为 10，也就是说初始其实是空数组 当增加第一个元素的时候数组容量才变成 10
*/
public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}
/**
* 结构一个蕴含指定汇合的元素的列表，依照它们由汇合的迭代器返回的程序。*/
public ArrayList(Collection<? extends E> c) {
// 将指定汇合转换为数组
elementData = c.toArray();
// 如果 elementData 数组的长度不为 0
if ((size = elementData.length) != 0) {
// 如果 elementData 不是 Object 类型数据（c.toArray 可能返回的不是 Object 类型的数组所以加上上面的语句用于判断）if (elementData.getClass() != Object[].class)
// 将原来不是 Object 类型的 elementData 数组的内容，赋值给新的 Object 类型的 elementData 数组
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// 其余状况，用空数组代替
this.elementData = EMPTY_ELEMENTDATA;
}
}
/**
* 批改这个 ArrayList 实例的容量是列表的以后大小。应用程序能够应用此操作来最小化 ArrayList 实例的存储。*/
public void trimToSize() {
modCount++;
if (size < elementData.length) {elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
// 上面是 ArrayList 的扩容机制
//ArrayList 的扩容机制进步了性能，如果每次只裁减一个，// 那么频繁的插入会导致频繁的拷贝，升高性能，而 ArrayList 的扩容机制防止了这种状况。/**
* 如有必要，减少此 ArrayList 实例的容量，以确保它至多能包容元素的数量
* @param minCapacity 所需的最小容量
*/
public void ensureCapacity(int minCapacity) {
// 如果是 true，minExpand 的值为 0，如果是 false,minExpand 的值为 10
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 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 办法进行扩容，调用此办法代表曾经开始扩容了
grow(minCapacity);
}
/**
* 要调配的最大数组大小
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/**
* ArrayList 扩容的外围办法。*/
private void grow(int minCapacity) {
// oldCapacity 为旧容量，newCapacity 为新容量
int oldCapacity = elementData.length;
// 将 oldCapacity 右移一位，其成果相当于 oldCapacity /2，// 咱们晓得位运算的速度远远快于整除运算，整句运算式的后果就是将新容量更新为旧容量的 1.5 倍，int newCapacity = oldCapacity + (oldCapacity >> 1);
// 而后查看新容量是否大于最小须要容量，若还是小于最小须要容量，那么就把最小须要容量当作数组的新容量，if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 再查看新容量是否超出了 ArrayList 所定义的最大容量，// 若超出了，则调用 hugeCapacity()来比拟 minCapacity 和 MAX_ARRAY_SIZE，// 如果 minCapacity 大于 MAX_ARRAY_SIZE，则新容量则为 Interger.MAX_VALUE，否则，新容量大小则为 MAX_ARRAY_SIZE。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);
}
// 比拟 minCapacity 和 MAX_ARRAY_SIZE
private static int hugeCapacity(int minCapacity) {if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
/**
* 返回此列表中的元素数。*/
public int size() {return size;}
/**
* 如果此列表不蕴含元素，则返回 true。*/
public boolean isEmpty() {
// 留神 = 和 == 的区别
return size == 0;
}
/**
* 如果此列表蕴含指定的元素，则返回 true。*/
public boolean contains(Object o) {//indexOf()办法：返回此列表中指定元素的首次呈现的索引，如果此列表不蕴含此元素，则为 -1
return indexOf(o) >= 0;
}
/**
* 返回此列表中指定元素的首次呈现的索引，如果此列表不蕴含此元素，则为 -1
*/
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++)
//equals()办法比拟
if (o.equals(elementData[i]))
return i;
}
return -1;
}
/**
* 返回此列表中指定元素的最初一次呈现的索引，如果此列表不蕴含元素，则返回 -1。.
*/
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;
}
/**
* 返回此 ArrayList 实例的浅拷贝。（元素自身不被复制。）*/
public Object clone() {
try {ArrayList<?> v = (ArrayList<?>) super.clone();
//Arrays.copyOf 性能是实现数组的复制，返回复制后的数组。参数是被复制的数组和复制的长度
v.elementData = Arrays.copyOf(elementData, size);
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) {
// 这不应该产生，因为咱们是能够克隆的
throw new InternalError(e);
}
}
/**
* 以正确的程序（从第一个到最初一个元素）返回一个蕴含此列表中所有元素的数组。* 返回的数组将是“平安的”，因为该列表不保留对它的援用。（换句话说，这个办法必须调配一个新的数组）。* 因而，调用者能够自在地批改返回的数组。此办法充当基于阵列和基于汇合的 API 之间的桥梁。*/
public Object[] toArray() {return Arrays.copyOf(elementData, size);
}
/**
* 以正确的程序返回一个蕴含此列表中所有元素的数组（从第一个到最初一个元素）;
* 返回的数组的运行时类型是指定数组的运行时类型。如果列表适宜指定的数组，则返回其中。* 否则，将为指定数组的运行时类型和此列表的大小调配一个新数组。* 如果列表实用于指定的数组，其余空间（即数组的列表数量多于此元素），则紧跟在汇合完结后的数组中的元素设置为 null。*（这仅在调用者晓得列表不蕴含任何空元素的状况下能力确定列表的长度。）*/
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {if (a.length < size)
// 新建一个运行时类型的数组，然而 ArrayList 数组的内容
return (T[]) Arrays.copyOf(elementData, size, a.getClass());
// 调用 System 提供的 arraycopy()办法实现数组之间的复制
System.arraycopy(elementData, 0, a, 0, size);
if (a.length > size)
a[size] = null;
return a;
}
// Positional Access Operations
@SuppressWarnings("unchecked")
E elementData(int index) {return (E) elementData[index];
}
/**
* 返回此列表中指定地位的元素。*/
public E get(int index) {rangeCheck(index);
return elementData(index);
}
/**
* 用指定的元素替换此列表中指定地位的元素。*/
public E set(int index, E element) {
// 对 index 进行界线查看
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
// 返回原来在这个地位的元素
return oldValue;
}
/**
* 将指定的元素追加到此列表的开端。*/
public boolean add(E e) {ensureCapacityInternal(size + 1); // Increments modCount!!
// 这里看到 ArrayList 增加元素的本质就相当于为数组赋值
elementData[size++] = e;
return true;
}
/**
* 在此列表中的指定地位插入指定的元素。* 先调用 rangeCheckForAdd 对 index 进行界线查看；而后调用 ensureCapacityInternal 办法保障 capacity 足够大；* 再将从 index 开始之后的所有成员后移一个地位；将 element 插入 index 地位；最初 size 加 1。*/
public void add(int index, E element) {rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
//arraycopy()这个实现数组之间复制的办法肯定要看一下，上面就用到了 arraycopy()办法实现数组本人复制本人
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
/**
* 删除该列表中指定地位的元素。将任何后续元素挪动到左侧（从其索引中减去一个元素）。*/
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;
}
/**
* 从列表中删除指定元素的第一个呈现（如果存在）。如果列表不蕴含该元素，则它不会更改。* 返回 true，如果此列表蕴含指定的元素
*/
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
}
/**
* 从列表中删除所有元素。*/
public void clear() {
modCount++;
// 把数组中所有的元素的值设为 null
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
/**
* 按指定汇合的 Iterator 返回的程序将指定汇合中的所有元素追加到此列表的开端。*/
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;
}
/**
* 从此列表中删除所有索引为 fromIndex（含）和 toIndex 之间的元素。* 将任何后续元素挪动到左侧（缩小其索引）。*/
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;
}
/**
* 查看给定的索引是否在范畴内。*/
private void rangeCheck(int index) {if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/**
* add 和 addAll 应用的 rangeCheck 的一个版本
*/
private void rangeCheckForAdd(int index) {if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/**
* 返回 IndexOutOfBoundsException 细节信息
*/
private String outOfBoundsMsg(int index) {return "Index:"+index+", Size:"+size;}
/**
* 从此列表中删除指定汇合中蕴含的所有元素。*/
public boolean removeAll(Collection<?> c) {Objects.requireNonNull(c);
// 如果此列表被批改则返回 true
return batchRemove(c, false);
}
/**
* 仅保留此列表中蕴含在指定汇合中的元素。* 换句话说，从此列表中删除其中不蕴含在指定汇合中的所有元素。*/
public boolean retainAll(Collection<?> c) {Objects.requireNonNull(c);
return batchRemove(c, true);
}
/**
* 从列表中的指定地位开始，返回列表中的元素（按正确程序）的列表迭代器。* 指定的索引示意初始调用将返回的第一个元素为 next。初始调用 previous 将返回指定索引减 1 的元素。* 返回的列表迭代器是 fail-fast。*/
public ListIterator<E> listIterator(int index) {if (index < 0 || index > size)
throw new IndexOutOfBoundsException("Index:"+index);
return new ListItr(index);
}
/**
* 返回列表中的列表迭代器（按适当的程序）。* 返回的列表迭代器是 fail-fast。*/
public ListIterator<E> listIterator() {return new ListItr(0);
}
/**
* 以正确的程序返回该列表中的元素的迭代器。* 返回的迭代器是 fail-fast。*/
public Iterator<E> iterator() {return new Itr();
}
复制代码ArrayList 扩容机制剖析
构造函数
ArrayList 有三种形式来初始化，构造方法源码如下：
/**
* 默认初始容量大小
*/
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* 默认构造函数，应用初始容量 10 结构一个空列表(无参数结构)
*/
public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}
/**
* 带初始容量参数的构造函数。（用户本人指定容量）*/
public ArrayList(int initialCapacity) {if (initialCapacity > 0) {// 初始容量大于 0
// 创立 initialCapacity 大小的数组
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {// 初始容量等于 0
// 创立空数组
this.elementData = EMPTY_ELEMENTDATA;
} else {// 初始容量小于 0，抛出异样
throw new IllegalArgumentException("Illegal Capacity:"+
initialCapacity);
}
}
/**
* 结构蕴含指定 collection 元素的列表，这些元素利用该汇合的迭代器按程序返回
* 如果指定的汇合为 null，throws NullPointerException。*/
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;
}
}
复制代码
// 默认初始容量大小
private static final int DEFAULT_CAPACITY = 10;
// 空数组（用于空实例）。private static final Object[] EMPTY_ELEMENTDATA = {};
// 用于默认大小空实例的共享空数组实例。private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 保留 ArrayList 数据的数组
transient Object[] elementData; // non-private to simplify nested class access
//ArrayList 所蕴含的元素个数
private int size;
// 默认构造函数，应用初始容量 10 结构一个空列表(无参数结构)
public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}
复制代码以无参数构造方法创立 ArrayList 时，实际上初始化赋值的是一个空数组。
那么什么时候才真正调配容量呢？？答案是增加第一个元素时
add()
/**
* 将指定的元素追加到此列表的开端。*/
public boolean add(E e) {
// 增加元素之前，先调用 ensureCapacityInternal 办法
ensureCapacityInternal(size + 1); // Increments modCount!!
// 这里看到 ArrayList 增加元素的本质就相当于为数组赋值
elementData[size++] = e;
return true;
}
复制代码add()将制订的元素追加到开端，咱们能够看到该办法中首先是调用了 ensureCapacityInternal(size + 1); size+1 =0+1=1。
ensureCapacityInternal()
该办法失去的是失去最小扩容量minCapacity
// 失去的是失去最小扩容量 minCapacity
private void ensureCapacityInternal(int minCapacity) {ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
复制代码该办法中调用的是ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
calculateCapacity()
咱们首先来看 calculateCapacity 这个办法，计算容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
复制代码elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA应用默认结构器时曾经赋值 this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; 所以符合条件为 true。
return Math.max(DEFAULT_CAPACITY, minCapacity); 比拟两值取最大值。DEFAULT_CAPACITY 值为 10，minCapacity 为传过来的值，第一次为size+1=0+1=1。所以最大值为 10。返回 10。
ensureExplicitCapacity()
此时咱们再会到 add 办法中查看这个被调用的 ensureExplicitCapacity 办法，该办法是 判断是否须要扩容
// 判断是否须要扩容
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
// 调用 grow 办法进行扩容，调用此办法代表曾经开始扩容了
grow(minCapacity);
}
复制代码第一次增加元素时，咱们通过重重判断曾经失去了 minCapacity=10, 此时判断minCapacity - elementData.length > 0 此时到数据长度还是为 0，所以 10-0=10>0，符合条件调用 grow() 办法。
- 当咱们要 add 进第 1 个元素到 ArrayList 时，elementData.length 为 0（因为还是一个空的 list），因为执行了
ensureCapacityInternal()办法，所以 minCapacity 此时为 10。此时，minCapacity - elementData.length > 0成立，所以会进入grow(minCapacity)办法。 - 当 add 第 2 个元素时，minCapacity 为 2，此时 e lementData.length(容量)在增加第一个元素后扩容成 10 了。此时，
minCapacity - elementData.length > 0不成立，所以不会进入（执行）grow(minCapacity)办法。 - 增加第 3、4···到第 10 个元素时，仍然不会执行 grow 办法，数组容量都为 10。
直到增加第 11 个元素，minCapacity(为 11)比 elementData.length（为 10）要大。进入 grow 办法进行扩容。
当咱们增加第 1 个元素，和第 11 个元素时是合乎扩容条件的。
grow()
要调配的最大数组大小
增加第 1 个元素时:
int oldCapacity = elementData.length;oldCapacity=0;int newCapacity = oldCapacity + (oldCapacity >> 1);newCapacity = 0 + 0/2 = 0;newCapacity 这个代表了新的数组的大小，>>1 右移一位相当于除 2，加上原数组大小的一半，也就是扩容 1.5oldCapacity 为偶数就是 1.5 倍，否则是 1.5 倍左右）！奇偶不同，比方：10+10/2 = 15, 33+33/2=49。如果是奇数的话会丢掉小数.
- 第一个 if 条件
newCapacity - minCapacity < 0此时是满足的 0 -10=-10<0, 所以newCapacity = minCapacity;此时newCapacity为 10 - 第二个 if 条件
newCapacity - MAX_ARRAY_SIZE > 0由下面定义的代码能够的失去private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;这个数是21 亿，比他小。不合乎。 elementData = Arrays.copyOf(elementData, newCapacity);通过 Arrays.copy 将本来的数组复制并且长度变成了newCapacity也就是 10。此时咱们的 ArrayList 也就终于有了容量。默认为 10
此时终于能够回到 add 办法了执行前面的代码 elementData[size++] = e; 此时 elemetnData 的长度曾经为 10 了，size 为 0，在 elementData[0] 增加元素，size+1=1。返回 true。
当增加第 11 个元素时：
int oldCapacity = elementData.length;为 10int newCapacity = oldCapacity + (oldCapacity >> 1);10+10/2 = 15- 全都不符
elementData = Arrays.copyOf(elementData, newCapacity);复制原数组扩容为 15。
/**
* 要调配的最大数组大小
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/**
* ArrayList 扩容的外围办法。*/
private void grow(int minCapacity) {
// oldCapacity 为旧容量，newCapacity 为新容量
int oldCapacity = elementData.length;
// 将 oldCapacity 右移一位，其成果相当于 oldCapacity /2，// 咱们晓得位运算的速度远远快于整除运算，整句运算式的后果就是将新容量更新为旧容量的 1.5 倍，int newCapacity = oldCapacity + (oldCapacity >> 1);
// 而后查看新容量是否大于最小须要容量，若还是小于最小须要容量，那么就把最小须要容量当作数组的新容量，if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 如果新容量大于 MAX_ARRAY_SIZE, 进入(执行) `hugeCapacity()` 办法来比拟 minCapacity 和 MAX_ARRAY_SIZE，// 如果 minCapacity 大于最大容量，则新容量则为 `Integer.MAX_VALUE`，否则，新容量大小则为 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);
}
复制代码hugeCapacity()
从下面 grow() 办法源码咱们晓得：如果新容量大于 MAX_ARRAY_SIZE, 进入(执行) hugeCapacity() 办法来比拟 minCapacity 和 MAX_ARRAY_SIZE，如果 minCapacity 大于最大容量，则新容量则为Integer.MAX_VALUE，否则，新容量大小则为 MAX_ARRAY_SIZE 即为 Integer.MAX_VALUE - 8。
private static int hugeCapacity(int minCapacity) {if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
// 对 minCapacity 和 MAX_ARRAY_SIZE 进行比拟
// 若 minCapacity 大，将 Integer.MAX_VALUE 作为新数组的大小
// 若 MAX_ARRAY_SIZE 大，将 MAX_ARRAY_SIZE 作为新数组的大小
//MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
复制代码System.arraycopy() 和 Arrays.copyOf()
浏览源码的话，咱们就会发现 ArrayList 中大量调用了这两个办法。比方：咱们下面讲的扩容操作以及add(int index, E element)、toArray() 等办法中都用到了该办法！
看两者源代码能够发现 copyOf()外部理论调用了 System.arraycopy() 办法
arraycopy() 须要指标数组，将原数组拷贝到你本人定义的数组里或者原数组，而且能够抉择拷贝的终点和长度以及放入新数组中的地位 copyOf() 是零碎主动在外部新建一个数组，并返回该数组。
总结
当咱们应用默认的结构器是实例化 ArrayList 时，数组大小通过种种判断扩容为 10。
应用默认结构器实例化的 ArrayList，在第一次增加元素和第 11 次增加元素时才会触发扩容。也就是第一次时，和超过数组容量时增加才触发扩容。
而初始化指定实例化创立的 ArrayList 只有超过数组容量时增加才触发扩容。扩容为 1.5 倍左右（分奇偶数）
ensureCapacity办法
ArrayList 源码中有一个 ensureCapacity 办法不晓得大家留神到没有，这个办法 ArrayList 外部没有被调用过，所以很显然是提供给用户调用的，那么这个办法有什么作用呢？
/**
如有必要，减少此 ArrayList 实例的容量，以确保它至多能够包容由 minimum capacity 参数指定的元素数。*
* @param minCapacity 所需的最小容量
*/
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);
}
}
复制代码最好在 add 大量元素之前用 ensureCapacity 办法，以缩小增量重新分配的次数
咱们通过上面的代码理论测试以下这个办法的成果：
public class EnsureCapacityTest {public static void main(String[] args) {ArrayList<Object> list = new ArrayList<Object>();
final int N = 10000000;
long startTime = System.currentTimeMillis();
for (int i = 0; i < N; i++) {list.add(i);
}
long endTime = System.currentTimeMillis();
System.out.println("应用 ensureCapacity 办法前："+(endTime - startTime));
}
}
复制代码运行后果：
应用 ensureCapacity 办法前：2158
复制代码public class EnsureCapacityTest {public static void main(String[] args) {ArrayList<Object> list = new ArrayList<Object>();
final int N = 10000000;
list = new ArrayList<Object>();
long startTime1 = System.currentTimeMillis();
list.ensureCapacity(N);
for (int i = 0; i < N; i++) {list.add(i);
}
long endTime1 = System.currentTimeMillis();
System.out.println("应用 ensureCapacity 办法后："+(endTime1 - startTime1));
}
}
复制代码运行后果：
应用 ensureCapacity 办法前：1773
复制代码通过运行后果，咱们能够看出向 ArrayList 增加大量元素之前最好先应用ensureCapacity 办法，以缩小增量重新分配的次数。
细节
JDK7
JDK1.7:ArrayList 像饿汉式，间接创立一个初始容量为 10 的数组
JDK1.8:ArrayList 像懒汉式，一开始创立一个长度为 0 的数组，当增加第一个元 素时再创立一个始容量为 10 的数组
Arraylist 和 Vector 的区别?
www.kylin.show/60919.html
ArrayList是List的次要实现类，底层应用Object[]存储，实用于频繁的查找工作，线程不平安；Vector是List的古老实现类，底层应用Object[]存储，线程平安的。(底层 synchronized 同步办法)
Arraylist 与 LinkedList 区别?
- 是否保障线程平安：
ArrayList和LinkedList都是不同步的，也就是不保障线程平安； - 底层数据结构：
Arraylist底层应用的是Object数组 ；LinkedList底层应用的是 双向链表 数据结构（JDK1.6 之前为循环链表，JDK1.7 勾销了循环。留神双向链表和双向循环链表的区别，上面有介绍到！） - 插入和删除是否受元素地位的影响： ①
ArrayList采纳数组存储，所以插入和删除元素的工夫复杂度受元素地位的影响。 比方：执行add(E e)办法的时候，ArrayList会默认在将指定的元素追加到此列表的开端，这种状况工夫复杂度就是 O(1)。然而如果要在指定地位 i 插入和删除元素的话（add(int index, E element)）工夫复杂度就为 O(n-i)。因为在进行上述操作的时候汇合中第 i 和第 i 个元素之后的 (n-i) 个元素都要执行向后位 / 向前移一位的操作。②LinkedList采纳链表存储，所以对于add(E e)办法的插入，删除元素工夫复杂度不受元素地位的影响，近似 O(1)，如果是要在指定地位i插入和删除元素的话（(add(int index, E element)）工夫复杂度近似为o(n))因为须要先挪动到指定地位再插入。 - 是否反对疾速随机拜访：
LinkedList不反对高效的随机元素拜访，而ArrayList反对。疾速随机拜访就是通过元素的序号疾速获取元素对象 (对应于get(int index)办法)。 - 内存空间占用：
ArrayList的空 间节约次要体现在在 list 列表的结尾会预留肯定的容量空间，而LinkedList的空间破费则体现在它的每一个元素都须要耗费比ArrayList更多的空间（因为要寄存间接后继和间接前驱以及数据）。
链接：https://juejin.cn/post/690459…
正文完
