Java集合系列之ArrayList源码分析

数组(Array)

数组指的就是一组相关类型的变量集合，并且这些变量可以按照统一的方式进行操作，数组数据引用数据类型，在堆中进行内存分配，在内存中是连续存在，大小固定的。

ArrayList

ArrayList可以算是数组的加强版，其继承AbstractList接口，实现了List，RandomAccess，Cloneable接口，可序列化。在存储方面 数组可以包含基本类型和对象类型，比如：int[],Object[]，ArrayList只能包含对象类型；在空间方面，数组的空间大小是固定的，空间不够时不能再次申请，所以需要事前确定合适的空间大小。ArrayList的空间是动态增长的，如果空间不足，它会创建一个1.5倍大的新数组，然后把所有元素复制到新数组，而且每次添加新的元素时会检测内部数组的空间是否足够。

源码解析

变量

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

    //空数组与EMPTY_ELEMENTDATA 区别在于添加第一个元素时，扩充多少
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    //实例数组对象
    transient Object[] elementData; // non-private to simplify nested class access

    //数组大小
    private int size;

构造函数

ArrayList的构造方法有三种：

//自定义初始容量
public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
        //初始化容量大小   
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
        //容量初始值不能 < 0 小于零会抛出异常
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

//常用无参构造函数，默认数组大小为 10
public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

//创建一个包含collection的ArrayList
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)
        //构造大小为size的Object[]数组赋值给elementData
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // 替换空数组
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

常用函数(方法)

add函数

ArrayList调用add()方法添加函数，源码为

//在数组尾部添加元素 
public boolean add(E e) {
    //长度+1，也就是修改次数+1 确保内部容量
        ensureCapacityInternal(size + 1);  // Increments modCount!!
    //数组下标+1 并赋值
        elementData[size++] = e;
        return true;
    }

private void ensureCapacityInternal(int minCapacity) {
    //若数组元素为空，取最小容量，与默认容量的最大值做为最小容量
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
    //明确ArrayList的最小容量
        ensureExplicitCapacity(minCapacity);
    }
//用于内部优化确保空间资源不被浪费
private void ensureExplicitCapacity(int minCapacity) {
    //修改统计数+1，主要用来实现fail-fast机制
        modCount++;

        // 防止溢出，保证最小容量 > 数组缓冲区当前长度
        if (minCapacity - elementData.length > 0)
        //增加容量
            grow(minCapacity);
    }


 //增加容量以确保它至少可以容纳最小容量参数指定的元素数量。
 private void grow(int minCapacity) {
        // 元素长度为旧容量大小
        int oldCapacity = elementData.length;
    // 新容量= 旧容量 + 旧容量右移一位（旧容量/2）
        int newCapacity = oldCapacity + (oldCapacity >> 1);
    //判断新容量与最小容量大小 
        if (newCapacity - minCapacity < 0)
        //最小容量>新容量 ，则新容量为最小容量
            newCapacity = minCapacity;
    //若新容量 > 最大容量 ，对新容量重新计算
        if (newCapacity - MAX_ARRAY_SIZE > 0)
        //重新计算新容量
            newCapacity = hugeCapacity(minCapacity);
        // 扩容并赋值数组元素
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

private static int hugeCapacity(int minCapacity) {
    //若最小容量 < 0 则抛出异常
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
    //最小容量大于 最大数组长度，则返回int最大值作为容量大小
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

查看复制数组方法

Arrays.copyOf(elementData, newCapacity)

//Arrays.java类中的方法
public static <T> T[] copyOf(T[] original, int newLength) {
        return (T[]) copyOf(original, newLength, original.getClass());
    
//复制指定的数组，截断或使用null填充（如果需要），以便副本具有指定的长度。
// 对于在原始数组和副本中均有效的所有索引，两个数组将包含相同的值
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
        @SuppressWarnings("unchecked")
        T[] copy = ((Object)newType == (Object)Object[].class)
            ? (T[]) new Object[newLength]
            : (T[]) Array.newInstance(newType.getComponentType(), newLength);
    //从指定的源数组开始复制数组，从指定的位置开始到目标数组的指定位置
        System.arraycopy(original, 0, copy, 0,
                         Math.min(original.length, newLength));
        return copy;
    }

//内部调用System.arraycopy方法
@FastNative
public static native void arraycopy(Object src,  int  srcPos,
                                        Object dest, int destPos,
                                        int length);

在对应下标出添加数据元素
public void add(int index, E element) {
    //超出数据长度或 小于0 ，则抛出数组越界异常
        if (index > size || index < 0) 
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    ///增加容量以确保它至少可以容纳最小容量参数指定的元素数量，修改次数+1
        ensureCapacityInternal(size + 1);  // Increments modCount!!
    //数组拷贝赋值
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }
//添加数组集合
public boolean addAll(Collection<? extends E> c) {
    //转化数据
        Object[] a = c.toArray();
        int numNew = a.length;
    //修改次数+1
        ensureCapacityInternal(size + numNew);  // Increments modCount
    //数组拷贝赋值
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
        return numNew != 0;
    }

通过分析add方法可以发现ArrayList内部是调用System.arraycopy方法复制数组。

set函数
//对应下标设置对应的数组元素，原来的元素被替换掉并返回替换的数组元素
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;
    }
get函数

public E get(int index) {
    //下标 >数组长度， 则抛出数组越界异常
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    //根据下标直接返回对应数组元素，查找速度快
        return (E) elementData[index];
    }
remove函数
//移除数组下标对应的数组元素,返回删除的数组元素  
public E remove(int index) {  
     //下标 >数组长度， 则抛出数组越界异常  
     if (index >= size)  
         throw new IndexOutOfBoundsException(outOfBoundsMsg(index));  
     //修改次数统计 +1  
     modCount++;  
     //通过索引下标查找对应数组元素  
     E oldValue = (E) elementData[index];  
     //数组移动个数  
     int numMoved = size - index - 1;  
     if (numMoved > 0)  
         //后续数组元素整体往前移动   
         System.arraycopy(elementData, index+1, elementData, index,  
         numMoved);  
     //数组最后一位元素置空，且长度-1  
     elementData[--size] = null; // clear to let GC do its work  
     //返回移除对应数组元素  
     return oldValue;  
 }  

//删除对应元素，如果删除成功返回true  
public boolean remove(Object o) {  
    if (o == null) { //判断是否为空  
         for (int index = 0; index < size; index++)  
             if (elementData[index] == null) { //若数组下标对应元素为空则移除null元素  
                fastRemove(index);  
                return true;  
        }  
     } else {//不为空  
         for (int index = 0; index < size; index++)  
             //判断要删除的对象在数组是否存在，存在则删除  
             if (o.equals(elementData[index])) {   
                 fastRemove(index);  
                 return true;  
             }  
     }  
     return false;  
 }  
  
  
 //私有方法快速删除数组元素，该方法与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  
 }
