类关系图
功能介绍
包路径：java.util
功能描述： ArrayList 继承了AbstractList抽象类，同时实现了List的接口，实现了可变大小的**数组，默认扩容方式为原先的50%，数据结构如下。随机访问和遍历元素时，提供更好的性能。该类是非同步的,在多线程的情况下不要使用。
特点：非线程安全，查询快，增删慢（涉及数组扩容）
源码解析
ArrayList实现了哪些接口？
List
RandomAccess接口：这个是一个标记性接口，它的作用就是用来快速随机存取，有关效率的问题，实现了该接口的使用普通的for循环来遍历，性能更高，例如arrayList。而没有实现该接口的话，使用Iterator来迭代，这样性能更高，例如linkedList。所以这个标记性只是为了让我们知道我们用什么样的方式去获取数据性能更好。
Cloneable接口：实现了该接口，就可以使用Object.Clone()方法了。
Serializable接口：实现该序列化接口，表明该类可以被序列化，什么是序列化？简单的说，就是能够从类变成字节流传输，然后还能从字节流变成原来的类。
主要属性
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 = {};// 缺省空对象数组private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};// 元素数组transient Object[] elementData;// 实际元素大小，默认为0private int size;// 最大数组容量private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;}
我们看到，核心属性实际上就是elementData，它代表了ArrayList作为元素容器，是一个数组。
构造方法
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
/**
* 无参构造函数，默认构建空对象数组
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
* 指定数组容量的构造方法
* @param initialCapacity the initial capacity of the list
*/
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) { // 如果指定数组容量为0，则直接将EMPTY_ELEMENTDATA赋值给elementData即可
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
/**
* 传入集合的构造函数
* @param c the collection whose elements are to be placed into this list
*/
public ArrayList(Collection<? extends E> c) {
// 将传入集合转换为数组并赋值给elementData
elementData = c.toArray();
// 如果数组不为空
if ((size = elementData.length) != 0) {
// 每个集合的toarray()的实现方法不一样，所以需要判断一下
// 如果不是Object[].class类型，需要使用ArrayList中的方法去改造一下。
// 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的构造方法就做一件事情，就是初始化一下储存数据的容器，其实本质上就是一个数组，在其中就叫elementData。
核心方法
(1) add方法—-添加元素
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
/**
* 添加元素，添加成功返回true
* @param e element to be appended to this list 元素
* @return <tt>true</tt> (as specified by {@link Collection#add})
*/
public boolean add(E e) {
// 确定内部容量是否足够，elementData默认容量为0，size默认为0，如果没有额外设置长度，则有可能会被扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
// 在数组中正确的位置上放上元素e，并且size++
elementData[size++] = e;
return true;
}
/**
* 指定位置插入元素
* @param index index at which the specified element is to be inserted
* @param element element to be inserted
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public void add(int index, E element) {
// 检查是否合法位置，插入的位置肯定不能大于size 和小于0
rangeCheckForAdd(index);
// 确定内部容量是否足够，elementData默认容量为0，size默认为0，如果没有额外设置长度，则有可能会被扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
// 在插入元素之后，要将index之后的元素都往后移一位
System.arraycopy(elementData, index, elementData, index + 1,size - index);
// 插入元素
elementData[index] = element;
size++;
}
/**
* 添加集合元素
* @param c collection containing elements to be added to this list
* @return <tt>true</tt> if this list changed as a result of the call
*/
public boolean addAll(Collection<? extends E> c) {
// 将传入集合转为数组
Object[] a = c.toArray();
// 获取传入集合元素个数
int numNew = a.length;
// 判断数组容量是否充足，不够则进行扩容
ensureCapacityInternal(size + numNew); // Increments modCount
// 插入元素，将a数组从位置0开始的元素复制到elementData数组的size位置之后，也就是末尾,复制长度为numNew
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
/**
* 在指定位置插入集合元素
* @param index index at which to insert the first element from the
* specified collection
* @param c collection containing elements to be added to this list
*/
public boolean addAll(int index, Collection<? extends E> c) {
// 检查index合法性，插入的位置肯定不能大于size 和小于0
rangeCheckForAdd(index);
Object[] a = c.toArray();
int numNew = a.length;
// 判断数组容量是否充足，不够则进行扩容
ensureCapacityInternal(size + numNew); // Increments modCount
// 判断是否需要移动元素，index==size则表示插入到末尾
int numMoved = size - index;
if (numMoved > 0)
// 移动元素
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
// 复制元素，将a数组从位置0开始的元素复制到elementData数组的index位置之后,复制长度为numNew
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
}
(2) remove方法—-删除元素
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
/**
* 移除指定位置元素
* @param index the index of the element to be removed
* @return the element that was removed from the list
*/
public E remove(int index) {
// 检查位置合法性，index肯定不能大于size 和小于0
rangeCheck(index);
// 更新修改次数
modCount++;
// 获取旧值
E oldValue = elementData(index);
// 判断是否需要移动元素
int numMoved = size - index - 1;
if (numMoved > 0)
// 对当前数组进行复制和移动
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// 将--size上的位置赋值为null，让gc(垃圾回收机制)更快的回收它。
elementData[--size] = null; // clear to let GC do its work
// 返回被删除的元素。
return oldValue;
}
/**
* 移除指定元素
* @param o element to be removed from this list, if present
* @return <tt>true</tt> if this list contained the specified element
*/
public boolean remove(Object o) {
// 如果传入元素为null
if (o == null) {
// 遍历找到第一个为null的元素，将其移除并返回true
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index); // 快速移除
return true;
}
} else {
// 遍历找到第一个与传入元素相等的元素，将其移除并返回true
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
/*
* 快速删除，实际上根remove(int index)方法差不多
*/
private void fastRemove(int index) {
modCount++;
// 判断是否需要移动元素
int numMoved = size - index - 1;
// 如果numMoved等于
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,numMoved);
// 将--size上的位置赋值为null，让gc(垃圾回收机制)更快的回收它。
elementData[--size] = null; // clear to let GC do its work
}
/**
* 移除指定位置范围的元素
*/
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;
}
/**
* 移除指定集合中存在的所有元素
*/
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, false); // 批量删除
}
/**
* 仅保留该指定集合中存在的所有元素,其余删除
*/
public boolean retainAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, true); // 批量删除
}
/**
* 批量移除，complement表示是否保留指定集合的元素
*/
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;
}
}
(3) set方法—-设置元素
public E set(int index, E element) {
// 检验索引是否合法
rangeCheck(index);
// 旧值
E oldValue = elementData(index);
// 赋新值
elementData[index] = element;
// 返回旧值
return oldValue;
}
(4) get方法—-获取元素
public E get(int index) {
// 检验索引是否合法
rangeCheck(index);
return elementData(index);
}
E elementData(int index) {
return (E) elementData[index];
}
(5) forEach方法—-遍历元素
/**
* 遍历元素并对元素执行传入函数
*/
@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();
}
}
(6) sort方法—-排序
@Override
@SuppressWarnings("unchecked")
public void sort(Comparator<? super E> c) {
final int expectedModCount = modCount;
// 调用 Arrays 工具类的sort方法对elementData进行排序
Arrays.sort((E[]) elementData, 0, size, c);
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}
(7) ensureCapacityInternal方法—-扩容
添加元素的时候会涉及到数组容量的判断与扩容操作，我们看一下具体源码：
private void ensureCapacityInternal(int minCapacity) {
// 判断elementData是不是空的数组，也就是没有长度
if (elementData == EMPTY_ELEMENTDATA) {
// 因为如果是空的话，minCapacity=size+1；其实就是等于1。
// 空的数组没有长度就存放不了，所以就将minCapacity变成10，也就是默认大小
// 到这里，还没有真正的初始化这个elementData的大小。
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
//确认实际的容量，上面只是将minCapacity=10，这个方法就是真正的判断elementData是否够用
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
// minCapacity如果大于了实际elementData的长度，那么就说明elementData数组的长度不够用
// 那么就要增加elementData的length。
if (minCapacity - elementData.length > 0)
// arrayList自动扩展大小的关键方法
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
// 将扩充前的elementData大小赋值给oldCapacity
int oldCapacity = elementData.length;
// newCapacity就是1.5倍的oldCapacity
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 适应于elementData就空数组的时候，length=0，那么oldCapacity=0，newCapacity=0，所以这个判断成立，
// 在这里就是真正的初始化elementData的大小了，就是为10.前面的工作都是准备工作。
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
//如果newCapacity超过了最大的容量限制，就调用hugeCapacity，也就是将能给的最大值给newCapacity
newCapacity = hugeCapacity(minCapacity);
//新的容量大小已经确定好了，就copy数组，改变容量大小咯。
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
// 如果minCapacity都大于MAX_ARRAY_SIZE，那么就Integer.MAX_VALUE返回，反之将MAX_ARRAY_SIZE返回。
// 因为maxCapacity是三倍的minCapacity，可能扩充的太大了，就用minCapacity来判断了。
// Integer.MAX_VALUE:2147483647 MAX_ARRAY_SIZE：2147483639 也就是说最大也就能给到第一个数值。
// 还是超过了这个限制，就要溢出了。相当于arraylist给了两层防护。
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
也就是说，最核心的方法实际上是grow方法，正常情况下数组会扩容1.5倍，特殊情况下（新扩展数组大小已经达到了最大值）则只取最大值。
简单使用
package com.java.list;
import java.util.ArrayList;
import java.util.List;
/**
* @description ArrayList演示
* @date: 2021-01-06 21:16
*/
public class ArrayListCode {
public static void main(String[] args) {
ArrayList<String> arrayList = new ArrayList<>();
for (int i=0;i<20;i++){
arrayList.add(""+i);
}
System.out.println("arrayList = "+arrayList+"\n");
List<String> subList = arrayList.subList(0, 10);
System.out.println("subList = "+subList);
System.out.println("arrayList = "+arrayList+"\n");
// 除了指定范围的元素，其余元素全部移除
arrayList.retainAll(subList);
System.out.println("arrayList = "+arrayList+"\n");
}
}
输出如下：
arrayList = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
subList = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
arrayList = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
arrayList = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
总结
1、 ArrayList 继承了AbstractList抽象类，同时实现了List的接口，实现了可变大小的**数组**，数据结构本质上就是一个数组。随机访问和遍历元素时，提供更好的性能。该类是非同步的,在多线程的情况下不要使用。
2、ArrayList是非线程安全，查询快，增删慢（涉及数组扩容）
3、ArrayList可以存放null。
4、arrayList区别于数组的地方在于能够自动扩展大小，其中关键的方法就是gorw()方法。
5、arrayList由于本质是数组，所以它在数据的查询方面会很快，而在插入删除这些方面，性能下降很多，需要移动很多数据才能达到应有的效果
6、arrayList实现了RandomAccess，所以在遍历它的时候推荐使用for循环。
思考
为什么说ArrayList是线程不安全的？
首先，我们得知道啥叫线程不安全：多个线程同一时刻对同一个全局变量(同一份资源)做写操作(读操作不会涉及线程安全)时，如果跟我们预期的结果一样，我们就称之为线程安全，反之，线程不安全。
也就是说，多线程并发写操作的情况下，没有得到我们预期的结果，就是线程不安全的。
严谨起见，ArrayList是不是线程不安全的？我们来做个测试
public class ArrayListCode {
public static void main(String[] args) throws InterruptedException {
threadExample();
}
/**
* 多线程测试ArrayList线程安全性
*/
public static void threadExample() throws InterruptedException {
ArrayList<Integer> arrayList = new ArrayList<>();
// 创建线程A调用ArrayList.add方法，往集合中添加元素[0-9]
Thread threadA = new Thread("A"){
@Override
public void run() {
for (int i=0;i<10;i++){
arrayList.add(i);
// 模拟业务耗时
try {
Thread.sleep(1);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
};
// 创建线程B调用ArrayList.add方法，往集合中添加元素[10-19]
Thread threadB = new Thread("B"){
@Override
public void run() {
for (int i=10;i<20;i++){
arrayList.add(i);
// 模拟业务耗时
try {
Thread.sleep(1);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
};
threadA.start();
threadB.start();
// 等待两个线程执行完毕
threadA.join();
threadB.join();
// 输出最终的集合元素
System.out.println(arrayList);
}
}
在上述代码中，我们创建了两个线程，启动后都调用了arrayList.add方法往集合填充元素，理想的结果应该如下：0-19共20个元素
但是在高并发添加数据下，ArrayList会暴露三个问题：
1、部分值为null（我们并没有add null进去）
2、索引越界异常
3、size与我们add的数量不符，也就是数据被覆盖（如下缺失了0，6，18三个元素）
这就已经证明了ArrayList确实是线程不安全的，那么是为什么呢
public boolean add(E e) {
// 确定内部容量是否足够，elementData默认容量为0，size默认为0，如果没有额外设置长度，则有可能会被扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
// 先在数组中size的位置上放上元素e，后size++
elementData[size++] = e;
return true;
}
从上述源码分析，我们知道，add方法的步骤大体可以分为三步：
判断数组需不需要扩容，如果需要的话，调用grow方法进行扩容；
在数组的size位置设置值（因为数组的下标是从0开始的）；
将当前集合的元素数量size加1
**
下面我们来分析三种情况都是如何产生的：
- 部分值为null： 两个线程同时进行size++操作
当线程A走到了扩容那里发现当前size是9，而数组容量是10，所以不用扩容，这时候cpu让出执行权，线程B也进来了，发现size是9，而数组容量是10，所以不用扩容，这时候线程A继续执行，将数组下标索引为9的位置set值了，还没有来得及执行size++，这时候线程B也来执行了，又把数组下标索引为9的位置set了一遍，这时候两个先后进行size++，size直接变成了11，导致下标索引10的地方就为null了。
- 索引越界异常：执行插入先后次序问题
**
线程A走到扩容那里发现当前size是9，数组容量是10不用扩容，cpu让出执行权，线程B也发现不用扩容，这时候数组的容量就是10，而线程A set完之后size++，这时候线程B再进来size就是10，数组的大小只有10，而你要设置下标索引为10的就会越界（数组的下标索引从0开始）；
- size与我们add的数量不符：size++非原子操作
**
这个基本上每次都会发生，这个理解起来也很简单，因为size++本身就不是原子操作，可以分为三步：获取size的值，将size的值加1，将新的size值覆盖掉原来的，线程1和线程2拿到一样的size值加完了同时覆盖，就会导致一次没有加上，所以肯定不会与我们add的数量保持一致的；
总结下来，其实也就是ArrayList对非原子操作没有加锁导致的线程不安全。
解决ArrayList线程不安全问题
1、使用线程安全的类：CopyOnWriteArrayList【内部使用Lock类保证线程安全】
2、使用Collections.synchronizedList(new ArrayList
3、使用Vector(内部主要使用synchronized关键字实现同步)
若有收获，就点个赞吧
0 人点赞
