源码解析 ArrayList

                               首先要清楚ArrayList基本特点
  • 查询某节点数据、更改某节点数据，快
  • 增加、删除可能会慢，存在扩容和移动元素。
  • 底层实现是Object数组
  • 默认大小为10

ArrayList类的继承关系：


image.png
比对着源码看一下
public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

  • 可以看到继承了AbstractList。而AbstractList 是继承AbstractCollection 抽象类，实现了 List 接口，是 ArrayList 和 AbstractSequentiaList 的父类。AbstractList 主要是搭建List, 关系看图1.


    图（1）.png

  • 实现了List接口，就意味着ArrayList元素有序的，可以重复的，并且可以有null的元素。

  • 实现了RandomAccess接口标识着其支持随机快速访问。

  • 实现了Cloneable接口,标识着可以它可以被复制。调用ArrayList里面的clone()方法，需要注意的是clone是浅层拷贝。浅层拷贝对于ArrayList变量的意思就是说：ArrayList变量指向的是不同的内存地址，但是变量中的元素指向的是同一个元素。深层拷贝是指，不仅仅变量指向的内存地址不一样，而且变量中的各个元素所指地址也是不一样的。

  • 实现了Serializable 可被序列化。

ArrayList 的构造方法

在说构造方法之前我们要先看下与构造参数有关的几个全局变量：

//默认的数组容量
private static final int DEFAULT_CAPACITY = 10;
//用于空实例的共享空数组实例。
private static final Object[] EMPTY_ELEMENTDATA = {};
//另一个共享空数组实例,与EnvyTyEeltDATA区分开来.
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//底层容器
transient Object[] elementData;
//当前存放了多少个元素
private int size;

底层容器数组的前面有一个transient关键字，transient标识之后是不被序列化的。
但其实是ArrayList在序列化的时候会调用writeObject()，直接将size和element写入ObjectOutputStream；反序列化时调用readObject()，从ObjectInputStream获取size和element，再恢复到elementData。

transient标识主要原因在于elementData是一个缓存数组，它通常会预留一些容量，等容量不足时再扩充容量，那么有些空间可能就没有实际存储元素，采用上诉的方式来实现序列化时，就可以保证只序列化实际存储的那些元素，而不是整个数组，从而节省空间和时间。

无参构造方法
/** * 构造一个初始容量为10的空列表*/
public ArrayList() {    
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

命名里面讲elementData指向了一个空数组，但是注释说的是默认为10.

指定初始容量的构造方法
   public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {      //容量>0  构建数组
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {  //容量>0  指向了一个空的数据
            this.elementData = EMPTY_ELEMENTDATA;
        } else {报错 负数
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

如果我们预先知道一个集合元素的容纳的个数的时候推荐使用这个构造方法，避免使用ArrayList默认的扩容机制而带来额外的开销.

使用另一个集合 Collection 的构造方法
构建指定元素，顺序由迭代器返回顺序为准。排序啥用过
  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;
        }
    }
ArrayList的函数分析

增加元素+扩容机制
添加单个元素

 public boolean add(E e) {//添加元素到最后
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

   private void ensureCapacityInternal(int minCapacity) {
  //如果arraylist是无参构造，数组是 DEFAULTCAPACITY_EMPTY_ELEMENTDATA。然后DEFAULT_CAPACITY=10 ，
  //所以一开始上面构造的时候写的默认10.
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }

  private void ensureExplicitCapacity(int minCapacity) {
  //被修改次数，保证线程安全，迭代时候如果修改会报错。ConcurrentModificationException
        modCount++;

        // overflow-conscious code可能溢出代码
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

//扩容
  private void grow(int minCapacity) {
        // 原来的数组长度
        int oldCapacity = elementData.length;
        //新数组的大小=老数组大小+老数组大小的一半
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //判断上面的扩容之后的大小newCapacity是否够装minCapacity个元素
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        //判断比最大值Integer.MAX_VALUE - 8  还大的话给hugeCapacity处理
        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);
    }
  

   private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
      //终于溢出了
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

小章总结:

  1. 首先判断如果新添加一个元素是否会导致数组溢出
  2. 判断是否溢出:如果原数组是空的,那么第一次添加元素时会给数组一个默认大小10.接着是判断是否溢出,如果溢出则去扩容,扩容规则: 新数组大小是原来数组大小的1.5倍,最后通过Arrays.copyOf()去浅复制.
  3. 添加元素到最后
  • 添加元素到指定位置
 public void add(int index, E element) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

        ensureCapacityInternal(size + 1);  //要不要扩容
//相当于Index开始以及后面的数据，都往后移动了一位
        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;
        //是否要扩容
        ensureCapacityInternal(size + numNew);  // Increments modCount
        //a数组全部复制到size后面
        System.arraycopy(a, 0, elementData, size, numNew);
        //记录现有的元素个数
        size += numNew;
        return numNew != 0;

    }

将需要插入的集合转成数组a,判断了一下是否需要扩容，再将a数组插入到当前elementData的末尾。

  • 添加集合到指定位置
  public boolean addAll(int index, Collection<? extends E> c) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    
        Object[] a = c.toArray();
        int numNew = a.length;
        //跟上面一个意思
        ensureCapacityInternal(size + numNew);  // Increments modCount

      
        int numMoved = size - index;//需要后移的元素个数
        if (numMoved > 0)
        //将原有数据从Index以及之后开始的numMoved的元素，移动到index+numNew后面去。因为要插入a数组。
            System.arraycopy(elementData, index, elementData, index + numNew,
                             numMoved);
        //把a数组复制到elementData数组中
        System.arraycopy(a, 0, elementData, index, numNew);
        size += numNew;
        return numNew != 0;
    }

