ArrayList源码学习（一）

ArrayList在平时工作中几乎天天都在用。回想起三四年前在刚开始学编程时，只使用数组的恐怖支配。正好最近项目不忙，抽出来点时间看看源码是怎样的

Java version: 1.8

类说明

ArrayList顾名思义，数组表。属于一种线性列表。
让我们来看一下官方文档给出的介绍：


Resizable-array implementation of the List interface.
Implements all optional list operations, and permits all elements, including null.
In addition to implementing the List interface, this class provides methods to manipulate the size of the array that is used internally to store the list.
(This class is roughly equivalent to Vector, except that it is unsynchronized.)

从这段文字中，有两点重要的信息：

  1. 可变的长度是ArrayList的重要特征。
  2. ArrayList线程不安全,而Vector是线程安全的。要记住这一点。
The size, isEmpty, get, set, iterator, and listIterator operations run in constant time.
The add operation runs in amortized constant time, that is, adding n elements requires O(n) time.
All of the other operations run in linear time (roughly speaking).
The constant factor is low compared to that for the LinkedList implementation.

这段信息告诉我们：

  1. size, isEmpty, get, set, iterator等操作效率极高。
  2. 添加元素的效率也还不错。
  3. 其他操作基本复杂度都是线性的。
  4. 比较起LinkedList来说，效率要高一些。
Each ArrayList instance has a capacity. 
The capacity is the size of the array used to store the elements in the list.
It is always at least as large as the list size. As elements are added to an ArrayList, its capacity grows automatically.
The details of the growth policy are not specified beyond the fact that adding an element has constant amortized time cost.

ArrayList的size的变化是由一套逻辑来控制的，对它进行增删操作的时候，size会自动变化。

ArrayList类的定义：

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

这是因为：

  • AbstractList这个抽象类提供了常用方法的实现，继承它避免重复代码。

  • List接口定义了列表必须实现的方法。

  • RandomAccess是一个标记接口，接口内没有定义任何内容。

  • 实现了Cloneable接口的类，可以调用Object.clone方法返回该对象的浅拷贝。

  • 通过实现 java.io.Serializable 接口以启用其序列化功能。未实现此接口的类将无法使其任何状态序列化或反序列化。序列化接口没有方法或字段，仅用于标识可序列化的语义。

成员变量：

   /**
     * Default initial capacity.
     */
    private static final int DEFAULT_CAPACITY = 10; //默认容量为10

    /**
     * The size of the ArrayList (the number of elements it contains).
     *
     * @serial
     */
    private int size; //list的大小，包含元素的数量

空数组：


    /**
     * Shared empty array instance used for empty instances.
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /**
     * 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 = {};  //区别上一个空数组，这个数组使用默认容量长度。

真正保存数据的数组：

    /**
     * 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

构造方法：

public ArrayList();
public ArrayList(int initialCapacity);
public ArrayList(Collection<? extends E> c);

第一种:

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

我们最常用的构造方法:

List<E> list = new ArrayList<>();

我们可以看到，当不指定容量参数时，内部给出的是容量为10的空数组。

第二种构造，指定容量：

    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

1.当指定的容量大于0时，新建长度为容量参数的空数组。
2.当容量参数为0，数据数组为长度为0的数组。
3.参数为负数，抛出异常。

第三种构造，参数为集合：

    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

逻辑也非常简单，就是将这个集合转为数组数据。

常用操作：

add():

    /**
     * Appends the specified element to the end of this list.
     *
     * @param e element to be appended to this list
     * @return <tt>true</tt> (as specified by {@link Collection#add})
     */
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

add() 方法继承自 AbstractList类。从代码上看到，在赋值前，内部确认了一下size+1这个数据是否
trimToSize():

    /**
     * Trims the capacity of this <tt>ArrayList</tt> instance to be the
     * list's current size.  An application can use this operation to minimize
     * the storage of an <tt>ArrayList</tt> instance.
     */
    public void trimToSize() {
        modCount++; //继承自AbstractList的变量，表示改变次数，trimToSize操作认为是改变了一次list
        if (size < elementData.length) {
            elementData = (size == 0)
              ? EMPTY_ELEMENTDATA
              : Arrays.copyOf(elementData, size);
        } //如果目前size小于装载数据的数组时，需要重新设置elementData的size
    }

关于这个方法的解释在这里：
https://www.zhihu.com/question/51057675/answer/123911537

  • capacity 容量，指的是这个arrayList实例最多可装多少个元素
  • size 指的是这个arrayList实例已经装了多少个元素

现在写一段代码来debug一下：

        ArrayList<String> list = new ArrayList<>();
        list.add("1");
        list.trimToSize();

执行完第一行的变量状况：


1.png

执行完第二行的变量状况：


1.png

我们看到，elementData是一个长度为10的Object数组，第一个数据为“1”，其他为0.

执行trimToSize后:


1.png

可以看到，所有null元素都被清空了。
这样做的好处是可以节约一部分内存。

再往下看我们就看到：

public void ensureCapacity(int minCapacity)
private void ensureCapacityInternal(int minCapacity)
private void ensureExplicitCapacity(int minCapacity)

从这三个方法的名字上来看，应该是确保list容量时使用的方法。
读完这三个方法，还是有些不清楚。但是发现核心方法为：

ensureExplicitCapacity(minCapacity);
grow(minCapacity);

下面研究一下ArrayList的动态扩容机制：

        ArrayList<String> list = new ArrayList<>();
        while(true){
            list.add("1");
        }

debug这段代码，发现list里的elementData在第一个元素进入时，elementData长度为10,第一个元素为1,剩下的全都为null;
当10个元素全都入满后，数组长度变为15，再次将其入满数据，elementData的长度变为22,33,49,73...不难发现，每次扩容都会使elementData的长度变为原来的1.5倍。每次扩容还需要将elementData重新拷贝到新的数组中。这意味着，ArrayList中元素不要过多，否则在扩容数组的时候有可能会出效率问题。但是一般不会出现这种问题，在平时工作中，我用的破笔记本，arrayList里面放几万条数据也没啥事。

grow方法的代码：

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