1、特点:
ArrayList是个动态数组,实现List接口,主要用来存储数据,如果存储基本类型的数据,如int,long,boolean,short,byte,那只存储它们对应的包装类。
增删慢:每次删除元素,都需要更改数组长度、拷贝以及移动元素位置。
查询快:由于数组在内存中是一块连续空间,因此可以根据地址+索引的方式快速获取对应位置上的元素。
ArrayList 是 Java 集合框架中的成员之一,底层是基于数组实现,并且集合容量可动态变化的。它继承自 AbstractList 抽象类,实现了 List 接口。同时还实现了 RandomAccess,Cloneable 和 Serializable 三个标记接口,说明 ArrayList 是支持快速随机访问,可克隆复制的,可序列化的。
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
}
2、ArrayList线程安全吗?
ArrayList是线程不安全的。
当开启多个线程操作List集合,向ArrayList中增加元素,同时去除元素。最后输出list中的所有数据,会出现几种情况:
① 有些元素输出为Null;
② 数组下标越界异常。
为什么ArrayList线程不安全,我们还使用它?
因为大多数的场景中,查询操作使用频率高,增删操作的使用频率低。如果涉及频繁的增删,可以使用LinkedList,实际开发过程中还是ArrayList使用最多的。 不存在一个集合既查询效率高,又增删效率高,还线程安全的,因为数据结构的特性就是优劣共存的,想找个平衡点很难,牺牲了性能,那就安全,牺牲了安全那就快速。
3、ArrayList源码分析
3.1 变量
ArrayList 底层是基于数组实现,并且集合容量可动态变化。类中定义了一个 Object 类型的数组存储元素,因为是 Object 类型的数组,所以也只能存储引用数据类型,如果存储基本数据类型(例如 int ,double等),底层会自动将基本数据类型进行类的包装。
ArrayList 中还定义了一个记录数组元素个数的变量,以及一个代表默认初始化容量的静态变量。
/**
* ArrayList 中存储元素的数组,数组的长度即集合的容量
* 不用 private 关键字修饰是为了内部类方便访问此数组
* transient 关键字修饰代表此数组不作为序列化的一部分
*/
transient Object[] elementData;
/**
* 记录 ArrayList 集合中实际存储的元素个数
*/
private int size;
/**
* 默认初始化容量
*/
private static final int DEFAULT_CAPACITY = 10;
ArrayList 中定义了两个静态空数组对象,主要用来当集合初始化,并且没有添加任何元素时,作为一个空数组对象赋值给 elementData 数组对象,代表一个空 list。那为啥要定义2个空数组对象呢?后面会细讲。
/**
* 一个共享的静态空数组对象,用于空 list 集合中
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* 一个共享的静态空数组对象,用于默认大小初始化的空 list 集合中
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
ArrayList 的父类 AbstractList 中定义了 modCount 变量,它记录了集合被操作修改的次数,在使用迭代器 Iterator 中会被使用到,因为在使用迭代器遍历集合元素的过程中集合结构不允许被修改(例如添加元素,删除元素),通过比较 modCount 的值能防止在迭代的过程中集合被修改。
protected transient int modCount = 0;
3.2 构造函数
ArrayList 有三个构造函数,一个无参构造函数,一个指定集合容量大小的有参构造函数,以及一个使用指定 Collection 集合来构造集合的构造函数。
无参构造函数,即初始化一个容量为10的空 list 集合,虽说是初始化容量为10的集合,但是实际此时没创建一个容量为10的数组,而只是将DEFAULTCAPACITY_EMPTY_ELEMENTDATA 这个空数组对象赋值给 elementData 变量,只有在第一次添加元素时才创建一个容量的为10的数组。
/**
* 构造一个容量为10的空 list
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
指定初始化容量的有参构造函数,当初始化容量大于0时,直接创建指定容量大小的数组,如果初始化容量为0,则将 EMPTY_ELEMENTDATA 空数组对象赋值给 elementData 变量。
/**
* 构造一个指定初始化容量大小的空 list
*/
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);
}
使用指定 Collection 集合来构造 ArrayList 对象,如果 Collection 不为空,则将其元素拷贝赋值到 elementData 中,如果 Collection 为空,则还是创建一个空的 list,相当于 new ArrayList(0)。
/**
* 构造一个 list,它包含了指定 Collection 集合元素,这些元素的顺序是通过集合迭代器返回元素的顺序决定的
*/
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;
}
}
3.3 常用方法(增删改查)
1、增
public boolean add(E e)
在 list 尾部添加一个元素,首先会将记录对集合操作的次数加1,然后再判断集合容量是否足够,不够则进行扩容。
/**
* 在 list 尾部添加一个元素
*/
public boolean add(E e) {
// 修改操作次数,并且是否进行扩容操作
ensureCapacityInternal(size + 1);
// 将新元素添加在数组尾部
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
// 如果是采用默认初始化容量10构造的 list,则取默认初始化容量10和当前需要添加元素的下标+1的最大值来初始化 list
// 这里就说明了为什么要定义2个空数组对象,因为通过判断空 list 是否等于 DEFAULTCAPACITY_EMPTY_ELEMENTDATA,
// 如果是,则使用默认的初始化容量10来进行扩容
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
// 修改次数加1
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
// 扩容
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
// 扩容到原来容量的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 最大容量为 Integer.MAX_VALUE
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 拷贝数组
elementData = Arrays.copyOf(elementData, newCapacity(minCapacity));
}
//参数为所需要的最小容积值
private int newCapacity(int minCapacity) {
int oldCapacity = elementData.length; 获取原始数组的容积值
int newCapacity = oldCapacity + (oldCapacity >> 1); 新容积值=原始容积值+原始容积值/2 扩容50% 【重点】
if (newCapacity - minCapacity <= 0) { newCapacity新容积值 是否小于等于 所需要的最小容积值minCapacity
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) 当前存放数据的数组是否为默认的空数组
return Math.max(DEFAULT_CAPACITY, minCapacity); 获取默认容积10和所需要的最小容积1的较大值
if (minCapacity < 0) 判断所需要的最小容积值是否小于0,如果小于0则一定是越界 size+1超出int范围
throw new OutOfMemoryError(); 抛出OOM
return minCapacity; 返回所需要的最小容积值
}
//newCapacity新容积值 大于 所需要的最小容积值minCapacity
* 这里的MAX_ARRAY_SIZE=Integer.MAX_VALUE-8
return (newCapacity - MAX_ARRAY_SIZE <= 0) 新容积值如果小于MAX_ARRAY_SIZE则返回新容积值
? newCapacity
: hugeCapacity(minCapacity); 如果所需要的最小容积值大于MAX_ARRAY_SIZE,则返回Integer.MAX_VALUE,否则返回MAX_ARRAY_SIZE
}
在指定位置添加元素
public void add(int index, E element)
在 list 指定下标位置添加一个元素,首先会检查下标是否在范围内,将记录对集合操作的次数加1,然后再判断集合容量是否足够,不够则进行扩容。
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
// 将下标位置后面的所有元素往后拷贝移一位
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
将指定 Collection 的所有元素添加到 list 的尾部中去,还是先检查是否需要扩容,最后再将 Collection 集合拷贝到 list 尾部。
public boolean addAll(Collection<? extends E> c)
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;
}
2、改
public E set(int index, E element)
修改 list 指定下标位置的元素,首先会检查下标是否在范围内,然后替换指定下标的元素,返回旧的元素。
/**
* Replaces the element at the specified position in this list with
* the specified element.
*
* @param index index of the element to replace
* @param element element to be stored at the specified position
* @return the element previously at the specified position
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
3、返回集合中元素的个数
public int size()
public int size() {
return size;
}
4、判断集合是否为空,即集合是否有元素
public boolean isEmpty()
/**
* Returns <tt>true</tt> if this list contains no elements.
*
* @return <tt>true</tt> if this list contains no elements
*/
public boolean isEmpty() {
return size == 0;
}
5、判断集合是否包含某元素,主要通过 equals 方法比较是否存在某元素。
public boolean contains(Object o)
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
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;
}
6、返回指定下标位置的元素,访问速度快。
public E get(int index)
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
E elementData(int index) {
return (E) elementData[index];
}
7、删
public boolean remove(Object o) {
final Object[] es = elementData;
final int size = this.size;
int i = 0;
found: {
//判断所需要的删除元素如果为null,则直接使用==判断,非空则使用equals判断
if (o == null) {
for (; i < size; i++)
if (es[i] == null) 查找所需要删除的元素位置,找到后添加found:{}范围
break found;
} else {
for (; i < size; i++)
if (o.equals(es[i]))
break found;
}
return false; 如果找不到则返回false
}
fastRemove(es, i); 参数1是存储数据的数组,i为查找到的对应位置下标
return true;
}
8.如何使用clone()方法
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<String>();
list.add("云");
list.add("烟");
list.add("成");
list.add("雨");
Object o = list.clone();
System.out.println(o);
System.out.println(list);
}