java源码赏析--java.util.ArrayList

1. 简介

ArrayList 是可以动态增长和缩减的索引序列，它是基于数组实现的 List 类。

该类封装了一个动态再分配的 Object[] 数组，每一个类对象都有一个 capacity 属性，表示它们所封装的 Object[] 数组的长度，当向 ArrayList 中添加元素时，该属性值会自动增加。如果向 ArrayList 中添加大量元素，可使用 ensureCapacity 方法一次性增加 capacity ，可以减少增加重分配的次数提高性能。

ArrayList 的用法和 Vector 相类似，但是 Vector 是一个较老的集合，具有很多缺点，不建议使用。另外，ArrayList 和 Vector 的区别是：ArrayList 是线程不安全的，当多条线程访问同一个 ArrayList 集合时，程序需要手动保证该集合的同步性，而 Vector 则是线程安全的。

size、isEmpty、get、set、iterator和listIterator操作的运行时间是常量。add操作对于添加n个元素，需要O(n)的时间。其他的操作需要线性时间。

1.1 继承关系

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

  • 继承 AbstractList 抽象父类，AbstractList提供了List接口的默认实现（个别方法为抽象方法）。

  • 实现了 List 接口（规定了 List 的操作规范），List接口（extends Collection）定义了列表必须实现的方法。

  • RandomAccess（可随机访问），是一个标记接口，用来标记可适用与随机访问算法的类。

  • Cloneable（可拷贝），可以调用Object.clone方法返回该对象的浅拷贝。

  • Serializable（可序列化）。

2. 源码分析

2.1 属性

//默认初始容量  
private static final int DEFAULT_CAPACITY = 10;
  
//空数组  
private static final Object[] EMPTY_ELEMENTDATA = {};

//默认空数组   
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

// 不会被序列化  
transient Object[] elementData;  
  
//ArrayList实际元素容量
private int size;

//最大容量
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

  • ArrayList的默认容量DEFAULT_CAPACITY为10。

  • 数据存放在elementData中，且访问级别为包内私有，是为了使内部类能够访问到其中的元素。并且被标记为transient，也就意味着在序列化的时候，此字段是不会被序列化的。

  • size表示数组中元素的个数

  • EMPTY_ELEMENTDATA与DEFAULTCAPACITY_EMPTY_ELEMENTDATA是为了在构造函数中初始化elementData使用的。

  • MAX_ARRAY_SIZE为ArrayList最大分配容量。

2.2 构造函数

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

无参构造函数，elementData中没有元素，size为0，且elementData的长度也为0。使用DEFAULTCAPACITY_EMPTY_ELEMENTDATA为elementData赋值。

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

elementData中没有元素，size为0，不过elementData的长度有可能不同。使用EMPTY_ELEMENTDATA为elementData赋值。

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

首先将集合c转化为数组，然后检查转化的类型，如果不是 Object[] 类型，使用 Arrays 类中的 copyOf 方法进行复制；同时，如果 c 中没有元素，使用 EMPTY_ELEMENTDATA 初始化。

2.3 主要方法

2.3.1 boolean add(E e)

确保容量足够后，在尾部添加一个元素

public boolean add(E e) {
    ensureCapacityInternal(size + 1);
    elementData[size++] = e;
    return true;
}
动态扩容

ensureCapacityInternal 在 Arraylist 中多次使用，着重理解。

private void ensureCapacityInternal(int minCapacity) {
    
    //第一次添加元素时，如果是无参构造函数构造而来，那么所需最小容量为DEFAULT_CAPACITY
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

上面代码中if判断为了区分对象是由哪一种构造函数构造而来。第一次添加元素时需要确定最小扩容容量。而DEFAULTCAPACITY_EMPTY_ELEMENTDATA 与 EMPTY_ELEMENTDATA用来区分三个构造函数。

private void ensureExplicitCapacity(int minCapacity) {
    modCount++; //列表修改次数加1

    //如果所需最小容量大于数组长度时，才许真正扩容。
    if (minCapacity - elementData.length > 0){
        grow(minCapacity);
    }
}

private void grow(int minCapacity) {
    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);
}

