Java中ArrayList源码解析

Java中ArrayList源码解析

一、ArrayList介绍

ArrayList是Java和Android开发中使用最为频繁的一种集合。它的底层数据结构是动态数组,并且是线程不安全允许元素为null. ArrayList类结构如下:

//实现了List、RandomAccess、Cloneable、Serializable接口
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable{ 
                      //... 
}

其中, ArrayList实现了RandomAccess标记接口,用来表明其支持快速(通常是固定时间)随机访问。此接口的主要目的是允许一般的算法更改其行为,从而在将其应用到随机或连续访问列表时能提供良好的性能ArrayList实现了Cloneable标记接口,用来指示Object.clone()方法可以合法地对该类实例按字段复制。如果在没有实现 Cloneable接口的实例上调用 Objectclone 方法,则会导致抛出 CloneNotSupportedException 异常。Serializable 接口: 类通过实现 java.io.Serializable 接口以启用其序列化功能。未实现此接口的类将无法使其任何状态序列化或反序列化

二、ArrayList基本使用

List<String> dataList = new ArrayList<>();//创建一个ArrayList集合
List<String> dataList = new ArrayList<>(3);//指定初始化集合的大小为3的ArrayList集合
List<String> dataList = new ArrayList<>(originalList);//指定已经存在集合

三、ArrayList特性

1、是否保证线程安全

不是同步的,不能保证线程安全

2、底层数据结构

ArrayList底层使用的是Object数组数据结构,动态数组

3、插入和删除是否受元素位置的影响

ArrayList 采用数组存储,所以插入和删除元素的时间复杂度受元素位置的影响。 比如:执行add(E e)方法的时候, ArrayList 会默认在将指定的元素追加到此列表的末尾,这种情况时间复杂度就是O(1)。但是如果要在指定位置 i 插入和删除元素的话(add(int index, E element))时间复杂度就为 O(n-i)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作。

4、是否支持快速随机访问

ArrayList 实现了RandomAccess 接口,所以有随机访问功能。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index)方法)。

5、内存空间占用

ArrayList的空间浪费主要体现在在list列表的结尾会预留一定的容量空间

四、ArrayList类的继承关系

61e5a142265cea02d0cac40d29f0fbc8.png

五、ArrayList源码分析

1、构造器

通过分析ArrayList的构造器,发现其实构造ArrayList有三种方式,一种最为常见就是创建一个不带构造参数的ArrayList的实例,默认是DEFAULTCAPACITY_EMPTY_ELEMENTDATA空数组;然后第二种就是传入指定初始容量大小,默认会创建指定容器大小的Object数组;第三种就是传入已存在Collection集合,默认会直接把Collection集合转化成Object数组,并且如果转化失败就会利用Arrays.copyOf方法会把集合中元素批量加入到Object数组以此来初始化elementData.

关于Arrays.copyOf(elementData, size, Object[].class)方法,就是根据class的类型来决定是new 还是反射去构造一个泛型数组,同时利用native函数,批量赋值元素至新数组中。

2、ArrayList操作之增

add(E e)

  • 执行add(E e)方法,往集合尾部添加元素,每执行一次add操作之前都会调用ensureCapacityInternal来确认是否需要扩容

add(int index, E element)
  • 执行add(int index, E element)方法, 先检查index是否合法,是否越界。然后确认是否需要扩容,然后将index开始之后的所有数据元素整体向后移动一位,然后再把指定index的元素进行新值覆盖,最后size自增1

addAll(Collection<? extends E> c)

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

3、ArrayList扩容流程

  • 1、扩容源码分析

  • 2、扩容原理流程图

  • 3、扩容原理的总结

对于ArrayList扩容,首先需要明确一点ArrayListsizeelementData.length数组长度不是相等的,size表示当前数组的元素个数。如果ArrayList是以默认无参构造的,那么当第1次执行add操作后,会默认第一次扩容容量为DEFAULT_CAPACITY = 10, 后面再执行第210次执行add操作后,就不会进行扩容操作;当第11次执行add操作后就会就触发扩容操作,此次扩容的容量为当前数组长度(注意是数组长度而不是size,size增加只有真正把值add到数组中后才增加)的一半也就是5;所以当第1115次执行add操作后,又不会进行扩容操作。依次类推后续每次会扩容的容量为当前数组长度的一半,在扩容容量范围内就不会触发扩容操作

