ArrayList源码剖析

分享编程技能、互联网技术、生活感悟、打造干货分享平台，将总结的技术、心得、经验分享给大家，这里不只限于技术！还有职场心得、生活感悟、以及面经。点击上方 "杨守乐" ，选择“置顶公众号”，第一时间送达！

“

 一、总体介绍

ArrayList实现了List接口，是顺序容器，即元素存放的数据与放进去的顺序相同，允许放入null元素，底层通过数组实现。除该类未实现同步外，其余跟Vector大致相同。每个ArrayList都有一个容量（capacity），表示底层数组的实际大小，容器内存储元素的个数不能多于当前容量。当向容器中添加元素时，如果容量不足，容器会自动增大底层数组的大小。前面已经提过，Java泛型只是编译器提供的语法糖，所以这里的数组是一个Object数组，以便能够容纳任何类型的对象。

size(), isEmpty(), get(), set()方法均能在常数时间内完成，add()方法的时间开销跟插入位置有关，addAll()方法的时间开销跟添加元素的个数成正比。其余方法大都是线性时间。

为追求效率，ArrayList没有实现同步（synchronized），如果需要多个线程并发访问，用户可以手动同步，也可使用Vector替代。

“

 二、方法剖析

set()

既然底层是一个数组ArrayList的set()方法也就变得非常简单，直接对数组的指定位置赋值即可。

public E set(int index, E element) {
    rangeCheck(index);//下标越界检查
    E oldValue = elementData(index);
    elementData[index] = element;//赋值到指定位置，复制的仅仅是引用
    return oldValue;
}

get()

get()方法同样很简单，唯一要注意的是由于底层数组是Object[]，得到元素后需要进行类型转换。

public E get(int index) {
    rangeCheck(index);
    return (E) elementData[index];//注意类型转换
}

add()

跟C++ 的vector不同，ArrayList没有push_back()方法，对应的方法是add(E e)，ArrayList也没有insert()方法，对应的方法是add(int index, E e)。这两个方法都是向容器中添加新元素，这可能会导致capacity不足，因此在添加元素之前，都需要进行剩余空间检查，如果需要则自动扩容。扩容操作最终是通过grow()方法完成的。

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);//原来的1.5倍
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);//扩展空间并复制
}

由于Java GC自动管理了内存，这里也就不需要考虑源数组释放的问题。

空间的问题解决后，插入过程就显得非常简单。

add(int index, E e)需要先对元素进行移动，然后完成插入操作，也就意味着该方法有着线性的时间复杂度。

addAll()

addAll()方法能够一次添加多个元素，根据位置不同也有两个把本，一个是在末尾添加的addAll(Collection c)方法，一个是从指定位置开始插入的addAll(int index, Collection c)方法。跟add()方法类似，在插入之前也需要进行空间检查，如果需要则自动扩容；如果从指定位置插入，也会存在移动元素的情况。
addAll()的时间复杂度不仅跟插入元素的多少有关，也跟插入的位置相关。

remove()

remove()方法也有两个版本，一个是remove(int index)删除指定位置的元素，另一个是remove(Object o)删除第一个满足o.equals(elementData[index])的元素。删除操作是add()操作的逆过程，需要将删除点之后的元素向前移动一个位置。需要注意的是为了让GC起作用，必须显式的为最后一个位置赋null值。

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; //清除该位置的引用，让GC起作用
    return oldValue;
}

关于Java GC这里需要特别说明一下，有了垃圾收集器并不意味着一定不会有内存泄漏。对象能否被GC的依据是是否还有引用指向它，上面代码中如果不手动赋null值，除非对应的位置被其他元素覆盖，否则原来的对象就一直不会被回收。

欢迎大家加入，一起学习和交流， 三月份优惠期 68元/年， 从四月份起恢复为128元。

如果您觉得不错，请别忘了转发、分享、点赞让更多的人去学习， 您的举手之劳，就是对小乐最好的支持，非常感谢！

如何您想进技术群和大牛们交流，关注公众号在后台回复 “加群”，或者 “学习” 即可

来自：CarpenterLee

链接：

http://www.cnblogs.com/CarpenterLee/p/5419880.html

著作权归作者所有。本文已获得授权。欢迎投稿。

每日英文

Be true to who you are. Stop trying to please other people or be someone else. It’s better to be an original version of yourself than an exact duplicate of someone else.

做真实的自己，不要为了取悦别人或试图成为某个人。做你最原始的自己，比做任何人的复制品都来得好。

乐乐有话说

有人帮你，是你的幸运；无人帮你，是公正的命运。没有人该为你做什么，因为生命是你自己的，你得为自己负责。

推荐阅读

看完本文有收获？请转发分享给更多人
关注「杨守乐」，提升技能