ArrayList源码详解

ArrayList UML类图

ArrayList 概述

ArrayList 是实现 List 接口的动态数组,所谓动态就是它的大小是可变的。实现了所有可选列表操作,并允许包括 null 在内的所有元素。

除了实现 List 接口外,此类还提供一些方法来操作内部用来存储列表的数组的大小。

每个 ArrayList 实例都有一个容量,该容量是指用来存储列表元素的数组的大小。默认初始容量为 10。随着 ArrayList 中元素的增加,它的容量也会不断的自动增长。在每次添加新的元素时,ArrayList 都会检查是否需要进行扩容操作,扩容操作带来数据向新数组的重新拷贝,所以如果我们知道具体业务数据量,在构造 ArrayList 时可以给 ArrayList 指定一个初始容量,这样就会减少扩容时数据的拷贝问题。当然在添加大量元素前,应用程序也可以使用 ensureCapacity 操作来增加 ArrayList 实例的容量,这可以减少递增式再分配的数量。

请注意,此实现不同步。如果多个线程同时访问一个 ArrayList 实例,而其中至少一个线程从结构上修改了列表,那么它必须保持外部同步。所以为了保证同步,最好的办法是在创建时完成,以防止意外对列表进行不同步的访问: List list = Collections.synchronizedList(new ArrayList(…));

ArrayList 源码分析

几个比较重要的字段

//默认初始容量
private static final int DEFAULT_CAPACITY = 10;
//共享的空数组实例。
private static final Object[] EMPTY_ELEMENTDATA = {};
//存放元素的数组
private transient Object[] elementData;

transient是个关键字,这个关键字的意思是:transient修饰的变量将不进行序列化 详解:http://blog.csdn.net/u013207877/article/details/52572975 EMPTY_ELEMENTDATA 和elementData字段的作用将在构造方法里体现

构造方法
    //初始化一个默认为10的容量
    public ArrayList() {
        super();
        this.elementData = EMPTY_ELEMENTDATA;
    }
    //可以指定初始化容量,指定初始容量为负时,则抛出异常
    public ArrayList(int initialCapacity) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        this.elementData = new Object[initialCapacity];
    }
    //使用集合类对象初始化ArrayList,底层使用数组copy方式。
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        size = elementData.length;
        //jdk源码注释: c.toArray might (incorrectly) not return Object[] (see 6260652)
        //意思是:c.toArray可能(错误)不返回Object[]  see 6260652 这个编号代表JDK bug库中的编号
        //原因:https://www.cnblogs.com/cmdra/p/5901793.html
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    }

add方法

boolean add(E e)
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // jdk源码注释:Increments modCount!!。 自增修改次数!!
        elementData[size++] = e;
        return true;
    }

    //这个方法是 确保内部的容量大小可以存储元素
    private void ensureCapacityInternal(int minCapacity) {
        //if语句判断的是,当前是否第一次添加元素,如果是的话,则把最小容量(minCapacity)赋值为10
        if (elementData == EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);//DEFAULT_CAPACITY的值一定是10,final修饰了
        }
        ensureExplicitCapacity(minCapacity);
    }
    //这个方法是 确保明确增加多少容量
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;//防止迭代的时候有其他线程进行结构的改变。

        //如果最小的列表容量跟当前数组的长度相减大于0的话,那么需要进行扩容;
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    //这个方式是进行容量扩容
    private void grow(int minCapacity) {
        //oldCapacity 旧的容量
        int oldCapacity = elementData.length;
        //newCapacity 新的容量   (oldCapacity >> 1)这个表达式的意思是oldCapacity*1.5
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        //如果if语句成立,当minCapacity小于0则会抛出内存溢出异常,当minCapacity大于0,则newCapacity=Integer.MAX_VALUE;            
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        //当前元素添加到新的数组,并进行数组扩容。
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
    //数组扩容并把元素添加到新的数组里面
    public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
        //判断类型是否一致,如果不一致,则重新实例化(Array.newInstance())数组
        T[] copy = ((Object)newType == (Object)Object[].class)
            ? (T[]) new Object[newLength]
            : (T[]) Array.newInstance(newType.getComponentType(), newLength);
                //复制数组,将原数组从0索引开始复制,复制到新的数组,从0索引位置开始复制,复制Math.min(original.length, newLength)个
        System.arraycopy(original, 0, copy, 0,
                         Math.min(original.length, newLength));
        return copy;
    }
