乐趣区

关于java:ArrayList源码分析

ArrayList 概述
(1)ArrayList 是一种变长的汇合类,基于定长数组实现。
(2)ArrayList 容许空值和反复元素,当往 ArrayList 中增加的元素数量大于其底层数组容量时,其会通过扩容机制从新生成一个更大的数组。
(3)因为 ArrayList 底层基于数组实现,所以其能够保障在 O(1) 复杂度下实现随机查找操作。
(4)ArrayList 是非线程安全类,并发环境下,多个线程同时操作 ArrayList,会引发不可预知的异样或谬误。
ArrayList 的成员属性
在介绍对于 ArrayList 的各种办法之前先看一下根底属性成员。其中 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 与 EMPTY_ELEMENTDATA 的区别是:当咱们向数组中增加第一个元素时,DEFAULTCAPACITY_EMPTY_ELEMENTDATA 将会晓得数组该裁减多少。
// 默认初始化容量
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;
复制代码 static 润饰的 EMPTY_ELEMENTDATA 和 DEFAULTCAPACITY_EMPTY_ELEMENTDATA

ArrayList 构造方法
(1)带有初始化容量的构造方法

参数大于 0,elementData 初始化为 initialCapacity 大小的数组
参数小于 0,elementData 初始化为空数组
参数小于 0,抛出异样

// 参数为初始化容量
public ArrayList(int initialCapacity) {

// 判断容量的合法性
if (initialCapacity > 0) {
    //elementData 才是理论寄存元素的数组
    this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {// 如果传递的长度为 0,就是间接应用本人曾经定义的成员变量(一个空数组)
    this.elementData = EMPTY_ELEMENTDATA;
} else {
    throw new IllegalArgumentException("Illegal Capacity:"+
                                       initialCapacity);
}

}
复制代码(2)无参结构

构造方法中将 elementData 初始化为空数组 DEFAULTCAPACITY_EMPTY_ELEMENTDATA
当调用 add 办法增加第一个元素的时候,会进行扩容
扩容至大小为 DEFAULT_CAPACITY=10

// 无参结构,应用默认的 size 为 10 的空数组,在构造方法中没有对数组长度进行设置,会在后续调用 add 办法的时候进行扩容
public ArrayList() {

this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;

}
复制代码(3)参数为 Collection 类型的结构器
// 将一个参数为 Collection 的汇合转变为 ArrayList(实际上就是将汇合中的元素换为了数组的模式)。如果
// 传入的汇合为 null 会抛出空指针异样(调用 c.toArray() 办法的时候)
public ArrayList(Collection<? extends E> c) {

elementData = c.toArray();
if ((size = elementData.length) != 0) {//c.toArray()可能不会正确地返回一个 Object[]数组,那么应用 Arrays.copyOf()办法
    if (elementData.getClass() != Object[].class)
        elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
    // 如果汇合转换为数组之后数组长度为 0,就间接应用本人的空成员变量初始化 elementData
    this.elementData = EMPTY_ELEMENTDATA;
}

}
复制代码​ 下面的这些构造方法了解起来比较简单,关注前两个构造方法做的事件,目标都是初始化底层数组 elementData(this.elementData=XXX)。区别在于无参构造方法会将 elementData 初始化一个空数组,插入元素时,扩容将会按默认值从新初始化数组。而有参的构造方法则会将 elementData 初始化为参数值大小(>= 0)的数组。个别状况下,咱们用默认的构造方法即可。假使在可晓得将会向 ArrayList 插入多少元素的状况下,能够应用有参构造方法。
​ 下面说到了应用无参结构的时候,在调用 add 办法的时候会进行扩容,所以上面咱们就看看 add 办法以及扩容的细节
ArrayList 的 add 办法
add 办法大抵流程
// 将指定元素增加到 list 的开端
public boolean add(E e) {

// 因为要增加元素,所以增加之后可能导致容量不够,所以须要在增加之前进行判断(扩容)ensureCapacityInternal(size + 1);  // Increments modCount!!(待会会介绍到 fast-fail)elementData[size++] = e;
return true;

}
复制代码咱们看到 add 办法中在增加元素之前,会先判断 size 的大小,所以咱们来看看 ensureCapacityInternal 办法的细节
ensureCapacityInternal 办法剖析
private void ensureCapacityInternal(int minCapacity) {

// 这里就是判断 elementData 数组是不是为空数组
//(应用的无参结构的时候,elementData=DEFAULTCAPACITY_EMPTY_ELEMENTDATA)// 如果是,那么比拟 size+1(第一次调用 add 的时候 size+1=1)和 DEFAULT_CAPACITY,// 那么显然容量为 10
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);

}
复制代码​ 当 要 add 进第 1 个元素时,minCapacity 为 (size+1=0+1=)1,在 Math.max() 办法比拟后,minCapacity 为 10。而后紧接着调用 ensureExplicitCapacity 更新 modCount 的值,并判断是否须要扩容
ensureExplicitCapacity 办法剖析
private void ensureExplicitCapacity(int minCapacity) {

modCount++; // 这里就是 add 办法中正文的 Increments modCount
// 溢出
if (minCapacity - elementData.length > 0)
    grow(minCapacity);// 这里就是执行扩容的办法

}
复制代码​ 上面来看一下扩容的次要办法 grow。
grow 办法剖析
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE – 8;
private void grow(int minCapacity) {

// oldCapacity 为旧数组的容量
int oldCapacity = elementData.length;
// newCapacity 为新数组的容量(oldCap+oldCap/2: 即更新为旧容量的 1.5 倍)int newCapacity = oldCapacity + (oldCapacity >> 1);
// 查看新容量的大小是否小于最小须要容量,如果小于那旧将最小容量最为数组的新容量
if (newCapacity - minCapacity < 0)
    newCapacity = minCapacity;
// 如果新容量大于 MAX_ARRAY_SIZE,应用 hugeCapacity 比拟二者
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);

}
复制代码 hugeCapacity 办法
这里简略看一下 hugeCapacity 办法
private static int hugeCapacity(int minCapacity) {

if (minCapacity < 0) // overflow
    throw new OutOfMemoryError();
// 对 minCapacity 和 MAX_ARRAY_SIZE 进行比拟
// 若 minCapacity 大,将 Integer.MAX_VALUE 作为新数组的大小
// 若 MAX_ARRAY_SIZE 大,将 MAX_ARRAY_SIZE 作为新数组的大小
//MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;

}
复制代码 add 办法执行流程总结
​ 咱们用一幅图来简略梳理一下,当应用无参结构的时候,在第一次调用 add 办法之后的执行流程