验证上述理论,可以明显发现ArrayListadd操作执行的第1次,第11次,第16次会明显耗时更长。

4、ArrayList操作之删

remove(int index)

remove(Object o)

removeAll(Collection<?> c)
   //在当前集合中批量删除传入集合c中的元素
    public boolean removeAll(Collection<?> c) {
        Objects.requireNonNull(c);
        return batchRemove(c, false);//removeAll方法实际上是委托给batchRemove方法实现的,传入参数分别要删除,注意传入第二个参数,complement = false表示在当前集合删除传入的集合
    }
    //在当前集合中批量删除除了传入集合c中的元素(保留传入集合c中的元素,其他全删除)
    public boolean retainAll(Collection<?> c) {
        Objects.requireNonNull(c);
        return batchRemove(c, true);//注意传入第二个参数,complement = true表示在当前集合保留传入的集合元素,其他全部删除
    }

    //批量移除集合中元素
    private boolean batchRemove(Collection<?> c, boolean complement) {
        final Object[] elementData = this.elementData;//将当前集合中元素赋值给elementData
        int r = 0, w = 0;//设置两个游标分别读游标r和写游标w
        boolean modified = false;
        try {
            for (; r < size; r++)//遍历当前集合中的所有元素
            //注意: 这里需要考虑两种情况:
            //第一: 如果当前集合中元素在需要删除集合c中且complement为false则表示在当前集合中移除传入集合c中元素,
            //会把当前集合中不在c集合中的元素,整体往前移动,w游标增加
            //第二: 如果当前集合中元素在需要保留集合c中且complement为true则表示在当前集合中保留传入集合c中元素,
            //会把当前集合中在c集合中的元素,整体往前移动,w游标增加
                if (c.contains(elementData[r]) == complement)
                    elementData[w++] = elementData[r];
        } finally {
            // 出现异常会导致r != size,则将出现异常处后面的数据全部复制覆盖到数组里
            if (r != size) {
                System.arraycopy(elementData, r,
                                 elementData, w,
                                 size - r);
                w += size - r;//修改w游标
            }
            //最后w游标值就是产生新的数组的size
            if (w != size) {
                //从w之后到size的所有位置重置为null,以便GC回收
                for (int i = w; i < size; i++)
                    elementData[i] = null;
                //modCount增加表示修改到元素次数    
                modCount += size - w;
                size = w;//最后的w也就是size集合大小
                modified = true;
            }
        }
        return modified;
    }

5、ArrayList操作之改

    //注意修改数组中对应元素的值是不需要修改modCount
    public E set(int index, E element) {
        rangeCheck(index);//越界检查

        E oldValue = elementData(index);//通过elementData按到index元素
        elementData[index] = element;//并用传入的新值覆盖旧值
        return oldValue;//并返回旧值oldValue
    }

6、ArrayList操作之查

    //注意查找数组中对应元素的值是不需要修改modCount
    public E get(int index) {
        rangeCheck(index);//越界检查

        return elementData(index);
    }
    @SuppressWarnings("unchecked")
    E elementData(int index) {
        return (E) elementData[index];//直接获取对应index的值
    }

7、ArrayList操作之clear

  public void clear() {
        modCount++;//修改modCount
        //elementData数组中的元素全部复制为null, 以便GC回收
        for (int i = 0; i < size; i++)
            elementData[i] = null;
        size = 0;//最后重置size为0
   }

