Java ArrayList 源码解析

Java ArrayList 源码解析

GG

ps：这篇文章是Java 集合框架源码分析系列的第一篇文章，从Java中最常用的集合类ArrayList开始。

ArrayList简介

以下源码来自jdk1.8

  • 这是一个实现了List接口的 底层通过数组实现的容量可变的集合
  • 类中add方法的时间复杂度为O(n)，其他操作的时间复杂度大致与add方法的时间复杂度持平
  • 创建ArrayList时，可以指定预期容量大小，也可以不指定，但如果知道预期存储元素的大小，创建ArrayList时指定大小可以减少动态扩容的消耗
  • ArrayList是线程不安全的集合，所以不要多线程环境下使用ArrayList，可以使用Collections工具类中的：mList = Collections.synchronizedList(mList);来将一个List转换成线程安全的集合
  • 如果在操作ArrayList的迭代器或SubList（ArrayList的一个子类，代表ArrasyList的视图）的情况下，同时操作arrayList本类，则会抛出ConcurrentModificationException

下面贴一下ArrayList的官方文档：


IDEA是真的好用啊

ArrayList类的继承关系：

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
  • RandomAccess 空接口，代表这个类支持随机访问，并且当对ArrayList遍历时，通过索引访问的效率要比迭代器的效率高
  • Cloneable 支持实例克隆，这里实现的克隆是浅克隆
  • Serializable 支持序列化

ArrayList的构造函数

分析ArrayList的源码，让我们先从构造函数开始看起，这是一个使用一个类的起点：

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

   
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_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;
        }
    }

成员变量：

    private static final int DEFAULT_CAPACITY = 10;
    
    private static final Object[] EMPTY_ELEMENTDATA = {};
    
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    //真正存储元素的数组
    transient Object[] elementData; // non-private to simplify nested class access
    
    private int size;
ArrayList(int initialCapacity)

这种构造函数指定了底层存储元素数组elementData的容量,通过这种方式不会使用EMPTY_ELEMENTDATA和DEFAULTCAPACITY_EMPTY_ELEMENTDATA这两个成员变量数组，直接将elementDatanew出来，不过当容量为0时，element指向EMPTY_ELEMENTDATA 空数组

ArrayList()

将elementData指向默认数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA

ArrayList(Collection<? extends E> c)

将集合c中的元素转成数组然后让elementData指向这个数组
总的来说，三个构造函数都在初始化elementData这个ArrayList底层存储元素的数组

常用方法

add(E e)

容易想到的是，动态扩容机制一定是在add方法中直接或间接执行的，先看add方法的源码

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

将元素e存储在elementData数组内，ensureCapacityInternal这个方法翻译过来就是，确定内部容量

    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

只有我们执行空参数构造函数，if条件才成立，返回DEFAULT_CAPACITY, minCapacity的较大值，然后充当ensureExplicitCapacity方法的参数，DEFAULT_CAPACITY常量的值指定为10

    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

这里将modeCount++，这个成员变量的作用是为了防止迭代器或视图和arraylist同时进行增删，具体后面再说，先看完整流程，这个方法的最后调用了grow，grow方法是真正的数组扩容的方法。

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

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

通过Arrays.copyOf返回扩容后的数组然后将引用重新赋值给elementData

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

通过grow方法可以总结出ArrayList动态扩容的逻辑：

  • 正常逻辑：
    执行add方法是，如果当前元素的size + 1大于elementData数组的大小，那么就触发扩容机制，将当前数组大小扩大1一半，也就是：10.15.22.33,49.....，数组的最大大小是Integer.MAX_VALUE,超出这个大小会抛出：OutOfMemoryError异常：
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        ...
    }
  • 第一次add时
    如果构造函数时没有指定容量，那么当第一次执行add方法时，会将数组大小指定为DEFAULT_CAPACITY：10。
set(int index, E element)

就是在检查index是否合法后，修改element数组对应idex的值。

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

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

返回数组中的值

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

        return elementData(index);
    }
remove(int index)

移除此列表中指定位置的元素。,被删除元素的所有后续元素向左移一位。容易想到的时，使用ArrayList尽量不要在中间增加或删除元素，尤其是当size很大时，这样会非常消耗资源。这里又看到了modeCount++这个操作。

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

这样增删改查方法就分析完毕，其他的一些方法都是对elementData数组进行的操作，就不展开一一分析了。

modCount

上面我们看到在add和remove方法中会让modCount++，那这个变量到底有什么用呢？
它的作用是为了阻止arraylist和它的迭代器或subList同时修改elementData这个数组，否则会有并发问题。ArrayList是线程不安全集合。先看一下这一段代码：

    public static void main(String[] args) throws InterruptedException {
        ArrayList<String> arrayList = new ArrayList<>(5);

        for (int i = 0; i < 5; i++) {
            arrayList.add(i + "");
        }

        ListIterator<String> listIterator = arrayList.listIterator();
        arrayList.remove(4);
        listIterator.next();
    }

执行后会抛出异常：

异常

这里抛出异常应该的，如果迭代器和arraylist同时修改elementData，如果使用者不了解其中细节，大概率会出现问题。下面分析是什么机制让迭代器检测到并发问题并抛出异常。

    private class Itr implements Iterator<E> {
        int cursor;       // index of next element to return
        int lastRet = -1; // index of last element returned; -1 if no such
        int expectedModCount = modCount;

        Itr() {}

        public boolean hasNext() {
            return cursor != size;
        }
            ...
}

在初始化迭代器时，会将expectedModCount 指定为modCount的值，然后看next方法：

    public E next() {
            checkForComodification();
            int i = cursor;
            if (i >= size)
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            cursor = i + 1;
            return (E) elementData[lastRet = i];
        }

在第一行看到一个checkForComodification()，继续跟进

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

看到这里我们就全明白了，当我们得到arraylist的迭代器时，会将expectedModCount的值指定为modCount，之后如果继续通过list执行增删操作，那么这里的判断modCount != expectedModCount就会成立， 那么就会抛出ConcurrentModificationException异常！

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