文档章节

ArrayList源码分析

tsmyk0715
 tsmyk0715
发布于 2017/04/23 21:02
字数 1548
阅读 28
收藏 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);
}

© 著作权归作者所有

共有 人打赏支持
tsmyk0715
粉丝 34
博文 65
码字总数 143556
作品 0
成都
程序员
私信 提问

暂无文章

设计模式之单例模式

单例模式核心:保证一个类只有一个对象 单例模式分为五种:懒汉式、饿汉式、双重检测锁式、静态内部类式、枚举式 五种模式的特点:懒汉式---线程安全,调用效率高,不能延时加载 饿汉式---线...

森林之下
2分钟前
0
0
markdown语法

这篇博客是本人在使用markdown语法过程中,用于记录一些自己总是会忘记的语法,并且会持续更新; 如何增加批注/备注:>; 这是一条备注/引言 如何手动换行,行末两次空格;

BlackCanary
3分钟前
0
0
redis 设置外网可访问

前提是你已经把redis的端口放到了防火墙计划中,  /sbin/iptables -I INPUT -p tcp --dport 6379 -j ACCEPT /etc/rc.d/init.d/iptables save 更改redis.conf 文件 bind 127.0.0.1prot...

时刻在奔跑
5分钟前
0
0
css3隐藏滚动条

chrome 和Safari .element::-webkit-scrollbar { width: 0 } IE 10+ .element { -ms-overflow-style: none; } Firefox .element { overflow: -moz-scrollbars-none; } firefox这个没试过~啦啦......

呵呵闯
21分钟前
0
0
Poco官方PPT_020-ErrorHandlingAndDebugging双语对照翻译

因工作需要用到这一块的功能,所以直接翻译了一下 此PPT来源于官方文件,地址https://pocoproject.org/documentation.html

CHONGCHEN
25分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部