JDK源码阅读(三):ArraryList源码解析

星期三, 六月 19日 2019, 11:33 晚上

发布时间: 2019-06-19
 
阅读次数:
 
文章字数:1.8k字
 
阅读时长:6分

今天来看一下ArrayList的源码

  • 目录
    • 介绍
    • 继承结构
    • 属性
    • 构造方法
    • add方法
    • remove方法
    • 修改方法
    • 获取元素
    • size()方法
    • isEmpty方法
    • clear方法
    • 循环数组

      1.介绍

      一般来讲文章开始应该先介绍一下说下简介。这里就不介绍了 如果你不知道ArrayList是什么的话就没必要在看了。大致讲一下一些常用的方法

      2.继承结构

      ArrayList源码定义:

ArrayList继承结构如下:

  • Serializable 序列化接口

  • Cloneable 前面我们在看Object源码中有提到这个类,主要表示可以进行克隆

  • List 主要定义了一些方法实现

  • RandomAccess 也是一个标记类,实现RandomAccess表示该类支持快速随机访问。

3.属性

ArrayList中的主要属性方法有:

初始化容量,默认为10

private static final int DEFAULT_CAPACITY = 10;

空数组

private static final Object[] EMPTY_ELEMENTDATA = {};

也是一个空数组,和上面的数组相比主要的作用是在添加元素的时候知道数组膨胀了多少。

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

ArrayList的大小

private int size;

注意ArrrayList中有一个modCount成员变量,来记录修改次数,主要是在使用迭代器遍历的时候,用来检查列表中的元素是否发生结构性变化(列表元素数量发生改变)了,主要在多线程环境下需要使用,防止一个线程正在迭代遍历,另一个线程修改了这个列表的结构。好好认识下这个异常:ConcurrentModificationException。对了,ArrayList是非线程安全的。

4.构造方法

我们来看一下ArrayList的构造方法
无参构造方法:

可以看出无参构造会直接创建一个指定DEFAULTCAPACITY_EMPTY_ELEMENTDATA的数组,而DEFAULTCAPACITY_EMPTY_ELEMENTDATA数组默认是空的。

所以在执行一下代码的时候ArrayList默认创建的是一个初始化容量为0 的数组。

ArrayList list = new ArrayList();

有参构造方法:

传入创建数组的大小,如果大于0 就创建一个传入参数大小的数组,如果等于0 就就指定为空数组。如果小于0就会抛异常。

看源码我们可以看到传入Collection的构造方法做的事情就是复制数组,将已有的集合复制到新的集合中。

5.add方法

ArrayList底层是用数组来实现的,那我们就一起来看以下Add方法是如何实现的

以下是Add方法的实现源码。

可以看到ArrayList在添加元素之前先检查一下集合的大小

在 ensureExplicitCapacity 方法中,首先对修改次数modCount加一,这里的modCount给ArrayList的迭代器使用的,在并发操作被修改时,提供快速失败行为(保证modCount在迭代期间不变,否则抛出ConcurrentModificationException异常,可以查看源码865行),接着判断minCapacity是否大于当前ArrayList内部数组长度,大于的话调用grow方法对内部数组elementData扩容,grow方法代码如下:

上面的代码可以看出ArrayList的扩容。首先获得老数组的容量,然后 oldCapacity + (oldCapacity >> 1);计算出老数组大小的1.5倍,判断 新容量小于参数指定容量,修改新容量,如果新容量大于最大容量的话就指定容量。

6.remove方法

ArrayList的删除操作一共有两种一种是根据索引删除,一种是根据内容删除。

根据索引删除元素


remove方法表示删除索引index处的元素,首先通过 rangeCheck 方法判断给定索引的范围,超过集合大小则抛出异常;接着通过 System.arraycopy 方法对数组进行自身拷贝。
根据元素删除

我们可以看到首先判断一下是否为空。不为空的话就开始循环查找元素,用equals来判断元素是否相同,如果一致就调用fastRemove来删除元素。然后通过System.arraycopy进行自身复制。

7.修改方法


 通过调用 set(int index, E element) 方法在指定索引 index 处的元素替换为 element。并返回原数组的元素。先通过rangCheck来检查索引的合法性,如果不合法(负数,或者其他值)会抛出异常。

8.获取元素

因为本身ArrayList就是用数组来实现的,所以获取元素就相对的来说简单一点。


首先也是调用rangeCheck方法来判断索引是否合法,然后在直接根据索引回去元素


根据元素查找索引


直接返回第一次出现的元素。否则返回-1

9.size()方法


直接返回的size大小。

9.isEmpty方法

直接返回size==0的结果,是不是非常简单。

10.clear方法


循环把元素赋值为空,便于GC回收

11.循环数组

for循环

for循环可能在java中是最常用的遍历方法主要实现:


因为我们前面说过get方法可以通过索引来获取元素。同理。

迭代器 iterator

先看实现:


我们来看一下源码怎么实现的:


返回一个 Itr 对象,这个类是 属于ArrayList 的内部类。

 /**
     * An optimized version of AbstractList.Itr
     */
    private class Itr implements Iterator<E> {
        //游标, 下一个要返回的元素的索引
        int cursor; 
        // 返回最后一个元素的索引; 如果没有这样的话返回-1.
        int lastRet = -1; 
        int expectedModCount = modCount;

        Itr() {}
        //通过 cursor != size 判断是否还有下一个元素
        public boolean hasNext() {
            return cursor != size;
        }

        @SuppressWarnings("unchecked")
        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;
            //返回索引为i处的元素,并将 lastRet赋值为i
            return (E) elementData[lastRet = i];
        }

        public void remove() {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
            //调用ArrayList的remove方法删除元素
                ArrayList.this.remove(lastRet);
                //游标指向删除元素的位置,本来是lastRet+1的,这里删除一个元素,然后游标就不变了
                cursor = lastRet;
                //lastRet恢复默认值-1
                lastRet = -1;
                //expectedModCount值和modCount同步,因为进行add和remove操作,modCount会加1
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

        @Override
        @SuppressWarnings("unchecked")
        public void forEachRemaining(Consumer<? super E> consumer) {
            Objects.requireNonNull(consumer);
            final int size = ArrayList.this.size;
            int i = cursor;
            if (i >= size) {
                return;
            }
            final Object[] elementData = ArrayList.this.elementData;
            if (i >= elementData.length) {
                throw new ConcurrentModificationException();
            }
            while (i != size && modCount == expectedModCount) {
                consumer.accept((E) elementData[i++]);
            }
            // update once at end of iteration to reduce heap write traffic
            cursor = i;
            lastRet = i - 1;
            checkForComodification();
        }
        //前面在新增元素add() 和 删除元素 remove() 时,我们可以看到 modCount++。修改set() 是没有的
        final void checkForComodification() {
            if (modCount != expectedModCount)
            //也就是说不能在迭代器进行元素迭代时进行增加和删除操作,否则抛出异常
                throw new ConcurrentModificationException();
        }
    }

从上面的代码我们得出,在遍历的时候如果删除或者新增元素都会抛异常出来,而修改不会。看下方例子。

抛出异常:

小弟不才,如有错误请指出。喜欢请关注,慢慢更新JDK源码阅读笔记



JDK源码  

JDK Java 源码

本博客所有文章除特别声明外,均采用 CC BY-SA 3.0协议 。转载请注明出处!

 目录