​ 这是第一次调用 add 办法的过程,当扩容值 capacity 为 10 之后,

持续增加第 2 个元素(先留神调用 ensureCapacityInternal 办法传递的参数为 size+1=1+1=2)

在 ensureCapacityInternal 办法中,elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA 不成立,所以间接执行 ensureExplicitCapacity 办法

ensureExplicitCapacity 办法中 minCapacity 为刚刚传递的 2,所以第二个 if 判断(2-10=-8)不会成立,即 newCapacity 不比 MAX_ARRAY_SIZE 大,则不会进入 grow 办法。数组容量为 10,add 办法中 return true,size 增为 1。

假如又增加 3、4……10 个元素(其中过程相似,然而不会执行 grow 扩容办法)

当 add 第 11 个元素时候,会进入 grow 办法时,计算 newCapacity 为 15,比 minCapacity(为 10+1=11)大,第一个 if 判断不成立。新容量没有大于数组最大 size,不会进入 hugeCapacity 办法。数组容量扩为 15,add 办法中 return true,size 增为 11。

add(int index,E element)办法
// 在元素序列 index 地位处插入
public void add(int index, E element) {

rangeCheckForAdd(index); // 校验传递的 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 rangeCheckForAdd(int index) {

if (index > size || index < 0) // 这里判断的 index>size(保障数组的连续性),index 小于 0
    throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

}
复制代码 add(int index, E element)办法(在元素序列指定地位(假如该地位正当)插入)的过程大略是上面这些

检测数组是否有足够的空间 (这里的实现和下面的)
将 index 及其之后的所有元素向后移一位
将新元素插入至 index 处.

将新元素插入至序列指定地位,须要先将该地位及其之后的元素都向后挪动一位,为新元素腾出地位。这个操作的工夫复杂度为 O(N),频繁挪动元素可能会导致效率问题,特地是汇合中元素数量较多时。在日常开发中,若非所需,咱们该当尽量避免在大汇合中调用第二个插入方法。
ArrayList 的 remove 办法
ArrayList 反对两种删除元素的形式
1、remove(int index) 依照下标删除
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);

复制代码​ 删除过程如下图所示

