Java源码分析-ArrayList

作者: gatsby_dhn | 来源:发表于2016-10-05 16:31 被阅读86次

    ArrayList是我们最常用的集合类,我们看下它的实现(基于JDK1.8)。

    支持原创,转载请注明出处。

    继承关系

    public class ArrayList<E> extends AbstractList<E>
            implements List<E>, RandomAccess, Cloneable, java.io.Serializable
    
    public interface List<E> extends Collection<E>
    

    ArrayList实现了List接口,List又实现了Collection接口。

    核心成员变量

        private static final int DEFAULT_CAPACITY = 10 ;   //默认容量
        transient Object [] elementData;                   //保存元素
        private int size ;                                 //当前元素个数
        private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; //空数组
    

    我们注意,数组默认的大小为10。

    构造函数

        public ArrayList (int initialCapacity) {
            if ( initialCapacity > 0) {
                this. elementData = new Object [initialCapacity ] ;     //初始化指定大小的数组
            } else if ( initialCapacity == 0 ) {
                this. elementData = EMPTY_ELEMENTDATA;
            } else {
                throw new IllegalArgumentException( "Illegal Capacity: "+
                                                   initialCapacity );
            }
        }
    
        public ArrayList() {
            this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
        }  //初始化一个空数组
    

    添加元素

        public boolean add(E e) {      //在最后添加元素
            ensureCapacityInternal(size + 1);  //确保不会越界
            elementData[size++] = e;          //加入数组
            return true;
        }
    
       private void ensureCapacityInternal(int minCapacity) {
            if (elementData == DEFAULTCAPACITY_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 void grow(int minCapacity) {
            // overflow-conscious code
            int oldCapacity = elementData.length;
            int newCapacity = oldCapacity + (oldCapacity >> 1);    //扩容机制
            if (newCapacity - minCapacity < 0)
                newCapacity = minCapacity;
            if (newCapacity - MAX_ARRAY_SIZE > 0)
                newCapacity = hugeCapacity(minCapacity);
            //拷贝原始数组到一个新的数组,新的数组大小为newCapacity,可能截断,或在尾部添加null
            elementData = Arrays.copyOf(elementData, newCapacity);
        }
    
    

    加入元素e后,首先确保添加该元素后不会溢出,必要时会进行扩容,扩容机制为int newCapacity = oldCapacity + (oldCapacity >> 1)大约为原大小的1.5倍,然后将原数组复制到新的长度为newCapacity的数组中。最后将该元素e加入到数组末尾。这里我们看到根据需要指定ArrayList的大小可以防止扩容,提高效率。

    查找元素

       public E get(int index) {
            rangeCheck(index);    //检查是否越界
    
            return elementData(
        }
    
        E elementData(int index) {
            return (E) elementData[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;   //返回被删除元素
        }
    

    在数组中间删除元素同样会进行拷贝,如果是常用操作可以使用LinkedList代替。

    支持原创,转载请注明出处。
    github:https://github.com/gatsbydhn

    相关文章

      网友评论

        本文标题:Java源码分析-ArrayList

        本文链接:https://www.haomeiwen.com/subject/fqnsyttx.html