indexof函数
//查找数组元素对应下标 ，数组元素  
public int indexOf(Object o) {
        if (o == null) {  //判断是否为空
            for (int i = 0; i < size; i++)//遍历
        //数组元素为null返回对应下标
                if (elementData[i]==null) 
                    return i;
        } else {
            for (int i = 0; i < size; i++)
        //遍历存在对象o 则返回对应下标
                if (o.equals(elementData[i]))
                    return i;
        }
    //数组中不存在，则返回-1
        return -1;
    }
subList方法
//从ArrayList中截取子列表集合
public List<E> subList(int fromIndex, int toIndex) {
    //子列表集合范围检测
        subListRangeCheck(fromIndex, toIndex, size);
    //返回值为一个SubList对象
        return new SubList(this, 0, fromIndex, toIndex);
    }

SubList为ArrayList的一个内部类

 private class SubList extends AbstractList<E> implements RandomAccess {
        private final AbstractList<E> parent;
        private final int parentOffset;
        private final int offset;
        int size;

        SubList(AbstractList<E> parent,
                int offset, int fromIndex, int toIndex) {
        //该参数为父类ArrayList 把自身传了进来   
            this.parent = parent;
        //开始截取的位置索引         
            this.parentOffset = fromIndex;
            this.offset = offset + fromIndex;
        //截取后得到的ArrayList长度
            this.size = toIndex - fromIndex;
            this.modCount = ArrayList.this.modCount;
        }


       public void add(int index, E e) {
        //检测索引是否越界，越界则抛出异常  
            rangeCheckForAdd(index);
        //检测数组列表是否被修改
            checkForComodification();
            parent.add(parentOffset + index, e);
            this.modCount = parent.modCount;
            this.size++;
        }

        private void checkForComodification() {
        //判断ArrayList的修改次数与子类的修改次数是否相等，否则抛出并发修改异常   
            if (ArrayList.this.modCount != this.modCount)
                throw new ConcurrentModificationException();
          }

    .....
}

举个例子：

    ArrayList<String> list = new ArrayList<>();
        list.add("f1");
        list.add("f2");
        list.add("f3");
        
        List<String> subList =list.subList(0,2);
        subList.add("s1");
        subList.remove(1);
        System.out.println("list = " + list);
        System.out.println("subList = " + subList);

输出为：
list = [f1, s1, f3]
subList = [f1, s1]

从输出结果可以看出，截取后的subList是可以增删查找的，而list是跟随subList改变而改变的。原因是，在初始化SubList的时候直接把ArrayList 自身传了进去，在subList进行增删查找时相当于是对ArrayList自身操作。

那在subList 执行增删方法后还可以操作list增删吗？答案：是可以的，不过是有一个前提是 不能再对subList进行任何操作，包括输出subList对象。
紧接上面的例子

        subList.add("s2");
        list.add("f4");
        System.out.println("list = " + list);
        list.remove("s1");
        System.out.println("list = " + list);

输出结果为：
list = [f1, s1, f3]
subList = [f1, s1]
list = [f1, s1, s2, f3, f4]
list = [f1, s2, f3, f4]

如果对list进行操作后又对subList操作将会抛出ConcurrentModificationException,原因是ArrayList进行增删时修改了modCount ，而 SubList的modCount并没有被修改，检测的时候二者不相等所以抛出异常。

总结

  • 数组与ArrayList之间的区别
  • 本文主要分析了ArrayList的常用add，remove等方法的源码，以及子类SubList的使用方法。

相关文章阅读
Java集合系列之HashMap源码分析

Android 源码解析系列分析

自定义View绘制过程源码分析
ViewGroup绘制过程源码分析
ThreadLocal 源码分析
Handler消息机制源码分析
Android 事件分发机制源码分析
Activity启动过程源码分析
Activity中View创建到添加在Window窗口上到显示的过程源码分析

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