8、ArrayList操作之包含contains

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

    public int indexOf(Object o) {
        if (o == null) {//如果o为null, 遍历elementData数组找到第一个出现null的位置
            for (int i = 0; i < size; i++)
                if (elementData[i]==null)
                    return i;
        } else {//如果o不为null, 遍历elementData数组找到第一个出现与o值相等的位置
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;//否则找不到就返回-1
    }

9、ArrayList操作之迭代器Iterator

    private class Itr implements Iterator<E> {
        int cursor;       // 返回下一个元素的index
        int lastRet = -1; // 返回上一个元素的index,没有上一个元素就默认返回-1
        int expectedModCount = modCount;//整个过程中操作集合(包括add、remove操作)次数modCount

        public boolean hasNext() {
            return cursor != size;//当前游标cursor不等于size,说明集合并没有迭代完毕,还有下一个元素
        }

        @SuppressWarnings("unchecked")
        //获取迭代器中当前的元素next
        public E next() {
            checkForComodification();//检查修改集合次数modCount
            int i = cursor;
            if (i >= size)//越界检查
                throw new NoSuchElementException();
            Object[] elementData = ArrayList.this.elementData;//取出集合中数组elementData
            if (i >= elementData.length)//越界检查
                throw new ConcurrentModificationException();
            cursor = i + 1;//cursor游标累加
            return (E) elementData[lastRet = i];//取出当前i的元素中的值返回,并设置上一次返回的元素的下标
        }

        //迭代中移除当前迭代元素
        public void remove() {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();//modCount检查

            try {
                ArrayList.this.remove(lastRet);//移除元素
                cursor = lastRet;//删除的游标
                lastRet = -1;//不能重复删除 所以修改删除的标志位
                expectedModCount = modCount;//更新 判断集合是否修改的标志,
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

        //主要是为了检查线程安全,ArrayList不是线程安全的,但是避免多线程操作ArrayList中在迭代器迭代过程中,
        //对集合具有写操作的修改导致modCount次数和expectedModCount不一致就会抛出ConcurrentModificationException异常
        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }

7、ArrayList中的modCount了解一下

我们都知道ArrayList是非线程安全的,在使用迭代器遍历的时候,用来检查列表中的元素是否发生结构性变化(列表元素数量发生改变)了,主要在多线程环境下需要使用,防止一个线程正在迭代遍历,另一个线程修改了这个列表的结构,那么这个modCount就是记录被修改的次数。使用迭代器遍历时,iterator.hasNext()方法中的checkForComodification()方法会检查modCountexpectedModCount是否相等,从而判断在多线程环境下,迭代器遍历的过程中列表中的元素是否发生结构性变化。

一起来看个有趣例子:

class ArrayListTest {
    public static void main(String[] args) {
        List<Integer> resultList = new ArrayList<>();
        resultList.add(10);
        Iterator iterator = resultList.iterator();
        while (iterator.hasNext()) {
            Integer value = (Integer) iterator.next();
            if (value == 10){
                resultList.remove(value);//注意这里是调用了ArrayList中的remove方法, 值删除后resultList为空,modCount++
            }
        }
    }
}

得到的运行结果会抛出一个异常:

为什么会抛出这个异常呢?这个其实就是modCount导致的,不妨再次来看下ArrayList remove的源码。

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

        modCount++;//会发现remove调用后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;
    }

再接着来下ArrayList中的Iteator迭代源码,会发现resultList为空,所以size为0,但是cursor不为0,hasNext()返回true, 就会继续执行next()方法

        public boolean hasNext() {
            return cursor != size;//会发现size为0,但是cursor不为0,hasNext()返回true
        }

        @SuppressWarnings("unchecked")
        public E next() {
            checkForComodification();//检查modCount,还记得在ArrayList中的remove方法中modCount会自增后就造成expectedModCount和modCount不一致,抛出异常
            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];
        }

        //注意使用iteator自带的remove方法就不会抛出异常
        public void remove() {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();//会先去检查modCount

            try {
                ArrayList.this.remove(lastRet);//虽然内部也是调用remove方法,modCount自增了
                cursor = lastRet;
                lastRet = -1;
                expectedModCount = modCount;//但是这里需要特别注意它把修改后的最新的modCount重置给expectedModCount,所以需要在迭代过程中删除元素还是调用iteator自带的remove方法
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

   转载规则


《Java中ArrayList源码解析》 mikyou 采用 知识共享署名 4.0 国际许可协议 进行许可。
 上一篇
二分查找 二分查找
二分查找一、时间复杂度最坏时间复杂度 O(log n) 最优时间复杂度 O(1) 平均时间复杂度 O(log n) 二、基本思想在一个有序的列表中,要查找的数与列表中间的位置相比,若相等说明找到了,若要查找的数大于列表中间的数,说明要查找的
下一篇 
Java中的HashMap和ConcurrentHashMap源码解析 Java中的HashMap和ConcurrentHashMap源码解析
Java中的HashMap和ConcurrentHashMap源码解析一、HashMap与HashTable区别 1、线程是否安全: HashMap 是非线程安全的,HashTable 是线程安全的;HashTable 内部的方法基本都经过
2020-01-02