欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

ArrayList源码详解

程序员文章站 2022-04-18 19:07:27
ArrayList是一个容量能够动态增涨的数组,它是java集合框架中一个重要的类,继承抽象类AbstractList,实现了List接口。 实现了RandomAccess接口,该接口为标记接口,即提供了随机访问功能。 实现了Cloneable接口,可以调用Object的clone方法,返回对象的浅 ......
    public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

ArrayList是一个容量能够动态增涨的数组,它是java集合框架中一个重要的类,继承抽象类AbstractList,实现了List接口。
实现了RandomAccess接口,该接口为标记接口,即提供了随机访问功能。
实现了Cloneable接口,可以调用Object的clone方法,返回对象的浅拷贝。
实现了java.io.Serializable接口,可以进行序列化功能。

  • ArrayList的属性

    private static final int DEFAULT_CAPACITY = 10;         //默认大小
    private static final Object[] EMPTY_ELEMENTDATA = {};      //空的数组
    private transient Object[] elementData; //存放ArrayList内元素的数组,定义了transient在实现Serializable序列化时,不会被串行化
    private int size;  //ArrayList的大小,成员变量,系统默认初始化0, 存在堆内存中,实际为ArrayList存放元素的个数                   
  • ArrayList的构造方法

    public ArrayList(int initialCapacity) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        this.elementData = new Object[initialCapacity];        //初始化一个initialCapacity大小的数组
     }
     public ArrayList() {
        super();                                                                     //ArrayList(10) jdk1.6该构造方法的实现,默认就创建10个大小的数组
        this.elementData = EMPTY_ELEMENTDATA;         //将elementData的引用指向定义的空数组(本文基于jdk1.7)
     }
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        size = elementData.length;
        if (elementData.getClass() != Object[].class)       //返回若不是Object[]将调用Arrays.copyOf方法将其转为Object[]
            elementData = Arrays.copyOf(elementData, size, Object[].class);  
    }
  • ArrayList的方法

add方法

    //直接添加元素,添加至数组末尾
   public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;        //把元素追加到数组最后一个,size+1
        return true;
    }

    //通过下标添加元素,假如当前数组大小为10,数组里有5个元素,下标传参只能<=5,
    //index=5 则元素直接添加至末尾
    //index<5 index原位置元素及后续所有元素都往后移一个单位,新元素插入原index元素位置
    //eg: 此时有arraylist有[1,2,3,4,5,6,7,8]size:8,我想在索引为5的时候插入1个数字1
    //add(5,1) ,arrayList最后是[1,2,3,4,5,1,6,7,8]
    public void add(int index, E element) {
        rangeCheckForAdd(index);            //检查数组下标越界

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }

    private void ensureCapacityInternal(int minCapacity) {
        if (elementData == EMPTY_ELEMENTDATA) {                 //假如elementDate是个空的数组,即没有容量大小
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);  //比较大小,返回大的那个数值,作为初始化数组的大小 
        }

        ensureExplicitCapacity(minCapacity);                //检查容量是否够,不够就扩容
    }

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;                             ////AbstractList里所定义,假如使用迭代器将会用到 
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;                   //假设当前的ArrayList大小为12,即oldCapacity大小为12
        //12二进制为1100,右移一个单位,即0110,十进制就是6,newCapacity即为18
        int newCapacity = oldCapacity + (oldCapacity >> 1);     
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
            //MAX_ARRAY_SIZE=Integer.MAX_VALUE-8 Integer.MAX_VALUE = 2147483647
        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);      //创建一个原来大小1.5倍的数组,将原数组数据复制过去
    }

    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();                           //小于0则报内存溢出 
            //当天arrayList大小假如大于定义的MAX_ARRAY_SIZE大小,则返回Integer的最大值
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :                             
            MAX_ARRAY_SIZE;
    }

     private void rangeCheckForAdd(int index) {                     //检查数组下标是否越界
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

关于方法:扩容方法grow()里Arrays.copyOf(elementData, newCapacity),就是根据class的类型来决定是new 还是反射去构造一个泛型数组,同时利用System.arraycopy函数,批量赋值元素至新数组中。

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
        T[] copy = ((Object)newType == (Object)Object[].class)
            ? (T[]) new Object[newLength]
            : (T[]) Array.newInstance(newType.getComponentType(), newLength);
        System.arraycopy(original, 0, copy, 0,
                         Math.min(original.length, newLength));
        return copy;
    }