一般正常情况下，新的容量一般为旧容量的1.5倍(oldCapacity + (oldCapacity >> 1))。

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) {// 这种情况，如何出现？
        throw new OutOfMemoryError();
    }
    return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE :  MAX_ARRAY_SIZE;
}

minCapacity 在超出最大限制时允许达到 Integer.MAX_VALUE，而不仅仅是Integer.MAX_VALUE - 8

2.3.2 void ensureCapacity(int minCapacity)

供外部调用的扩容方法。

在大致了解List大小时，可用此方法一次性增加minCapacity，这可以减少重分配次数，从而提高性能。

public void ensureCapacity(int minCapacity) {
    int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
        // any size if not default element table
        ? 0
        // larger than default for default empty table. It's already
        // supposed to be at default size.
        : DEFAULT_CAPACITY;

    if (minCapacity > minExpand) {
        ensureExplicitCapacity(minCapacity);
    }
}

  • 如果是通过无参构造函数构造且elementData中没有元素，则不需要扩容。

  • 在ensureExplicitCapacity方法中，如果扩容大小小于elementData长度，则不需要扩容。

2.3.3 void add(int index, E element) 

public void add(int index, E element) {
    rangeCheckForAdd(index);

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

检查 index 是否数组越界。

private void rangeCheckForAdd(int index) {
    if (index > size || index < 0) {
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
}

private String outOfBoundsMsg(int index) {
    return "Index: "+index+", Size: "+size;
}
  1. 先调用 rangeCheckForAdd 检查索引是否合法。
  2. 合法再调用上面讲过的 ensureCapacityInternal 执行扩容。
  3. 调用系统的 arraycopy 函数将索引处及其后的元素后移一位。
  4. 在 index 处插入该元素。

add(int index, E element)方法太耗时，主要体现在arraycopy上，一般别用。

2.3.4 boolean addAll(Collection<? extends E> c) 

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;
}
  1. 将 c 转换为数组 a。
  2. 调用 ensureCapacityInternal 动态扩容。
  3. 调用系统函数 arraycopy。
  4. 增加 elementData 的 size。
  5. 有意思的小细节，numNew != 0，则返回 true。

疑惑点

  • 为什么不从一开始就判断 numNew 的值呢，如果等于0，直接返回，后面的函数也就不用执行了？

2.3.5 boolean addAll(int index, Collection<? extends E> c) 

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;
}
  1. 和 add(int index, E element) 一样，先调用 rangeCheckForAdd 检查索引合法性。
  2. 将 c 转换为数组 a。
  3. 调用 ensureCapacityInternal 扩容。
  4. 如果插入位置不是 Arraylist 的末尾，则调用 arraycopy 将索引及其后的元素后移。
  5. 将 a 的元素 arraycopy 到 elementData 中。
  6. 增加 size。
  7. numNew != 0，则返回true。

2.3.5 E get(int index) 

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

    return elementData(index);
}

注意和 rangeCheckForAdd的不同之处。

