文档章节

ArrayList源码分析

TSMYK
 TSMYK
发布于 2017/04/23 21:02
字数 1548
阅读 45
收藏 2

ArrayList源码分析

注:基于 jdk 1.8的源码。

ArrayList是Java的一个集合类,属于Collection分支下。继承于List,下面对一些方法的源码进行研究:
首先,ArrayList底层是通过 Object数组来存放元素的,当使用构造器创建一个ArrayList的时候,可以指定初始的容量,如果不指定初始容量,则默认的容量大小是10。

构造器的源码:

 public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

elementData是一个 Object 数组:

 transient Object[] elementData; 

DEFAULTCAPACITY_EMPTY_ELEMENTDATA也是一个Object 数组:

 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

也就是在创建对象的时候,并没有立刻初始化容器的大小,直到第一次调用 add()方法的时候,才进行确定。

add()方法:

add()运行流程图:

在调用 add()方法的时候,首先调用 ensureCapacityInternal()方法来确定是否还有容量来容纳新的值。size是表示数组的初始大小,默认为 0 。

第一次调用的时候,把size+1 = 1 传入ensureCapacityInternal()方法,然后进行判断,第一次的时候 elementDataDEFAULTCAPACITY_EMPTY_ELEMENTDATA是相等的,所以进入循环体,选择初始容量,
因为 DEFAULT_CAPACITY是10 ,而我们传入的1,所以初始容量为10。

private static final int DEFAULT_CAPACITY = 10;

之后把 10 传入ensureExplicitCapacity()方法,因为开始的时候,数组还没有值,所以 elementeDatalength()等于0,之后进入 grow()方法,把添加的值放入elementDate中。在grow()方法中,oldCapacity是初始数组的长度,为 0 ,newCapacity也等于 0 ,minCapacity是我们传入的,为10,因为 newCapacity < minCapacity,所以把10 赋值给newCapacity,之后进行数据的复制,这时,elementData的长度是 10.,第一个元素成功的添加到数组中。

注:在 ensureExplicitCapacity()方法中,有个modCount++的语句,modCount是用来记录列表中的元素发生结构性变化的次数,主要在多线程环境下需要使用,防止一个线程正在迭代遍历,另一个线程修改了这个列表的结构

当添加第二个元素的时候,size变为1,把size+1 = 2 传入ensureCapacityInternal(),因为第一次已经成功把第一个元素存入 elementData中,这时它为:


而此时DEFAULTCAPACITY_EMPTY_ELEMENTDATA还是为 {},如下所示:

if条件不成立,则直接执行,ensureExplicitCapacity(),这时参数是 2 。之后进行if判断,if (minCapacity - elementData.length > 0)也就是 2 > 10 不成立,(第一次已经把elementData.length变成10了)。然后就直接把数据放入到数组中,不进行扩容处理。

elementData[size++] = e;

当向集合中添加第 11 个元素的时候,把 11 传入 ensureExplicitCapacity(),  这时 ensureExplicitCapacity() > elementData.length成立(11 > 10)。然后在此进入 grow()方法,把容量扩展到原来的 1.5 倍,之后再添加元素。

如此循环即可。

remove()方法:

remove()方法用来从集合中删除一个元素,可以删除指定索引出的元素,也可以指定元素。

把元素当作参数来删除元素,执行流程图如下:

如图例子中,要删除 a3这个元素,把 a3传入到 remove()这个方法,首先进行判断是否为null,因为 ArrayList可以存放 null,,如果为 null 则用==判断元素是否相等,否则用 equals()方法进行判断。

然后循环遍历 elementData这个数组,size为数组元素个数,找到和 a3相等的元素的索引,例子中 index = 2, 然后把 2 传入到 fastRemove()方法中,之后计算要移动的元素的个数:

int numMoved = size - index -1

例子中 numMoved = 5 - 2 - 1 = 2 ,也就是一共要移动两个元素,然后把 a3之后的两个元素往前移动,然后进行 size-1,把最后一个元素位置的值设置为 null。

这样即可在ArrayList中删除一个元素。

get()方法

通过索引来获取集合中对应的元素,

