ArrayList源码解析

ArrayList底层通过数组实现,是线程安全的,具有随机访问快(根据下标),随机增删慢的特点

2. 成员变量

/**
     * 默认初始容量
     */
    private static final int DEFAULT_CAPACITY = 10;

    /**
     * 用于空对象的共享空数组
     * 用于创建指定长度为0的ArrayList的构造方法
     * java.util.ArrayList#ArrayList(int)
     * java.util.ArrayList#ArrayList(java.util.Collection)
     *
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /**
     * 用于默认大小的空对象的共享空数组(跟上面的区分开来)
     * 用于创建默认长度为10的ArrayList的构造方法
     * java.util.ArrayList#ArrayList()
     *
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     * 存储内容的数组
     */
    transient Object[] elementData; // non-private to simplify nested class access

    /**
     * ArrayList的长度
     */
    private int size;
    
    /**
     * 数组的最大长度
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
复制代码

这里有一点要特别注意: elementData.length 是指数组的长度 size 是指List的长度 这两个长度不是一样的

3. 构造函数

public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            // 初始容量大于0时,新建Object数组指向elementData
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            // 初始容量等于0时,EMPTY_ELEMENTDATA数组指向elementData
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            // 初始容量小于0,抛出异常
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

    public ArrayList() {
        // 无参构造,elementData指向默认的空数组
        // 这也表明,elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA的话
        // 表示ArrayList还没有添加过任何元素
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    public ArrayList(Collection<? extends E> c) {
        // collection转数组
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // 数组长度不等于0
            // [2] c.toArray might (incorrectly) not return Object[] (see 6260652)
            if (elementData.getClass() != Object[].class)
                // [1]
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }
复制代码

[1] 处ArrayList的源码中,涉及到数组复制的,都是使用Arrays提供的工具类

[2] 处关于toArray方法不一定返回Object数组,可以看看这篇文章 c.toArray might not return Object[]?

如果是涉及到数组的移动(有添加、删除引发),会使用 java.lang.System#arraycopy 方法

4. 常用的方法

4.1 添加

方法执行流程

ArrayList源码解析

可以看到 addaddAll 方法都会使用到 ensureCapacityInternal ,该方法中的核心代码是对 ensureExplicitCapacity 方法的调用

ensureExplicitCapacity 有两点作用:

modCount
grow

modCount 记录了对象被修改的次数

java.util.ArrayList#add(E)

public boolean add(E e) {
        /*
        1. 确保elementData数组拥有足够的容量
        2. 增加修改次数
         */
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        // 数组添加元素
        elementData[size++] = e;
        return true;
    }
    /**
     * 确保数组拥有足够的容量
     * @param minCapacity 最小需要的容量
     */
    private void ensureCapacityInternal(int minCapacity) {

        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            // 表示elementDat还没有添加过元素
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }

    private void ensureExplicitCapacity(int minCapacity) {
        // 增加修改次数
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            // 当最小需要的容量超出了数组的长度,则需要扩容
            grow(minCapacity);
    }
    
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        // 扩容1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        // 扩容后还是小于需要的最小容量,则使用minCapacity作为newCapacity
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        // 扩容后发现newCapacity大于最大的数组长度
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // 通过Arrays工具类进行数组扩容
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
复制代码

java.util.ArrayList#add(int, E)

