Java底层类和源码分析系列-ArrayList底层架构和源码分析
几个要点
- ArrayList非线程安全;
- ArrayList基于动态数组，是一种线性表。随机访问友好,其可以保证在 O(1) 复杂度下完成随机查找操作，插入和删除效率低;
- ArrayList 实现了RandmoAccess接口，即提供了随机访问功能。RandmoAccess是java中用来被List实现，为List提供快速访问功能的。在ArrayList中，我们即可以通过元素的序号快速获取元素对象；
- 容量动态调节，有一套扩容和优化空间的机制,ArrayList 允许空值和重复元素，当往 ArrayList 中添加的元素数量大于其底层数组容量时，其会通过扩容机制重新生成一个更大的数组;
- ArrayList继承了AbstractList，实现了List、RandomAccess、Cloneable、Serializable接口;
- ArrayList扩容的长度是原长度的1.5倍;
- 删除和插入需要复制数组，性能差（可以使用LinkindList替代），ArrayList适合读多写少的场景；
定义
public class ArrayList<E> extends AbstractList<E>implements List<E>, RandomAccess, Cloneable, java.io.Serializable
成员属性
//默认初始化容量private static final int DEFAULT_CAPACITY = 10;
//默认的空的数组，这个主要是在构造方法初始化一个空数组的时候使用
private static final Object[] EMPTY_ELEMENTDATA = {};
//使用默认size大小的空数组实例，和EMPTY_ELEMENTDATA区分开来，
//这样可以知道当第一个元素添加的时候进行扩容至多少
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//ArrayList底层存储数据就是通过数组的形式，ArrayList长度就是数组的长度。
//一个空的实例elementData为上面的DEFAULTCAPACITY_EMPTY_ELEMENTDATA，当添加第一个元素的时候
//会进行扩容，扩容大小就是上面的默认容量DEFAULT_CAPACITY
transient Object[] elementData; // non-private to simplify nested class access
//arrayList的大小
private int size;
// 数组最大长度
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
构造方法
无参构造函数
如果不传入参数，则使用默认无参构建方法创建ArrayList对象，如下：
public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
注意：此时我们创建的ArrayList对象中的elementData中的长度是1，size是0,当进行第一次add的时候，elementData将会变成默认的长度：10.
带int类型的构造函数
如果传入参数，则代表指定ArrayList的初始数组长度，传入参数如果是大于等于0，则使用用户的参数初始化，如果用户传入的参数小于0，则抛出异常，构造方法如下：
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对象的内容（可以理解为深拷贝）copy到elementData中
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;
}
}
扩容
每次扩0.5倍进新容量newCapacity
private void grow(int minCapacity) { // overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
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);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
add
/** 在元素序列尾部插入 */public boolean add(E e) {
// 1. 检测是否需要扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
// 2. 将新元素插入序列尾部
elementData[size++] = e;
return true;
}
add主要的执行逻辑如下：
1）确保数组已使用长度（size）加1之后足够存下 下一个数据
2）修改次数modCount 标识自增1，如果当前数组已使用长度（size）加1后的大于当前的数组长度，则调用grow方法，增长数组，grow方法会将当前数组的长度变为原来容量的1.5倍。
3）确保新增的数据有地方存储之后，则将新元素添加到位于size的位置上。
4）返回添加成功布尔值。
/** 在元素序列 index 位置处插入 */public void add(int index, E element) {
rangeCheckForAdd(index);
// 1. 检测是否需要扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
// 2. 将 index 及其之后的所有元素都向后移一位
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
// 3. 将新元素插入至 index 处
elementData[index] = element;
size++;
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
remove
public E remove(int index) { rangeCheck(index); //校验下标是否合法（如果index>size，旧抛出IndexOutOfBoundsException异常）
modCount++;//修改list结构，就需要更新这个值
E oldValue = elementData(index); //直接在数组中查找这个值
int numMoved = size - index - 1;//这里计算所需要移动的数目
//如果这个值大于0 说明后续有元素需要左移(size=index+1)
//如果是0说明被移除的对象就是最后一位元素(不需要移动别的元素)
if (numMoved > 0)
//索引index只有的所有元素左移一位 覆盖掉index位置上的元素
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//移动之后，原数组中size位置null
elementData[--size] = null; // clear to let GC do its work
//返回旧值
return oldValue;
}
//src:源数组
//srcPos:从源数组的srcPos位置处开始移动
//dest:目标数组
//desPos:源数组的srcPos位置处开始移动的元素，这些元素从目标数组的desPos处开始填充
//length:移动源数组的长度
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);
//私有删除方法，不进行边界检查，不返回被删除元素
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
//native方法，速度比for和clone都"fast"
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null;
}
//删除[fromIndex,toIndex)的元素
protected void removeRange(int fromIndex, int toIndex) {
modCount++;
int numMoved = size - toIndex;//要移动的数量
System.arraycopy(elementData, toIndex, elementData, fromIndex,
numMoved);
// 删除后，list 的长度
int newSize = size - (toIndex-fromIndex);
//将失效元素置空
for (int i = newSize; i < size; i++) {
elementData[i] = null;
}
size = newSize;
}
//移除c集合中的元素
public boolean removeAll(Collection<?> c) {
//判断集合是否为空，否则抛出NPE
Objects.requireNonNull(c);
return batchRemove(c, false);
}
//保留c集合中的元素
public boolean retainAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, true);
}
get
public E get(int index) { rangeCheck(index);
checkForComodification();
return ArrayList.this.elementData(offset + index);
}
//顺序找，返回首先出现的位置，找不到返-1。O(n)
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;
}
//逆序找，返回最后出现的位置，找不到返-1。O(n)
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;
}
//顺序找实现，根据返回值判断
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
遍历的4种方法
ArrayList<String> list = new ArrayList<String>();list.add("a");
list.add("b");
list.add("c");
方式1
Iterator<String> it = strList.iterator();
while (it.hasNext()) {
System.out.println(it.next());
}
方式2
for (int i = 0; i < list.size(); i++) {
list.get(i);
}
方式3
for(String tmp:list){
System.out.println(tmp);
}
方式4
Consumer<String> consumer = (a) -> System.out.println(a);
list.forEach(consumer);
以上是 Java底层类和源码分析系列-ArrayList底层架构和源码分析 的全部内容， 来源链接： utcz.com/z/391631.html