判断一下添加了集合之后是否需要扩容,因为需要将集合插入到index处,所以需要将index后面的元素往后挪动,需要挪动的元素个数为:size - index,挪动的间隔是index + numNew。

  • 移除指定位置元素
    public E remove(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

        modCount++;
        E oldValue = (E) elementData[index];//记录删除的元素

        int numMoved = size - index - 1;//获取移动的位置
        if (numMoved > 0)//删除元素后面有数据往前移动
            //将Index后面的数据往前移动一个，不包含Index
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        //删除 ， 就是赋值null,让gc回收
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
    }
  1. 保存删除元素旧值
  2. 然后将数组的index后面的元素往前挪动一位
  3. 将数组的末尾元素赋值为null,方便GC回收。

  • 移除指定元素

  • 移除第一个集合中与指定元素相同(通过equals()判断)的元素.移除成功了则返回true,未移除任何元素则返回false

  • 如果传入的是null,则移除第一个null元素

  • 如果传入的是非null元素,,通过equals()移除第一个相同的元素

   public boolean remove(Object o) {
        if (o == null) {
            for (int index = 0; index < size; index++)
                //获取第一个为Null的
                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;
    }

    private void fastRemove(int index) {
        modCount++;
        int numMoved = size - index - 1;//获取删除元素后面要移动元素的个数
        if (numMoved > 0)
            //移动index后面的数据往前移动1.
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work
    }

判断需要移除的元素是否为null
如果为null,则循环遍历数组,移除第一个为null的元素
如果非null,则循环遍历数组,移除第一个与指定元素相同(equals() 返回true)的元素

  • 删除原有集合里面所有包含的数据
  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++)
                //complement = false取补集，C包含不记录，不包含记录
                //complement = true 取交集，C包含记录 ，不包含不记录
                if (c.contains(elementData[r]) == complement)
 //r是正在遍历的位置  w是用于记录有效元素的   在w之前的全是有效元素,w之后的会被"删除"
                    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
          // 将w之后的元素全部置空  因为这些已经没用了,置空方便GC回收
                for (int i = w; i < size; i++)
                    elementData[i] = null;
                modCount += size - w;
                size = w;
                modified = true;
            }
        }
        return modified;
    }
  1. 首先我们进行c集合检查,判断是否为null
  2. 然后我们调用batchRemove()方法去移除 c集合与当前列表的交集
  3. 循环遍历当前数组,记录c集合中没有的元素,放在前面(记录下标为w),w前面的是留下来的元素,w后面的是需要删除的数据
  4. 第3步可能会出错,出错的情况下,则将出错位置的后面的全部保留下来,不删除
  5. 然后就是将w之后的元素全部置空(方便GC回收),然后将size(标记当前数组有效元素)的值赋值为w,即完成了删除工作
    再笼统一点说吧,其实就是将当前数组(elementData)中未包含在c中的元素,全部放在elementData数组的最前面,假设为w个,最后再统一置空后面的元素,并且记录当前数组有效元素个数为w.即完成了删除工作.
  • 清空列表
    将数组所有元素都置为null,然后GC把它回收了
 public void clear() {
        modCount++;

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

        size = 0;
    }

改动元素

  • 替换指定下标的元素内容

就是将index处的元素替换成element

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

查询元素

  • 返回指定位置处元素

将index索引处的数组的值返回

public E get(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

        return (E) elementData[index];
    }

总结

下面我们来总结一下ArrayList的关键点

  • 底层是Object数组存储数据
  • 扩容机制:默认大小是10,扩容是扩容到之前的1.5倍的大小,每次扩容都是将原数组的数据复制进新数组中.。
  • 如果是添加到数组的指定位置,那么可能会挪动大量的数组元素,并且可能会触发扩容机制;如果是添加到末尾的话,那么只可能触发扩容机制.
  • 如果是删除数组指定位置的元素,那么可能会挪动大量的数组元素;如果是删除末尾元素的话,那么代价是最小的. ArrayList里面的删除元素,其实是将该元素置为null.
  • 查询和更改某个位置的元素是非常快的。

有兴趣的小伙伴可以帮忙关注一下csdn，谢谢
https://blog.csdn.net/binbinxiaoz

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念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