public void add(int index, E element) {
        // 检查index有没有越界
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        // 将elementData[index:]的元素移动到elementData[index+1:]
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        // 在index位置添加元素
        elementData[index] = element;
        size++;
    }
    
    private void rangeCheckForAdd(int index) {
        // [1]
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
复制代码
  • [1]处判断是否越界不是根据 elementData 的长度,而是根据ArrayList的长度 size 去判断

java.util.ArrayList#addAll(java.util.Collection<? extends E>)

public boolean addAll(Collection<? extends E> c) {
        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;
        return numNew != 0;
    }
复制代码

方法很简单,自己look look就行了

4.2 删除

java.util.ArrayList#remove(int)

public E remove(int index) {
        // 检查是否越界
        rangeCheck(index);

        modCount++;
        // 根据index找到对应的value
        E oldValue = elementData(index);

        int numMoved = size - index - 1;
        if (numMoved > 0)
            // 将elementData[index+1:]移动到elementData[index:]
            System.arraycopy(elementData, index+1, elementData, index, numMoved);
        
        // 清空最后一个元素
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
    }
    
    private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
    
    E elementData(int index) {
        return (E) elementData[index];
    }
复制代码

java.util.ArrayList#remove(java.lang.Object)

public boolean remove(Object o) {
        if (o == null) {
        // 如果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)
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work
    }
复制代码

其他删除的方法的实现都不负责,有兴趣可以自己挑来看看

这里可以看到,很多方法里面,关于数据的移动,都是通过 System.arraycopy 实现

4.3 查找

public E get(int index) {
        // 检查数组越界
        rangeCheck(index);

        return elementData(index);
    }
复制代码

方法很简单,自己look look

5. 内部类

SubList

ArrayList有个 subList 的方法,这个方法返回的是ArrayList的一个视图

public List<E> subList(int fromIndex, int toIndex) {
        subListRangeCheck(fromIndex, toIndex, size);
        return new SubList(this, 0, fromIndex, toIndex);
    }
复制代码

方法返回的是SubList类的对象

ArrayList源码解析

可以看到这个类把ArrayList的增删改查方法基本都自己实现了一遍

先来看看构造方法

SubList(AbstractList<E> parent,
                int offset, int fromIndex, int toIndex) {
            this.parent = parent;
            this.parentOffset = fromIndex;
            this.offset = offset + fromIndex;
            this.size = toIndex - fromIndex;
            // [1]
            this.modCount = ArrayList.this.modCount;
        }
复制代码

可以看到[1]处,在创建SubList对象的时候,会把当时ArrayList.modCount的值赋值给SubList.modCount,Sublist的modCount的用处体现在 checkForComodification 方法中(下文会提及)

再来看看增删改查的流程

ArrayList源码解析

可以看到增删改查的方法都会先调用检查边界的方法 rangeCheckrangeCheckForAdd ,然后调用 checkForComodification

checkForComodification 方法的作用是检查SubList对象的modCount跟当前ArrayList的modCount是否相等

private void rangeCheck(int index) {
            if (index < 0 || index >= this.size)
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }

        private void rangeCheckForAdd(int index) {
            if (index < 0 || index > this.size)
                throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
        }
        
        private void checkForComodification() {
        // [1]
            if (ArrayList.this.modCount != this.modCount)
                throw new ConcurrentModificationException();
        }
复制代码

可以看到[1]处,当检查modCount不相等的时候,表示这时还有其他对象在修改ArrayList,就会抛出 ConcurrentModificationException

modCountItr 内部类中也起着相同的作用

现在来看看SubList增删改查的具体是现实

public void add(int index, E e) {
            rangeCheckForAdd(index);
            checkForComodification();
            // 实际调用的是ArrayList的add方法
            parent.add(parentOffset + index, e);
            // 同步一下modCount的信息
            this.modCount = parent.modCount;
            this.size++;
        }
        
        public E remove(int index) {
            rangeCheck(index);
            checkForComodification();
            // 实际调用的是ArrayList的remove方法
            E result = parent.remove(parentOffset + index);
            // 同步一下modCount
            this.modCount = parent.modCount;
            this.size--;
            return result;
        }
        
        public E set(int index, E e) {
            rangeCheck(index);
            checkForComodification();
            // 调用ArrayList的elementData方法
            E oldValue = ArrayList.this.elementData(offset + index);
            ArrayList.this.elementData[offset + index] = e;
            return oldValue;
        }
        
        public E get(int index) {
            rangeCheck(index);
            checkForComodification();
            // 调用ArrayList的elementData方法
            return ArrayList.this.elementData(offset + index);
        }
复制代码

正如上面所提及的,SubList对增删改查的实现就是 检查边界 + 比较modCount + 调用ArrayList本身对应的方法

Itr

在ArrayList中会有 iterator 方法,方法具体实现如下

public Iterator<E> iterator() {
        return new Itr();
    }
复制代码

可以看到方法是直接返回一个新建的Iter类对象

ArrayList源码解析

Itr内部类实现了Iterator接口,来看看它的成员变量

int cursor;       // 下一个元素的下标
        int lastRet = -1; // 最后一次返回的元素的下标; -1 if no such
        int expectedModCount = modCount; // [1]期望的修改次数
复制代码

可以从[1]处看到,Itr对象也会使用modCount,实际作用也是检查当前有没有别的对象在修改ArrayList,如果有就抛 ConcurrentModificationException 异常

接下来看看常用方法的实现

public boolean hasNext() {
            return cursor != size;
        }
        
        public E next() {
            // 检查modCount
            checkForComodification();
            int i = cursor;
            // 检查有没有超出size
            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];
        }

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

            try {
                ArrayList.this.remove(lastRet);
                cursor = lastRet;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }
        
        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
复制代码

方法还是比较容易读懂的,可以自己看看

原文 

https://juejin.im/post/5dc7a3a6e51d452c20567f64

本站部分文章源于互联网,本着传播知识、有益学习和研究的目的进行的转载,为网友免费提供。如有著作权人或出版方提出异议,本站将立即删除。如果您对文章转载有任何疑问请告之我们,以便我们及时纠正。

PS:推荐一个微信公众号: askHarries 或者qq群:474807195,里面会分享一些资深架构师录制的视频录像:有Spring,MyBatis,Netty源码分析,高并发、高性能、分布式、微服务架构的原理,JVM性能优化这些成为架构师必备的知识体系。还能领取免费的学习资源,目前受益良多

转载请注明原文出处:Harries Blog™ » ArrayList源码解析

赞 (0)
分享到:更多 ()

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址