Java集合(二)--ArrayList简析

通过上一篇文章的内容，我们简单了解了集合的框架。从本章开始，我们将开始分析集合的具体的实现类。我们先从ArrayList开始。

ArrayList的定义

先看一下ArrayList的定义：

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{}

具体分析一下：

1、继承了AbstractList，实现了List接口，即拥有List基本的添加、删除及修改等等。并且部分方法因为继承了AbstractList，所以也无需重写。

2、实现了RandomAccess接口，RandomAccess支持快速（通常是恒定时间）随机访问。所以，ArrayList也支持快速的随机访问。

3、实现了Cloneable接口，即支持clone。

4、实现了Serializable接口，即可以序列化，可以通过序列化去传输数据。

注意，ArrayList是有大小的，随着列表中元素的增加，它会自动扩容。ArrayList不是线程安全的，如果多个线程同时访问ArrayList的实例，并且至少有一个线程在结构上修改了列表，则必须在外部同步。

接下来，我们就通过源码，一步步分析一下ArrayList。

ArrayList的源码简析

首先，是ArrayList的创建。它提供了三个构造函数：

//构造具有指定初始容量的空列表,初始容量可以理解为initialCapacity。
public ArrayList(int initialCapacity) {}

//构造一个初始容量为10的空列表
public ArrayList() {}

//构造一个包含指定集合元素的列表
public ArrayList(Collection<? extends E> c) {}

在这里，我们从无参的构造函数入手分析。在调用了无参构造函数后，会执行以下代码：

this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;

嗯？this.elementData是个啥？DEFAULTCAPACITY_EMPTY_ELEMENTDATA又是什么鬼？赶紧去属性声明的地方看一下。

transient Object[] elementData;

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

哦，就是初始化了一个空的数组。

注意：elementData是存储ArrayList元素的数组缓冲区。 ArrayList的容量是此数组缓冲区的长度。
size属性是动态数组的实际大小（接下来要用）。

欸？空的数组？那初始容量10是怎么来的？嗯。。。我们想一下，每次我们实例化完一个ArrayList之后，一般会干什么？是添加元素对吧。那我们去add()方法里看看：

public boolean add(E e) {
        //确定数组大小
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //将新元素加入数组
        elementData[size++] = e;
        return true;
    }

我们看到他调用了一个ensureCapacityInternal()方法，并且，传递了一个参数"size + 1"。那这个方法是干嘛用的，又做了些什么事，我们去看看：

private static final int DEFAULT_CAPACITY = 10;

private void ensureCapacityInternal(int minCapacity) {
        //判断当前数组是否为默认数组
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            //取10和minCapacity的最大值作为新的数组的长度，调用无参构造函数生成ArrayList的话，添加第一个元素时minCapacity是1
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        //根据minCapacity判断是否要对数组扩容
        ensureExplicitCapacity(minCapacity);
    }

private void ensureExplicitCapacity(int minCapacity) {
        //将修改记录加1
        modCount++
        //判断数组当前容量是否可以容纳当前元素的个数
        if (minCapacity - elementData.length > 0)
            //当前容量无法容纳当前元素的个数，对数组扩容
            grow(minCapacity);
    }

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

