- 定义
- java.util.ArrayList类就是传说中的动态数组，相当于Array的复杂版本，也就是说，ArrayList对象既有数组的特征，也有列表的特征。ArrayList实现了List接口，允许对元素进行快速随机访问。
-
结构
image.png
- 源码
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 = {};
//主要作为一个标识位，在扩容时区分：默认大小和容量为0，使用默认容量时采取的是“懒加载”
//即等到add元素的时候才进行实际容量的分配
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//ArrayList内部结构，是一个Object[]类型的数组
transient Object[] elementData;
//记录当前容器中有多少元素
private int size;
- DEFAULT_CAPACITY ：默认大小为 10；（扩容为原来的一半 扩容一次以后为15）扩容使用Arrays.copyOf(elementData, size, Object[].class);
- EMPTY_ELEMENTDATA： 共享的空数组，用于初始化空实例
- Object[] elementData：ArrayList内部结构，是一个Object[]类型的数组
- size：记录当前容器中有多少元素
- 构造方法
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;
}
}
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);
}
}
//无参构造器，指向的是默认容量大小的Object数组，注意使用无参构造函数的时候并没有直接创建容量
//为10的Object数组,而是采取懒加载的策略：使用DEFAULTCAPACITY_EMPTY_ELEMENTDATA（实际容量为0）
//作为标识，在真正add元素时才会开辟Object数组，即在扩容函数中有处理默认容量的逻辑，后面会有分析
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
1. public ArrayList(int initialCapacity) 构造方法：表示接受指定容量值，初始化创建数组，真正开发时候按照实际情况创建ArrayList可指定。
2. public ArrayList() 构造方法：是默认的构造方法，它创建一个空数组。
3. public ArrayList(Collection<? extends E> c) 构造方法：接收一个Collection的实体，将该Collection实体转换为ArrayList对象。
- add 添加方法
public boolean add(E e) {
modCount++;
//add操作的核心函数，当使用无参构造器时并没有直接分配大小为10的Object数组，这里面有对应
//的处理逻辑
add(e, elementData, size);
return true;
}
- 主要用于标识线程安全，即ArrayList只能在单线程环境下使用，在多线程环境下会出现并发安全问题，modCount主要用于记录对ArrayList的修改次数，如果一个线程操作期间modCount发生了变化即，有多个线程同时修改当前这个ArrayList，此时会抛出“ConcurrentModificationException”异常，这又被称为“failFast机制”，在很多非线程安全的类中都有failFast机制：HashMap、 LinkedList等。这个机制主要用于迭代器、加强for循环等相关功能，也就是一个线程在迭代一个容器 时，如果其他线程改变了容器内的元素，迭代的这个线程会抛出“ConcurrentModificationException”异常
-
LinkedList底层采用双向列表实现，所以在添加新元素的时候要先构造一个Node对象（item为我们加入的值），只需要将Node的next赋值为新的Node即可。但是相对于ArrayList而言，LinkedList可以更加高效的插入元素，因为它不会涉及到ArrayList扩容。但也因为这种数据结构，导致它不具备有随机访问的能力。
-
ArrayList和LinkedList都不是线程安全的。那么如果我们要用线程安全的用什么呢 ？
- List<String> list = Collections.synchronizedList(new ArrayList<>());Collections提供了方法synchronizedList保证list是同步线程安全的。
- CopyOnWriteArrayList：写时复制，CopyOnWrite容器既写时复制的容器，往一个容器添加元素的时候，不直接往当前的容器Object[]添加，而是先将当前容器Object[] 进行Copy,复制出一个新的容器Object[] newElements,然后往新的容器Object[] newElement里面添加元素，添加完元素之后，再将原容器的引用指向新的容器，setArray(newElements );这样做的好处是可以对CopyOnWriter容器进行并发的读，而不需要加锁，因为当前容器不会添加任何元素，所以CopyOnWrite容器也是一种读写分离的思想，读和写不同的容器。
public boolean add(E e) { final ReentrantLock lock = this.lock; lock.lock(); try { Object[] elements = getArray(); int len = elements.length; Object[] newElements = Arrays.copyOf(elements, len + 1); newElements[len] = e; setArray(newElements); return true; } finally { lock.unlock(); } }
image.png
网友评论