2、remove(Object o) 依照元素删除,会删除和参数匹配的第一个元素
public boolean remove(Object o) {

// 如果元素是 null 遍历数组移除第一个 null
if (o == null) {for (int index = 0; index < size; index++)
        if (elementData[index] == null) {
            // 遍历找到第一个 null 元素的下标 调用下标移除元素的办法
            fastRemove(index);
            return true;
        }
} else {
    // 找到元素对应的下标 调用下标移除元素的办法
    for (int index = 0; index < size; index++)
        if (o.equals(elementData[index])) {fastRemove(index);
            return true;
        }
}
return false;

}
// 依照下标移除元素(通过数组元素的地位挪动来达到删除的成果)
private void fastRemove(int index) {
modCount++;
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
}
复制代码 ArrayList 的其余办法
ensureCapacity 办法
最好在 add 大量元素之前用 ensureCapacity 办法,以缩小增量从新调配的次数
public void ensureCapacity(int minCapacity) {

int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
    // any size if not default element table
    ? 0
    // larger than default for default empty table. It's already
    // supposed to be at default size.
    : DEFAULT_CAPACITY;

if (minCapacity > minExpand) {ensureExplicitCapacity(minCapacity);
}

}
复制代码 ArrayList 总结
(1)ArrayList 是一种变长的汇合类,基于定长数组实现,应用默认构造方法初始化进去的容量是 10(1.7 之后都是提早初始化,即第一次调用 add 办法增加元素的时候才将 elementData 容量初始化为 10)。
(2)ArrayList 容许空值和反复元素,当往 ArrayList 中增加的元素数量大于其底层数组容量时,其会通过扩容机制从新生成一个更大的数组。ArrayList 扩容的长度是原长度的 1.5 倍
(3)因为 ArrayList 底层基于数组实现,所以其能够保障在 O(1) 复杂度下实现随机查找操作。
(4)ArrayList 是非线程安全类,并发环境下,多个线程同时操作 ArrayList,会引发不可预知的异样或谬误。
(5)程序增加很不便
(6)删除和插入须要复制数组,性能差(能够应用 LinkindList)
(7)Integer.MAX_VALUE – 8:次要是思考到不同的 JVM, 有的 JVM 会在退出一些数据头, 当扩容后的容量大于 MAX_ARRAY_SIZE, 咱们会去比拟最小须要容量和 MAX_ARRAY_SIZE 做比拟, 如果比它大, 只能取 Integer.MAX_VALUE, 否则是 Integer.MAX_VALUE -8。这个是从 jdk1.7 开始才有的
fast-fail 机制
fail-fast 的解释:

在零碎设计中,疾速生效零碎一种能够立刻报告任何可能表明故障的状况的零碎。疾速生效零碎通常设计用于进行失常操作,而不是试图持续可能存在缺点的过程。这种设计通常会在操作中的多个点查看零碎的状态,因而能够及早检测到任何故障。疾速失败模块的职责是检测谬误,而后让零碎的下一个最高级别处理错误。

​ 就是在做零碎设计的时候先思考异常情况,一旦产生异样,间接进行并上报,比方上面的这个简略的例子
// 这里的代码是一个对两个整数做除法的办法,在 fast_fail_method 办法中,咱们对被除数做了个简略的查看,如果其值为 0,那么就间接抛出一个异样,并明确提醒异样起因。这其实就是 fail-fast 理念的理论利用。
public int fast_fail_method(int arg1,int arg2){

if(arg2 == 0){throw new RuntimeException("can't be zero");
}
return arg1/arg2;

}
复制代码​ 在 Java 汇合类中很多中央都用到了该机制进行设计,一旦使用不当,触发 fail-fast 机制设计的代码,就会产生非预期状况。咱们通常说的 Java 中的 fail-fast 机制,默认指的是 Java 汇合的一种谬误检测机制。当多个线程对局部汇合进行构造上的扭转的操作时,有可能会触发该机制时,之后就会抛出并发批改异样ConcurrentModificationException. 当然如果不在多线程环境下,如果在 foreach 遍历的时候应用 add/remove 办法,也可能会抛出该异样。参考 fast-fail 机制,这里简略做个总结
​ 之所以会抛出 ConcurrentModificationException 异样,是因为咱们的代码中应用了加强 for 循环,而在加强 for 循环中,汇合遍历是通过 iterator 进行的,然而元素的 add/remove 却是间接应用的汇合类本人的办法。这就导致 iterator 在遍历的时候,会发现有一个元素在本人人不知; 鬼不觉的状况下就被删除 / 增加了,就会抛出一个异样,用来提醒可能产生了并发批改!所以,在应用 Java 的汇合类的时候,如果产生 ConcurrentModificationException,优先思考 fail-fast 无关的状况,实际上这可能并没有真的产生并发,只是 Iterator 应用了 fail-fast 的爱护机制,只有他发现有某一次批改是未通过本人进行的,那么就会抛出异样。

作者:RoadTrip
链接:https://juejin.cn/post/684490…
起源:稀土掘金
著作权归作者所有。商业转载请分割作者取得受权,非商业转载请注明出处。

退出移动版