ArrayList类源码笔记

ArrayList类是一个继承自AbstractList类的变长数组，其长度可以随着元素数量的变化而变化。它同时实现了List、RandomAccess、Cloneable和Serializable接口。此外，ArrayList允许插入的元素为null，是一个线程不安全版本的Vector。

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

所在路径：\java\util\ArrayList.java

ArrayList类继承关系图

一、成员变量

ArrayList类的成员变量共7个，大概可以分为四类。1是默认容量（长度）和最大长度；2是空数组实例；3是当前数组的值和长度；最后是常规的UID。各变量具体的描述如下所示。

/** 默认容量为10（List的长度） */
private static final int DEFAULT_CAPACITY = 10;
/** List的最大长度（因为有些虚拟机为head word保留了空间，所以这个值减了8） */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

/** 空数组实例，适用于有参数的构造器（容量传入为0） */
private static final Object[] EMPTY_ELEMENTDATA = {};
/** 默认容量的空数组，适用于无参数的构造器（没有传入容量） */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/** 存储List元素的数组 */
transient Object[] elementData;
/** elementData的长度 */
private int size;

/** serialVersionUID */
private static final long serialVersionUID = 8683452581122892189L;

EMPTY_ELEMENTDATA和DEFAULTCAPACITY_EMPTY_ELEMENTDATA的区别主要是供不同的构造器使用，ArrayList类的创造者认为这是一种规范：https://blog.csdn.net/weixin_43390562/article/details/101236833

transient关键字修饰elementData是为了在序列化时不将数组尾部的空元素也输入进去，而是采取实现writeObject()方法的方式，只序列化有值的数组部分：https://www.cnblogs.com/vinozly/p/5171227.html

二、构造器

1、无参构造器

直接将一个空的数组赋值给elementData。

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
2、入参为初始容量

初始化一个长度为initialCapacity的数组。

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);
    }
}
3、入参为Collection接口的实现类或其子类

当入参为一个集合接口的实现类或其子类时，使用toArray()方法进行初始化。例如：List<String> stringList = new ArrayList<>(Arrays.asList("1", "2"));

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()和addAll()

1、add()

add()方法是ArrayList类的核心方法，它可以将元素添加到数组的尾部或指定位置。用户在使用add()方法不需要关心elementData的长度，只要不超过之前定义的最大长度，ArrayList会自动对elementData进行扩容。

/** 默认添加至尾部 */
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

/** 添加至指定位置 */
public void add(int index, E element) {
    rangeCheckForAdd(index);

    ensureCapacityInternal(size + 1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,
                     size - index);
    elementData[index] = element;
    size++;
}

每次插入数据前，ArrayList都会计算当前elementData是否需要扩容。扩容的具体过程如下：

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

    ensureExplicitCapacity(minCapacity);
}

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

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

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);
}

扩容的动作最终由Arrays.copyOf()方法完成（这个方法我们之前介绍过，它最终调用的是System.arraycopy()方法，实际上就是数组元素的逐一拷贝），数组的实际长度会增加为原来的1.5倍。

modCount表示被修改次数，在ArrayList的所有涉及结构变化的方法中都增加modCount的值，包括：add()、remove()、addAll()、removeRange()及clear()方法。这些方法每调用一次，modCount的值就加1。当线程对ArrayList进行遍历时，通过比较modCount和expectModCount的值来确保循环不会因多线程的不安全操作而出错。

https://blog.csdn.net/qq_24235325/article/details/52450331

当newCapacity大于MAX_ARRAY_SIZE时，会调用hugeCapacity()方法，最多返回一个Integer.MAX_VALUE。

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}
2、addAll()

addAll()方法可以将一个集合中的每个元素的都加入到数组中，具体的实现方法基本与add()一致。在copy前，ArrayList会先调用目标集合的toArray()方法，将其转换为一个Object类型的数组。

public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // Increments modCount
    System.arraycopy(a, 0, elementData, size, numNew);
    size += numNew;
    return numNew != 0;
}

public boolean addAll(int index, Collection<? extends E> c) {
    rangeCheckForAdd(index);

    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // Increments modCount

    int numMoved = size - index;
    if (numMoved > 0)
        System.arraycopy(elementData, index, elementData, index + numNew,
                         numMoved);

    System.arraycopy(a, 0, elementData, index, numNew);
    size += numNew;
    return numNew != 0;
}

四、remove()和removeAll()

1、remove()

