ArrayList结构和派系
派生关系
Iterable
集合的最上级接口, 定义了spliterator,iterator和实现了forEach函数Collection
所有集合的父级接口, 定义了通用函数 AbstractCollection
实现了Collection中大量函数, 除了特定的几个函数iterator和size之外的函数 AbstractList
继承了AbstractCollection, 实现了List接口的抽象类, 它实现了List中除size(), get(int location)之外的函数
和AbstractCollection相比, 实现了iterator()接口 RandomAccess
提供了随机访问(随机查找)功能, 在ArrayList中通过元素的序号快速获取元素对象, 这就是快速随机访问(随机查找) List
List有序队列接口, 提供了一些通过下标访问元素的函数.
List中每一个元素都有一个索引, 第一个元素是0, 往后每次+1
数据结构
ArrayList数据结构是数组
通过一定的算法逻辑动态扩容数组的长度, 可以理解为ArrayList底层是一个动态数组
与java原生的数组相比, 它的容量能动态增长
内存需要连续的空间保证
除去尾部位置元素的添加, 删除操作, 其余都涉及到位置移动
随机查找效率快(下标搜寻)初始化
ArrayList源码设计的优雅之道
new ArrayList的时候, 并不会真的创建长度10的对象数组
什么时候往里面添加元素了,什么时候才会完成数组的创建初始化源码
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; // non-private to simplify nested class access
private int size;
public ArrayList() {
this.elementData = DEFAULTCAPACITY_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);
}
}详细分析
serialVersionUID
用来验证版本一致性的字段, 反序列化时会效验DEFAULT_CAPACITY
默认容量, 为10 EMPTY_ELEMENTDATA
空对象数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA
默认容量空对象数组elementData
动态数组的空间大小, 包含空元素size
动态数组的实际大小, 记录数组里有多少元素, 不记录空元素ArrayList()
无参构造
public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}
把默认容量空对象数组赋值给elementData, 还是空
无参构造创建动态数组时, size为0, elementData为0ArrayList(int initialCapacity)
带参构造
参数大于0时
this.elementData = new Object[initialCapacity];
创建一个大小为initialCapacity的Object数组赋给elementData
参数小与于0时
this.elementData = EMPTY_ELEMENTDATA;
开一个长度为10的空间
参数小与于0时
抛异常总结
代码测试
public static void main(String[] args) throws Exception {
ArrayList arr = new ArrayList();
Field field = arr.getClass().getDeclaredField("elementData");
field.setAccessible(true);
Object[] o = (Object[]) field.get(arr);
System.out.println(arr.size());
System.out.println(o.length);
arr.add("1");
field = arr.getClass().getDeclaredField("elementData");
field.setAccessible(true);
o= (Object[]) field.get(arr);
System.out.println(arr.size());
System.out.println(o.length);
for (int i = 0; i < 16; i++) {
arr.add(i);
}
field = arr.getClass().getDeclaredField("elementData");
field.setAccessible(true);
o= (Object[]) field.get(arr);
System.out.println(arr.size());
System.out.println(o.length);
}输出
0
0
1
10
17
22初始化总结
ArrayList arr = new ArrayList();
elementData为0
size为0
ArrayList arr = new ArrayList(1);
elementData为0
size为1, 走了带参构造, 参数为几, 空间为几, ArrayList(int initialCapacity)
add("test");//添加元素源码分析会讲为什么空间为10
elementData为10
size为1
如果第一次添加元素数量为11, 基于动态扩容1.5倍, 它的长度就是15
添加元素
添加元素源码
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}详细分析
添加一个元素1-10个元素时
add(E e)方法 //以无参初始化(ArrayList arr = new ArrayList();), 并调用add(E e)添加一个元素为例
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
进ensureCapacityInternal(size + 1);此时传参为1 (0+1=1)
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
进calculateCapacity, 判断elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA是否成立
public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }
条件成立, 因为无参初始化方法已经赋过值
进if, 判断10和参数哪个大, 10大, 返回10
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
此时返回ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); 这里, 参数是10
10-10不大于0, 没走到动态扩容
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}目前是elementData(空间长度为10), size为1(size不记录空元素)
添加元素超出10的情况, 动态扩容
添加第11个元素时
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
此时minCapacity为11
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
不走if, 返回11, 则ensureExplicitCapacity(11)
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
11-10大于0, 进入动态扩容
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
进grow(minCapacity); 动态扩容方法
private void grow(int minCapacity) {
老空间为10
int oldCapacity = elementData.length;
新空间=10+(10>>1), 位运算10的二进制位为1010,
右移动1位二进制为101, 10进制为5, 所以新空间为15=10+5
int newCapacity = oldCapacity + (oldCapacity >> 1);
如果新空间-11小于0,则新空间为11
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
如果新空间大于0, 则赋值
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity); //下面讲这个方法
拷贝一个新的数组和长度的集合,赋值给我们的对象数组
elementData = Arrays.copyOf(elementData, newCapacity);
}
MAX_ARRAY_SIZE为Integer.MAX_VALUE-8 (int最大值-8)
如果要开的空间大于MAX_ARRAY_SIZE, 就把int最大值-8赋值给它
如果不大于MAX_ARRAY_SIZE,则把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;
}
官方注释对于-8的介绍
这8bit里存了要分配最大数组的大小(数组下标???)
虚拟机中在数据中保留的标题字 (既数组形状判断是否为数组,对象是否同步,数组大小, 不知道是否包含了对象类型的类信息指针???)
尝试分配更大的数组会抛异常, 其实大小还是支持到了Integer.MAX_VALUE
/**
* The maximum size of array to allocate.
* Some VMs reserve some header words in an array.
* Attempts to allocate larger arrays may result in
* OutOfMemoryError: Requested array size exceeds VM limit
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;fail-fast失败原因(modCount++)
之前介绍源码的时候把modCount++跳过了, 接下来解释下, 在ArrayList源码里有个监听
源码
private class Itr implements Iterator<E> {
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
int expectedModCount = modCount;
Itr() {}
public boolean hasNext() {
return cursor != size;
}
@SuppressWarnings("unchecked")
public E next() {
checkForComodification();
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[lastRet = i];
}
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
@Override
@SuppressWarnings("unchecked")
public void forEachRemaining(Consumer<? super E> consumer) {
Objects.requireNonNull(consumer);
final int size = ArrayList.this.size;
int i = cursor;
if (i >= size) {
return;
}
final Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length) {
throw new ConcurrentModificationException();
}
while (i != size && modCount == expectedModCount) {
consumer.accept((E) elementData[i++]);
}
// update once at end of iteration to reduce heap write traffic
cursor = i;
lastRet = i - 1;
checkForComodification();
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
在每次做集合元素操作时,都会改变modCount,在迭代的时候,会把modCount赋值给expectedModCount,
如果在迭代过程中删除元素,就会修改modCount,但是迭代器在过程中不会同步expectedModCount,
每次迭代会会比较是否相等
就是说在使用迭代器的时候, 不能改变元素, 但是可以使用迭代器的方法去改变
查找元素
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
E elementData(int index) {
return (E) elementData[index];
}
判断下标是否越界
复杂度O(1), 直接根据下标位置返回元素
删除元素
删除元素源码
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;
}
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);
src - 源数组。
srcPos - 源数组中的起始位置。
dest - 目标数组。
destPos - 目的地数据中的起始位置。
length - 要复制的数组元素的数量。总结
将指定源数组中的数组从指定位置复制到目标数组的指定位置
比如我们有个数组
值为 a b c d e f g h i g k
下标 0 1 2 3 4 5 6 7 8 9 10
如果删除f
rangeCheck(index); //效验下标越界, index=5
int numMoved = size - index - 1; //numMoved= 4
调用System.arraycopy(elementData, index+1, elementData, index, numMoved);从原数组下标从6开始copy到新数组从下标从5开始的后面
