ArrayList源码阅读

前言

数组是我们最常用最简单的数据结构,Java里对数组做了一个简单的包装,就是ArrayList,提供自动扩容的功能。

最常用法

list在我们日常代码中最为常用的做法是创建一个list,放入数据,取出数据。如下:

@Test
public void testList(){
    final List<String> list = new ArrayList<>();
    list.add("a");
    list.add("b");
    list.add("c");
    list.add("a");

    final String one = list.get(0);
    final int size = list.size();

    Assert.assertEquals("a", one);
    Assert.assertEquals(4, size);
}

下面,将从构造函数开始读取源码。

构造器

第一步,构造一个list对象

/**
 * Constructs an empty list with an initial capacity of ten.
 */
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

注释写的很清楚,构造一个空list,初始化容量为10. 我们来看看这个初始值。

/**
 * Shared empty array instance used for default sized empty instances. We
 * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
 * first element is added.
 */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

默认大小的共享的空array实例。可以注意到这是一个static变量,也就是说所有的ArrayList对象共享这个变量。由此可以猜测,这是一个临时值。

然后看我们的数据存储对象elementData.

/**
 * The array buffer into which the elements of the ArrayList are stored.
 * The capacity of the ArrayList is the length of this array buffer. Any
 * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
 * will be expanded to DEFAULT_CAPACITY when the first element is added.
 */
transient Object[] elementData; // non-private to simplify nested class access

ArrayList的容量(capacity)就是这个数组的长度。 另外,注意修饰关键字transient, 这个不常用,用来表示这个字段不可以被序列化。我们知道,ArrayList实现了Serializable接口,为什么不允许序列化data呢?具体原因参加 http://www.cnblogs.com/woshimrf/p/java-serialize.html

add

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

先保证容量,然后插入数据,size数量+1.

private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

针对空list第一次add,判断elementData是不是默认的空对象,若是空对象,计算容量。容量的计算也很有意思。

private static final int DEFAULT_CAPACITY = 10;

第一次添加后容量就是10了,当超过10之后就肯定要扩容了。

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

再一次看到modCount这个变量名,和HashMap一样,记载容量发生变化的次数。而扩容的阈值也相当简单,只要保证当前数量+1能够容纳就好。当数组长度不够的时候,扩容。

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    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);
}

扩容也同HashMap一样,扩大为2倍。然后新建数组,长度为新的容量,复制旧数据。由于过程中没有加锁,ArrayList也不是线程安全的。

Get

public E get(int index) {
    rangeCheck(index);

    return elementData(index);
}

实现相当简单,就是通过数组下标读取元素。但值得学习的是编程结构。比如,这个的范围检测,通过一个有意义的方法名封装了一段代码。清晰易懂。

private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

如何使用线程安全的List

自己对变化过程加锁,或者使用

List list = Collection.synchronizedList(new ArrayList());

CopyOnWriteArrayList是一个有趣的例子,它规避了只读操作(如get/contains)并发的瓶颈,但是它为了做到这点,在修改操作中做了很多工作和修改可见性规则。 此外,修改操作还会锁住整个List,因此这也是一个并发瓶颈。所以从理论上来说,CopyOnWriteArrayList并不算是一个通用的并发List。(并发编程网)

参考

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏张善友的专栏

单元测试同时支持 NUnit/MSTest

让单元测试代码同时支持NUnit/MSTest,可以参照MSDN magazine,也可以参看 Switching Between Using NUnit an...

1896
来自专栏张善友的专栏

每周.NET前沿技术文章摘要(2017-05-24)

汇总国外.NET社区相关文章,覆盖.NET ,ASP.NET等内容。

5790
来自专栏张善友的专栏

IbatisNet支持2.0的版本Release 发布了

iBATIS.NET DataMapper 1.5 and DataAccess 1.8 Beta! (Jul 5, 2006) The iBATIS.NET ...

17710
来自专栏张善友的专栏

11年微软MVP:每周.NET前沿技术文章摘要(2017-05-10)

汇总国内外.NET社区相关文章,覆盖.NET ,ASP.NET两个方面的内容

5250
来自专栏前端小叙

网页CSS常用中英文字体收集

Windows的中文字体: 黑体:SimHei 宋体:SimSun 新宋体:NSimSun 仿宋:FangSong 楷体:KaiTi 仿宋_GB2312:Fan...

2834
来自专栏张善友的专栏

搭建.NET Framework 3.0开发环境 及SharePoint 2007/WSS 3环境

第一步:首先您必须安装.NET Framework 3.0,则可以下载其Redistributable Package Microsoft .NET Frame...

1956
来自专栏张善友的专栏

每周.NET前沿技术文章摘要(2017-05-24)

汇总国外.NET社区相关文章,覆盖.NET ,ASP.NET等内容: .NET Free eBook/Guide on ‘.NET Microservice...

1737
来自专栏张善友的专栏

每周.NET前沿技术文章摘要(2017-05-17)

汇总国外.NET社区相关文章,覆盖.NET ,ASP.NET等内容,本期包含性能分析这一主题内容

3570
来自专栏大内老A

MS Enterprise Library 5.0发布!!

What is Enterprise Library Enterprise Library is a collection of reusable softwa...

1745
来自专栏张善友的专栏

Microsoft training Kits

Microsoft training kits对于开始学习一门新技术的时候是一个非常好的资料.下面是一些training kits列表: .NET Framew...

1828

扫码关注云+社区