阅读 73

Java集合之ArrayList源码解析

ArrayList是我们在开发中经常使用的一个集合,继续按照以前的风格来解析源码(JDK1.7)。
ArrayList简要概括:
1.ArrayList的底层数据结构是一个数组,确切地说是一个动态数组,每次扩容的时候,都会重新创建一个数组并赋值给成员变量elementData,其容量的扩展方式为:newCapacity = oldCapacity + (oldCapacity >> 1);
2.ArrayList是线程不安全的,只能在单线程环境下安全使用,在多线程的环境下,需要使用Collections.synchronizedList(List l)函数来保证线程安全,或者使用concurrent并发包下的CopyOnWriteArrayList类。

下面我们首先看下ArrayList的构造函数,即应该如何创建一个ArrayList对象,情况代码清单1:
代码清单1:

 private static final int DEFAULT_CAPACITY = 10;//默认容量为10,这里可以复习一下,HashMap默认为16,Hashtable默认为11,ConcurrentHashmap默认为16
    private static final Object[] EMPTY_ELEMENTDATA = {};//当调用无参构造函数时,将该值赋予elementData.
    private transient Object[] elementData;//存储数据的数组,注意这里声明的类型为Object,也就是说可以同时存储字符串、整型、浮点数这些数据

    private int size;//当前的数据长度


    public ArrayList(int initialCapacity) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        this.elementData = new Object[initialCapacity];//创建指定长度数组
    }

    public ArrayList() {
        super();
        this.elementData = EMPTY_ELEMENTDATA;//无参时,将一个空数组赋elementData
    }
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();//注意toArray方法有时返回不了Object[]
        size = elementData.length;
        if (elementData.getClass() != Object[].class)//做检查
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    }复制代码

代码清单1 我们可以了解如何构造一个ArrayList,这里需要说的是当调用无参构造函数时(即ArrayList a=new ArrayList()),如果加入数据时,扩容至默认容量10。那么如何加入数据呢?请看代码清单2:

代码清单2

 public boolean add(E e) {//在末尾追加元素
        ensureCapacityInternal(size + 1);  // 增加修改次数以及扩容处理
        elementData[size++] = e;//数据长度+1
        return true;
    }
    public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1); //先执行扩容操作
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);//扩容之后,可以安全地整体移动数组元素。
        elementData[index] = element;
        size++;
    }
    private void ensureCapacityInternal(int minCapacity) {//这里需记住minCapacity是size+1,并不是数组本身的长度
        if (elementData == EMPTY_ELEMENTDATA) {
            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 static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);//在原有数组长度上扩展至1.5倍,即一次增加原有容量的一半。
        if (newCapacity - minCapacity < 0)//如果扩容后还不满足存储要求,则直接扩容至原数据长度+1
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);//扩容至最大值

        elementData = Arrays.copyOf(elementData, newCapacity);//这里数组的本质其已经更换掉了,看代码清单3就可知,elementData在这里指向新数组。
    }

    private static int hugeCapacity(int minCapacity) {//
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        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));
    }复制代码

看了代码清单2,通过代码注释我们应该已经理解了ArrayList的扩容方式与数据结构了,对于代码清单2中的代码,这里对于Sysytem.arraycopy方法和Arrays.copyOf方法做一下说明:
Arrays.copyOf方法内部调用的还是System.arraycopy方法,如代码清单3
代码清单3

//-------------------------------Arrays---------------------------------------
public static <T> T[] copyOf(T[] original, int newLength) {
        return (T[]) copyOf(original, newLength, original.getClass());
    }
 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;
    }
//--------------------------------------System--------------------------------
    public static native void arraycopy(Object src,  int  srcPos,
                                        Object dest, int destPos,
                                        int length); //native方法复制代码

这里简单说一下区别,arraycopy会抛出IndexOutOfBoundsException异常,而copyOf不会,代码清单3中的Math.min(original.length, newLength)这句代码可以很好的说明这个问题。在ArrayList的代码清单1和2中,arraycopy是用来移动元素,以方便在指定位置新增元素。copyof是用来复制整个数组的元素和扩容时的处理。这个具体的区别,大家可以写个demo很容易理解的。

那么我们怎么访问ArrayList中的元素和清除元素的呢?请看代码清单4:

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

    public E get(int index) {//其实就是根据下标访问数组元素
        rangeCheck(index);

        return elementData(index);
    }

 private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
 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; // clear to let GC do its work

        return oldValue;
    }
    public boolean remove(Object o) {//移除数组中第一个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
    }
    public void clear() {
        modCount++;

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

        size = 0;
    }复制代码

ArrayList相比较于HashMap、Hashtable、ConcurrentHashmap来说比较简单,就分析这么多内容了。其他的集合源码分析可以查看我其他的文章。

要说的内容就这么多,如果文中有不对的地方,麻烦指出,如果喜欢我的文章,可以动动手指关注一下,赞一下,我会有更大的动力写出更多的文章,转载请注明出处:blog.csdn.net/gc_gongchao…

关注下面的标签,发现更多相似文章
评论