void add( int index, E element)方法
    //指定的位置插入指定的元素,指定的位置必须小于等于size
    public void add(int index, E element) {
        //范围检查,指定的索引不能超过当前的容量值,也不能小于0
        rangeCheckForAdd(index);
        //确保容量内部有位置存储
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //将当前数组从指定的索引开始复制,复制到指定索引后面的一个位置
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }
    //检查传入的index值是否越界。
    private void rangeCheckForAdd(int index) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

Remove

    public E remove(int index) {
        //检查索引
        rangeCheck(index);

        modCount++;
        //获取删除的值
        E oldValue = elementData(index);
        //需要移动多少个值
        int numMoved = size - index - 1;
        //如果删除的元素不是最后一个,则需要进行数组复制
        if (numMoved > 0)
            //从指定索引后面那个位置开始复制元素,复制到指定索引的位置,也就是将指定索引的那个位置给覆盖掉
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        //将最后一个位置置空
        elementData[--size] = null; // JVM会清除
        //返回移除的元素
        return oldValue;
    }

get(int index)

    public E get(int index) {
        rangeCheck(index);
        return elementData(index);
    }

trimToSize

底层数组的容量调整为当前列表保存的实际元素的大小的功能

    public void trimToSize() {
        modCount++;
        //如果时间大小小于缓冲区容量的长度,则进行数组复制。
        if (size < elementData.length) {
            elementData = Arrays.copyOf(elementData, size);
        }
    }
Iterator迭代器
    private class Itr implements Iterator<E> {
        int cursor;        // 返回下一个元素的索引
        int lastRet = -1; // 返回的最后一个元素的索引;如果没有,则为1
        int expectedModCount = modCount;

        public boolean hasNext() {
            //第一次调用,因为变量的初始化,那么cursor的值为0,
            return cursor != size;
        }

        @SuppressWarnings("unchecked")
        public E next() {
            //检查是否有被并发修改
            checkForComodification();
            //将光标赋值给i
            int i = cursor;
            //如果光标值大于等于集合个数的话,则抛出异常
            if (i >= size)
                throw new NoSuchElementException();
            //获取集合内的元素
            Object[] elementData = ArrayList.this.elementData;
            //判断是否有其他线程进行修改
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            //光标加1
            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();
        }
    }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏用户画像

6.3.2 B+树基本概念

2)非叶根(不是叶子的根结点)结点至少有两棵子树,其他每个分支结点至少有【m/2】(向下取整)棵子树。(B树是要求至少2棵子树)

932
来自专栏刘君君

JDK8的ArrayList源码学习笔记

2716
来自专栏LanceToBigData

Java集合源码分析(一)ArrayList

前言   在前面的学习集合中只是介绍了集合的相关用法,我们想要更深入的去了解集合那就要通过我们去分析它的源码来了解它。希望对集合有一个更进一步的理解!   既然...

2456
来自专栏算法与数据结构

数据结构 单链表&顺序表

顺序表: 一般使用数组(C语言中的数组采用顺序存储方式。即连续地址存储)来描述。 优点:在于随机访问元素, 缺点:插入和和删除的时候,需要移动大量的元素。 链表...

41910
来自专栏一枝花算不算浪漫

Java中常见数据结构List之ArrayList

37212
来自专栏Bingo的深度学习杂货店

Q108 Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a hei...

3223
来自专栏架构之路

Java 集合系列03之 ArrayList详细介绍(源码解析)和使用示例

概要 上一章,我们学习了Collection的架构。这一章开始,我们对Collection的具体实现类进行讲解;首先,讲解List,而List中ArrayLis...

2854
来自专栏微信公众号:Java团长

Java集合源码剖析——ArrayList源码剖析

ArrayList是基于数组实现的,是一个动态数组,其容量能自动增长,类似于C语言中的动态申请内存,动态增长内存。

1022
来自专栏desperate633

LintCode 数组剔除元素后的乘积题目代码

定义B[i] = A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1], 计算B的时候请不要使用除法。

871
来自专栏我就是马云飞

ArrayList到底是什么?

ArrayList是日常开发中使用最频繁的集合类。首先这边简单介绍一下ArrayList:

1162

扫码关注云+社区