在例子中 把 2 传入 get()方法,首先检查索引是否大于数组元素个数,若大于,则抛出一个异常,否则的话,返回 elementData数组所对应的元素即可。

iterator()方法:


iterator()返回一个迭代器,迭代器内部有一个 cursor游标,用来遍历数组,进行判断是否到达了数组的末尾。

int expectedModCount = modCount;

这行代码用来进行判断集合的结构是否已经改变,可能在遍历的过程中,会删除元素。

例子中 expectedModCountmodCount都是 5,当执行这段代码的时候:

if("a3".equals(v)){
    al.remove(v);
}

也就是使用 ArrayListremove()方法来移除元素的时候,modCount会进行 + 1 操作,当再一次调用 next()方法的时候,进入 checkForComodification()方法进行判断:

    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }

这时 expectedModCountmodCount已经不相等了,则会抛出ConcurrentModificationException异常。

所以在遍历迭代器的同时,想删除元素的话,则应该调用迭代器本身的 remove()方法,代码如下:

   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();
        }
    }

remove()方法中,并没有对 modCount进行就 + 1 操作,在 checkForComodification()中进行判断的话,条件不满足,则不会抛出异常。

总结

ArrayList集合底层是用一个 Object 数组来存放元素的,所以在 ArrayList中存放的元素都是有序的,还可以存放 null 值,因为是使用数组来存放元素,所以在知道索引的情况下,进行元素的查找是很快的,但是也有缺点,如果数组的容量不能够存放新元素的时候,会进行数组的扩容,也就是把数组元素复制到一个容量更大的数组中,所以如果在经常进行元素添加和删除操作的情况下效率会比较低。

还有一点,ArrayList不是线程安全的,要保证线程安全,可以使用 Vector代替。
它的add()方法如下:

public synchronized boolean add(E e) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = e;
    return true;
}

remove()方法如下:

public synchronized boolean removeElement(Object obj) {
    modCount++;
    int i = indexOf(obj);
    if (i >= 0) {
        removeElementAt(i);
        return true;
    }
    return false;
}

get()方法:

public synchronized E get(int index) {
    if (index >= elementCount)
        throw new ArrayIndexOutOfBoundsException(index);

    return elementData(index);
}

© 著作权归作者所有

共有 人打赏支持
TSMYK
粉丝 64
博文 77
码字总数 187219
作品 0
成都
程序员
私信 提问

暂无文章

Docker的系统资源限制及验证

1 、限制容器的资源 默认情况下, 容器没有资源限制 ,可以使用主机内核调度程序允许的尽可能多的给定资源。 Docker 提供了控制容器可以 使用多少内存或 CPU 的方法 ,设置 docker run 命令的...

微笑向暖wx
7分钟前
1
0
Redis5.0之Stream案例应用解读

非常高兴有机会和大家在这里交流Redis5.0之Stream应用。今天的分享更多的是一个抛砖引玉,欢迎大家提出更多关于Redis的思考。 首先,我们来个假设,这里有个杯子,这个杯子是去年我老婆送的,...

中间件小哥
8分钟前
1
0
阿里开发者们的第20个感悟:好的工程师为人写代码,而不仅是为编译器

1月17日,好的工程师为人写代码,而不仅是为编译器。这是我们送给开发者的第20个感悟。 李响,作为开源项目etcd作者更为开发者所熟知。etcd是2013年由李响,Brandon Philips, Alex Polvi 所发...

阿里云官方博客
9分钟前
1
0
Linux vmstat命令详解

导读 Linux命令千千万,而我们在日常工作中真真切切用到的命令应该不超过50个,在接下来的日子里,我会对我经常使用的命令,以及使用过程中不熟悉的命令进行一个总结,一是自我总结,加深记忆...

问题终结者
9分钟前
1
0
MacOS Docker安装及使用

MacOS Docker 安装 Homebrew 安装 macOS 我们可以使用 Homebrew 来安装 Docker。 Homebrew 的 Cask 已经支持 Docker for Mac,因此可以很方便的使用 Homebrew Cask 来进行安装: # 安装命令...

火力全開
11分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部