remove方法

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

        modCount++;        
        E oldValue = elementData(index);        //读出要删除的值
        //eg:假设当前数组值为{1,2,3,4,5,6,7,8},size为8,要删除index为5的值,在数组里是6
        int numMoved = size - index - 1;        //numMoved = 8 - 5 -1 = 2
        if (numMoved > 0)
        //eg:System.arraycopy(elementData,5+1,elementData,5,2)
        //eg:从数组elementData中的第6个位置开始复制2个数,复制到elementData中,从elementData中的5位置开始存放
        //eg:{1,2,3,4,5,7,8}
            System.arraycopy(elementData, index+1, elementData, index,
                             numMoved);
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
}
    //删除该元素在数组中第一次出现的位置上的数据。 如果有该元素返回true,如果false。
    public boolean remove(Object o) {
        if (o == null) {
            for (int index = 0; index < size; index++)
                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
    }
    //for循环使数组里每一个元素为null
    public void clear() {
        modCount++;

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

        size = 0;
    }
    //从2个集合中删除重叠的数据
    public boolean removeAll(Collection<?> c) {
        return batchRemove(c, false);
    }
    //从2个集合中获取重叠的数据
    public boolean retainAll(Collection<?> c) {
        return batchRemove(c, true);
    }
    //
    private boolean batchRemove(Collection<?> c, boolean complement) {
        final Object[] elementData = this.elementData;  //获得当前对象的所有元素
        int r = 0, w = 0;           //w:标记两个集合公共元素的个数
        boolean modified = false;
        try {
            for (; r < size; r++)           ////遍历集合A
                if (c.contains(elementData[r]) == complement)  //判断集合B中是否包含集合A中的当前元素
                    elementData[w++] = elementData[r];          //如果包含则直接保存。
        } finally {
            // Preserve behavioral compatibility with AbstractCollection,
            // even if c.contains() throws.
            if (r != size) {   //出现异常会导致 r !=size , 则将出现异常处后面的数据全部复制覆盖到数组里。
                System.arraycopy(elementData, r,
                                 elementData, w,
                                 size - r);
                w += size - r;
            }
            if (w != size) {                            //置空数组后面的元素
                // clear to let GC do its work
                for (int i = w; i < size; i++)
                    elementData[i] = null;
                modCount += size - w;                   //记录集合中元素的改变(add/remove)
                size = w;
                modified = true;
            }
        }
        return modified;
    }

set方法

    public E set(int index, E element) {
        rangeCheck(index);                      //检查数组下标越界

        E oldValue = elementData(index);            //取出原来的元素
        elementData[index] = element;               //替换元素
        return oldValue;                            //返回原来的元素
    }

    @SuppressWarnings("unchecked")
    E elementData(int index) {
        return (E) elementData[index];
    }

get方法

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

        return elementData(index);
    }

iterator

    public Iterator<E> iterator() {
        return new Itr();
    }
    private class Itr implements Iterator<E> {
        int cursor;                                 //默认0
        int lastRet = -1;                           //上次返回的元素
        int expectedModCount = modCount;            //用于判断集合是否修改过结构的标识

        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;                     //游标+1
            return (E) elementData[lastRet = i];//返回元素,并将记录上次返回元素的下标
        }

        public void remove() {              //remove掉上次next的元素
            if (lastRet < 0)                 //判断有没有执行过next方法
                throw new IllegalStateException();
            checkForComodification();          //

            try {
                ArrayList.this.remove(lastRet);     //删除上次next的元素,会修改modCount
                cursor = lastRet;                   //被删除位置赋值给游标
                lastRet = -1;                       //不能连续删除
                expectedModCount = modCount;        //更新expectedModCount
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

        final void checkForComodification() {           //Fail-Fast 机制 
            if (modCount != expectedModCount)           //因此如果在使用迭代器的过程中有其他线程修改了modCount,就会抛ConcurrentModificationException()
                throw new ConcurrentModificationException();
        }

总结

ArrayList基于数组方式实现,容量限制不大于Integer.MAX_VALUE的小大,每次扩容1.5倍。有序,可以为null,允许重复,非线程安全。

elementData属性采用了transient来修饰,不使用Java默认的序列化机制来实例化,自己实现了序列化writeObject()和反序列化readObject()的方法。

增加和删除会修改modCount,在迭代的时候需要保持单线程的唯一操作,如果期间进行了插入或者删除操作,就会被迭代器检查获知,从而出现运行时异常。