remove()方法被用来从ArrayList中移除一个元素，移除元素的空当会被其他元素有序补齐。如果输入的参数是元素的index，ArrayList会直接用System.arraycopy()对其进行覆盖。如果入参是一个Object类对象，ArrayList会在遍历数组后调用fastRemove()方法。

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; // clear to let GC do its work

    return oldValue;
}

public boolean remove(Object o) {
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    } else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}

入参为Object类对象的remove()方法会在第一次遍历到该对象时移除并返回，此时ArrayList调用的是对象的equals()方法，必要的时候这个方法需要由调用者进行重写。

其中，fastRemove()方法的实现和入参为index的remove()方法是一样的，它的源码为：

private void fastRemove(int index) {
    modCount++;
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work
}
2、removeAll()

removeAll()方法可以移除数组中所有被包含在输入集合中的元素，ArrayList采用判断后再赋值给新数组的方式，避免了频繁的arraycopy操作。

public boolean removeAll(Collection<?> c) {
    Objects.requireNonNull(c);
    return batchRemove(c, false);
}

private boolean batchRemove(Collection<?> c, boolean complement) {
    final Object[] elementData = this.elementData;
    int r = 0, w = 0;
    boolean modified = false;
    try {
        for (; r < size; r++)
            if (c.contains(elementData[r]) == complement)
                elementData[w++] = elementData[r];
    } finally {
        // Preserve behavioral compatibility with AbstractCollection,
        // even if c.contains() throws.
        if (r != size) {
            System.arraycopy(elementData, r,
                             elementData, w,
                             size - r);
            w += size - r;
        }
        if (w != size) {
            // clear to let GC do its work
            for (int i = w; i < size; i++)
                elementData[i] = null;
            modCount += size - w;
            size = w;
            modified = true;
        }
    }
    return modified;
}

与removeAll()对应的是retainAll()方法，这个方法在调用fastRemove()方法时传入true，将入参集合中包含的元素留下来并删除其他元素。

public boolean retainAll(Collection<?> c) {
    Objects.requireNonNull(c);
    return batchRemove(c, true);
}

五、indexOf()和lastIndexOf()

indexOf()和lastIndexOf()方法分别返回输入元素按从前往后和从后往前两种顺序查找出的数组下标，如果该元素出现了多次，则只返回按当前顺序查找到的第一个。

public int indexOf(Object o) {
    if (o == null) {
        for (int i = 0; i < size; i++)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = 0; i < size; i++)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

public int lastIndexOf(Object o) {
    if (o == null) {
        for (int i = size-1; i >= 0; i--)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = size-1; i >= 0; i--)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}

六、writeObject()和readObject()

由于elementData被transient修饰，不会在序列化时被转换出来，ArrayList自己实现了writeObject()和readObject()方法。序列化时，ObjectOutputStream类会通过反射获得ArrayList的这两个方法，从而实现只序列化有elementData的有值部分。

private void writeObject(java.io.ObjectOutputStream s)
    throws java.io.IOException{
    // Write out element count, and any hidden stuff
    int expectedModCount = modCount;
    s.defaultWriteObject();

    // Write out size as capacity for behavioural compatibility with clone()
    s.writeInt(size);

    // Write out all elements in the proper order.
    for (int i=0; i<size; i++) {
        s.writeObject(elementData[i]);
    }

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

private void readObject(java.io.ObjectInputStream s)
    throws java.io.IOException, ClassNotFoundException {
    elementData = EMPTY_ELEMENTDATA;

    // Read in size, and any hidden stuff
    s.defaultReadObject();

    // Read in capacity
    s.readInt(); // ignored

    if (size > 0) {
        // be like clone(), allocate array based upon size not capacity
        ensureCapacityInternal(size);

        Object[] a = elementData;
        // Read in all elements in the proper order.
        for (int i=0; i<size; i++) {
            a[i] = s.readObject();
        }
    }
}

七、subList()

subList()方法会返回一个ArrayList的内部类，这个类同样继承自AbstractList，只是在起止index上与当前ArrayList有所不同。

public List<E> subList(int fromIndex, int toIndex) {
    subListRangeCheck(fromIndex, toIndex, size);
    return new SubList(this, 0, fromIndex, toIndex);
}

/** 内部类SubList */
private class SubList extends AbstractList<E> implements RandomAccess

八、iterator()

iterator()方法同样返回一个类型为Itr的内部类，它实现了Iterator<E>接口。

public Iterator<E> iterator() {
    return new Itr();
}

/** 内部类Itr */
private class Itr implements Iterator<E>

九、其他

最后，ArrayList同样提供了几个入参为各类接口实现的工具方法，用户可以自定义操作的规则。

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