private void rangeCheck(int index) {
    if (index >= size) {
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
}
  1. 检查索引合法性。
  2. 返回指定数据。

2.3.6 void clear() 

public void clear() {
    modCount++;

    // clear to let GC do its work
    for (int i = 0; i < size; i++){
        elementData[i] = null;
    }

    size = 0;
}
  1. 从结构上修改 此列表的次数加1；
  2. for循环将每个元素置空；
  3. size 置为0，elementData 的长度并没有修改，如果确定不再修改 list 内容之后最好调用 trimToSize 来释放掉一些空间）。

2.3.7 void trimToSize()

返回一个新数组，新数组不含null，数组的 size 和 elementData.length 相等，以节省空间。此函数可避免 size 很小但 elementData.length 很大的情况。

public void trimToSize() {
    modCount++;
    if (size < elementData.length) {
        elementData = (size == 0)
          ? EMPTY_ELEMENTDATA
          : Arrays.copyOf(elementData, size);
    }
}

2.3.8 int indexOf(Object o) 

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

ArrayList 中可以添加 null，且可以在任意位置。

2.3.9 boolean contains(Object o) 

public boolean contains(Object o) {
    return indexOf(o) >= 0;
}

不建议使用 contains(Object o) 方法。效率极差。原因是通过for循环分别 equals

2.3.10 boolean containsAll(Collection<?> c)

继承java.util.AbstractCollection 的 containsAll

public boolean containsAll(Collection<?> c) {
    for (Object e : c) {
        if (!contains(e)) {
            return false;
        }
    }
    return true;
}

不建议使用，效率更差。

2.3.11 int hashCode()

继承 java.util.AbstractList 的 hashCode

public int hashCode() {
    int hashCode = 1;
    for (E e : this) {
        hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());
    }
    return hashCode;
}

2.3.12 Object clone()

返回ArrayList实例的浅拷贝

public Object clone() {
    try {
        ArrayList<?> v = (ArrayList<?>) super.clone();
        v.elementData = Arrays.copyOf(elementData, size);
        v.modCount = 0;
        return v;
    } catch (CloneNotSupportedException e) {
        // this shouldn't happen, since we are Cloneable
        throw new InternalError(e);
    }
}

2.3.13 boolean remove(int index) 

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;
}
  • 检查索引合法性
  • 通过 System.arraycopy 挪动数组
  • size减一，并将elementData最后设为null

2.3.14 boolean remove(Object o) 

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

由于 ArrayList 中可以存储 null，所以需要判断参数 o 是否为空的判断。

直观从代码上看，不建议使用此方法删除对象，性能太差。建议使用 boolean remove(int index)删除元素。

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
}

需要注意 fastRemove(int index) 与 boolean remove(int index)的区别，仅仅是没有返回值，作者为什么将相同的代码写两遍呢？

2.3.15 boolean removeAll(Collection<?> c) 

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

判断对象是否为空

public static <T> T requireNonNull(T obj) {
    if (obj == null){
        throw new NullPointerException();
    }
    return obj;
}

batchRemove 这个类中最精妙的代码

private boolean batchRemove(Collection<?> c, boolean complement) {
    final Object[] elementData = this.elementData;
    int r = 0, w = 0;// r 用来遍历整个数组的索引  w 用来标记需要替换的索引
    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) { // 如果 w != size， 则说明 w之后的元素都是需要丢弃掉的。而如果 w == size， 则说明没有发生替换，不需要删除。
            // clear to let GC do its work
            for (int i = w; i < size; i++) {
                elementData[i] = null;
            }
            modCount += size - w; //本次修改次数就应该是 size - w
            size = w; //替换次数 = size
            modified = true;
        }
    }
    return modified;
}

2.3.16 boolean retainAll(Collection<?> c)

保留 c 中的元素，与 remoteAll 的区别在于 batchRemove(c, complement)。

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

2.3.17 E set(int index, E element)

替换对应索引的元素

public E set(int index, E element) {
    rangeCheck(index);

    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

2.3.18 Object[] toArray()

浅拷贝

public Object[] toArray() {
    return Arrays.copyOf(elementData, size);
}

2.3.19 <T> T[] toArray(T[] a) 

public <T> T[] toArray(T[] a) {
    if (a.length < size){
        // Make a new array of a's runtime type, but my contents:
        return (T[]) Arrays.copyOf(elementData, size, a.getClass());
    }
    System.arraycopy(elementData, 0, a, 0, size);
    if (a.length > size){
        a[size] = null;
    }
    return a;
}

2.3.20 void sort(Comparator<? super E> c) 

public void sort(Comparator<? super E> c) {
    final int expectedModCount = modCount;
    Arrays.sort((E[]) elementData, 0, size, c);
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
    modCount++;
}

ConcurrentModificationException 是用来判断在数组排序时是否被修改。

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