private void grow(int minCapacity) {
        //接下来的操作，就是通过一系列判断，对数组扩容
        int oldCapacity = elementData.length;
        //右移一位可以理解为除以2，所以newCapacity扩容了oldCapacity的3/2
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //如果minCapacity(新的元素个数)比newCapacity还大，则取minCapacity
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        //对数组扩容，拷贝原数组中的元素，将其放到一个新的容量为newCapacity的数组中，并返回新数组
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

private static int hugeCapacity(int minCapacity) {
        //如果要创建的新的数组的长度小于0，抛出异常
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        //确定新建数组的长度
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

通过分析上面的源码，相信大家已经知道为什么默认长度是10了。也知道了ArrayList每次扩容都是原基础的3/2。

添加第一个元素时，任何带有elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA的空ArrayList都将扩展为DEFAULT_CAPACITY（DEFAULT_CAPACITY = 10）。
modCount主要由iterator()和listIterator()方法返回的迭代器和列表迭代器实现使用，是从AbstractList继承过来的一个属性，具体的后面会讲。

接下来的get()和set()方法就相对容易了，请看：

public E get(int index) {
        //判断是否数组越界，数组越界就抛出异常
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        //返回指定位置的元素
        return (E) elementData[index];
    }

//
public E set(int index, E element) {
        //判断是否数组越界，数组越界就抛出异常
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        //先用一个局部变量接收此位置的旧的元素
        E oldValue = (E) elementData[index];
        //在指定的位置添加新的元素，替换旧值
        elementData[index] = element;
        //返回修改之前的元素
        return oldValue;
    }

接下来我们分析一下remove(int index)方法：

public E remove(int index) {
        //判断是否数组越界，越界则抛出异常
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

        //数组修改次数加1
        modCount++;
        //获取index位置的当前的元素
        E oldValue = (E) elementData[index];
        //根据删除的元素的角标及数组的长度，判断要拷贝的数组长度
        int numMoved = size - index - 1;
        if (numMoved > 0)
            //将修改后的数组拷贝到一个新的数组
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        //置空方便GC工作
        elementData[--size] = null;
        //返回移除掉的元素
        return oldValue;
    }

现在，我们分析完了一些常用的方法。接下来，我们再看一下刚开始说的ArrayList的clone：

public Object clone() {
        try {
            ArrayList<?> v = (ArrayList<?>) super.clone();
            //复制数据
            v.elementData = Arrays.copyOf(elementData, size);
            //将操作数置为0
            v.modCount = 0;
            //返回克隆好的数组
            return v;
        } catch (CloneNotSupportedException e) {
            // this shouldn't happen, since we are Cloneable
            throw new InternalError(e);
        }
    }

以及序列化的读写：

//将ArrayList实例的状态保存到流中（即序列化它）。
private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException{
        // 写出数组中数据改变的次数等
        int expectedModCount = modCount;
        s.defaultWriteObject();

        //写出数组的容量
        s.writeInt(size);

        // 按正确的顺序写出所有元素。
        for (int i=0; i<size; i++) {
            s.writeObject(elementData[i]);
        }

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


//从流中重构ArrayList实例（即反序列化它）。
private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        elementData = EMPTY_ELEMENTDATA;

        //读入数组大小等
        s.defaultReadObject();

        // 读入容量
        s.readInt();

        if (size > 0) {
            //根据大小而不是容量来分配数组
            ensureCapacityInternal(size);

            Object[] a = elementData;
            // 按正确的顺序读入所有元素
            for (int i=0; i<size; i++) {
                a[i] = s.readObject();
            }
        }
    }

好了，ArrayList暂时就分析到这。其他的如果需要，后续再写。现在来总结一下：

1、ArrayList是通过elementData数组(Object类型)去操作数据的。这就是我们所说的，ArrayList的底层是数组，而且是一个动态数组。

2、使用无参的构造函数创建的ArrayList默认长度为10。当ArrayList的容量不足以容纳全部的元素，ArrayList会自己扩容：新的容量=3/2旧的容量。当然，容量最大不超过0x7fffffff(是一个16进制的数，值为：2^31 - 1，是最大的int数值)。

3、克隆，就是将已有的元素复制到一个新的数组

4、序列化的时候会先写入数组改变的次数以及数组的容量，然后再写入元素；反序列化的时候，会将数组大小即数组容量等全部读取出来，然后根据数组的大小来分配数组，最后读入所有的元素。

5、 ArrayList非线程安全。如果有并发修改，会抛出ConcurrentModificationException异常。这涉及到fail-fast机制，我们后面会讲到。

6、每次调用add()、addAll()方法时，如果元素个数超过了数组的当前容量，ArrayList都会去扩容，扩容需要将旧的元素拷贝到一个新的数组。所以，在可以知道最大容量的情况下，最好给ArrayList一个初始的容量值。

7、ArrayList为什么改、查快？因为它底层是数组，通过角标就可以改变或者查询对应位置的元素。为什么增、删慢？是因为增加、删除的操作会导致元素从旧的数组拷贝到一个新的数组。

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 204,189评论 6赞 478
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 85,577评论 2赞 381
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 150,857评论 0赞 337
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,703评论 1赞 276
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,705评论 5赞 366
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,620评论 1赞 281
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 37,995评论 3赞 396
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,656评论 0赞 258
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 40,898评论 1赞 298
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,639评论 2赞 321
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,720评论 1赞 330
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,395评论 4赞 319
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 38,982评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,953评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,195评论 1赞 260
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 44,907评论 2赞 349
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,472评论 2赞 342