JDK 1.8 ArrayList源码解读

简介: JDK 1.8 ArrayList源码解读

前言 System.arraycopy的使用

/**
* src被拷贝数组
* srcPos开始下标
* dest  被插入目标数组
* destPos被插入目标数组下标
* length 拷贝和复制的长度
*/     
public static void arraycopy(Object src,
                             int srcPos,
                             Object dest,
                             int destPos,
                             int length);
                             

/*
//eg:elementData[a,b] 
     a[0,1,2] 
     System.arraycopy(elementData, 0, a, 0, 2);
     返回[a,b,2]

*/                             
                             
                             

全局变量

/**
   * Shared empty array instance used for empty instances.
   默认的空数组,用于构造函数或者重置ArrayList
   */
  private static final Object[] EMPTY_ELEMENTDATA = {};


/**
   * Shared empty array instance used for default sized empty instances. We
   * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
   * first element is added.
   无参构造函数,带默认容量10,时使用DEFAULTCAPACITY_EMPTY_ELEMENTDATA
   */
  private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
  
  
   /**
   * The array buffer into which the elements of the ArrayList are stored.
   * The capacity of the ArrayList is the length of this array buffer. Any
   * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
   * will be expanded to DEFAULT_CAPACITY when the first element is added.
   实际保存ArrrayList中元素的数组
   ArrrayList当前容量(capacity)即此数组的长度
   所有空的ArrayList都符合elementData ==DEFAULTCAPACITY_EMPTY_ELEMENTDATA
   但当有元素插入,ArrayList将被扩充至DEFAULT_CAPACITY,即10
   
   */
  transient Object[] elementData; // non-private to simplify nested class access

/**
   * The size of the ArrayList (the number of elements it contains).
   *当前ArrayList元素总数
   * @serial
   */
  private int size;
  
   /**
   * The maximum size of array to allocate.
   * Some VMs reserve some header words in an array.
   * Attempts to allocate larger arrays may result in
   * OutOfMemoryError: Requested array size exceeds VM limit
   */
  private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

构造函数

 * Constructs an empty list with the specified initial capacity.
     *
     * @param  initialCapacity  the initial capacity of the list
     * @throws IllegalArgumentException if the specified initial capacity
     *         is negative
     */
    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {//明确默认长度的ArayList
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {//否则用EMPTY_ELEMENTDATAz作为存放元素的数组elementData
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }
    
    /**
     * Constructs an empty list with an initial capacity of ten.
     无参构造函数,带默认容量10,时使用DEFAULTCAPACITY_EMPTY_ELEMENTDATA
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    
    
    /**
     * Constructs a list containing the elements of the specified
     * collection, in the order they are returned by the collection's
     * iterator.
     *
     * @param c the collection whose elements are to be placed into this list
     * @throws NullPointerException if the specified collection is null
     Collection容器对象作参的构造函数
     */
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // c.toArray might (incorrectly) not return Object[](see 6260652)
            //非Object[]数组即可进行数组复制(Object[]在数组复制时可能错误地不返回Object[] )
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }
    

trimToSize瘦身

/*
ArrayList扩容是1.5+1的,此方法用于瘦身ArrayList,使用elementData的长度等于size
*/
 public void trimToSize() {
        modCount++;
        if (size < elementData.length) {
            elementData = (size == 0)
              ? EMPTY_ELEMENTDATA
              : Arrays.copyOf(elementData, size);
        }
    }

ensureCapacity判断(确保)ArrayLit容量大于minCapacity,否则扩容

 public void ensureCapacity(int minCapacity) {
 
        //DEFAULTCAPACITY_EMPTY_ELEMENTDATA表示ArrayList为默认容量10
        int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            // any size if not default element table
            ? 0
            // larger than default for default empty table. It's already
            // supposed to be at default size.
            : DEFAULT_CAPACITY;
        //minExpand
        if (minCapacity > minExpand) {//明确进行扩容
            ensureExplicitCapacity(minCapacity);
        }
    }

minCapacity如果超过DEFAULT_CAPACITY(10)即进行扩容

 private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }

ensureExplicitCapacity明确扩容

 private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        // overflow-conscious code
        //大于当前数组容量即扩容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

扩容实现grow

/**
     * Increases the capacity to ensure that it can hold at least the
     * number of elements specified by the minimum capacity argument.
     *
     * @param minCapacity the desired minimum capacity
     */
    private void grow(int minCapacity) {
        // overflow-conscious code
        //oldCapacit原容量
        int oldCapacity = elementData.length;
        //扩容个1.5倍(其实不是1.5,只是二进制右移1位 oldCapacity >> 1)
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //如果小于minCapacity(最小容量)则已minCapacity为准
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        //newCapacity比最大长度还大,则以Integer.MAX_VALUE作为容量
        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);
    }

hugeCapacity判断最小容量

private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

contains ArrayList是否包含此元素

 public boolean contains(Object o) {
        //该元素下标大于等于0即包含
        return indexOf(o) >= 0;
    }

迭代elementData判断是否有此元素,有则直接返回下标

 public int indexOf(Object o) {
        if (o == null) {
            for (int i = 0; i < size; i++)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

反向迭代elementData判断是否有此元素,有则直接返回下标

 public int lastIndexOf(Object o) {
        if (o == null) {
            for (int i = size-1; i >= 0; i--)
                if (elementData[i]==null)
                    return i;
        } else {
            for (int i = size-1; i >= 0; i--)
                if (o.equals(elementData[i]))
                    return i;
        }
        return -1;
    }

重写父类clone(),实现深度克隆

public Object clone() {
        try {
            ArrayList<?> v = (ArrayList<?>) super.clone();
            v.elementData = Arrays.copyOf(elementData, size);
            v.modCount = 0;
            return v;
        } catch (CloneNotSupportedException e) {
            // this shouldn't happen, since we are Cloneable
            throw new InternalError(e);
        }
    }

arrayList转成数组

//其实就是把elementData拷贝出来而已
public Object[] toArray() {
        return Arrays.copyOf(elementData, size);
    }
//将ArrayList元素以T类型数组返回
 public <T> T[] toArray(T[] a) {
        //目标数组长度小于当前ArrayList size则直接拷贝elementData返回
        if (a.length < size)
            // Make a new array of a's runtime type, but my contents:
            return (T[]) Arrays.copyOf(elementData, size, a.getClass());
        //否则使用System.arraycopy返回
        //eg:elementData[a,b] a[0,1,2] 返回[a,b,2]
        System.arraycopy(elementData, 0, a, 0, size);
        if (a.length > size)
            a[size] = null;
        return a;
    }

elementData[i]下标所在元素,没做,判断容易下标越界

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

返回下标元素

public E get(int index) {
        rangeCheck(index);//检查是否超出size

        return elementData(index);
    }

设置下标元素,并返回原值

 public E set(int index, E element) {
        rangeCheck(index); //检查是否超出size
        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }

添加元素,先判断是否需要扩容再添加

public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

指定下标插入元素

public void add(int index, E element) {
        rangeCheckForAdd(index);//检查是否超出size

        ensureCapacityInternal(size + 1);  // Increments modCount!!扩容
        //拷贝数组,elementDatazai在index处向前进一位
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        //插入元素                 
        elementData[index] = element;
        size++;
    }

删除指定下标数据

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);
        //仅方便gc回收                     
        elementData[--size] = null; // clear to let GC do its work

        return oldValue;
    }

移除指定元素

 public boolean remove(Object o) {
        //找出第一个空元素,执行删除
        if (o == null) {
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true;
                }
        } else {
        //找出第一个obj,执行删除
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }

fastRemove 根据下标快速移除元素

 private void fastRemove(int index) {
        modCount++;
        int numMoved = size - index - 1;
        //判断目标下标是否在数组中间,是则执行拷贝
        if (numMoved > 0)
            System.arraycopy(elementData, index+1, elementData, index,numMoved);
        //yuan原数组尾元素置空    
        elementData[--size] = null; // clear to let GC do its work
    }

### clear数组置空

public void clear() {
       modCount++;

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

       size = 0;
   }

### 添加另一个Collection对象所有元素进ArrayList

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;
   } 

指定下标添加Collection对象所有元素

public boolean addAll(int index, Collection<? extends E> c) {
        rangeCheckForAdd(index);

        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityInternal(size + numNew);  // Increments modCount

        int numMoved = size - index;
        if (numMoved > 0)
            System.arraycopy(elementData, index, elementData, index + numNew,
                             numMoved);

        System.arraycopy(a, 0, elementData, index, numNew);
        size += numNew;
        return numNew != 0;
    }

从指定区间元素开始删除(不包含toIndex所在元素)

 protected void removeRange(int fromIndex, int toIndex) {
        modCount++;
        int numMoved = size - toIndex;
        System.arraycopy(elementData, toIndex, elementData, fromIndex,
                         numMoved);

        // clear to let GC do its work
        int newSize = size - (toIndex-fromIndex);
        for (int i = newSize; i < size; i++) {
            elementData[i] = null;
        }
        size = newSize;
    }

移除包含在Collection中所有元素

public boolean removeAll(Collection<?> c) {
        Objects.requireNonNull(c);
        return batchRemove(c, false);
    }

批量删除 complement true:删除包含的,false:删除不包含的

private boolean batchRemove(Collection<?> c, boolean complement) {
        final Object[] elementData = this.elementData;
        int r = 0, w = 0;
        boolean modified = false;
        try {
            //迭代查找出符合complement的元素并依次保存elementData
            for (; r < size; r++)
                if (c.contains(elementData[r]) == complement)
                    elementData[w++] = elementData[r];
        } finally {
            // Preserve behavioral compatibility with AbstractCollection,
            // even if c.contains() throws.
            //抽象地保存行为兼容性,即使c.contains()包含异常
            //不等于意味迭代中间有异常
            if (r != size) {
                //将没有判断的元素拷贝至已经并且符合complement的元素前
                System.arraycopy(elementData, r,
                                 elementData, w,
                                 size - r);
                w += size - r;
            }
            //如果w == size,即全部符合complement无需移除
            if (w != size) {
                // clear to let GC do its work
                //否则执行删除下标W以后的元素
                for (int i = w; i < size; i++)
                    elementData[i] = null;
                modCount += size - w;
                size = w;
                modified = true;
            }
        }
        return modified;
    }

### writeObject输出元素

private void writeObject(java.io.ObjectOutputStream s)
       throws java.io.IOException{
       // Write out element count, and any hidden stuff
       int expectedModCount = modCount;
       s.defaultWriteObject();

       // Write out size as capacity for behavioural compatibility with clone()
       s.writeInt(size);

       // Write out all elements in the proper order.
       for (int i=0; i<size; i++) {
           s.writeObject(elementData[i]);
       }

       if (modCount != expectedModCount) {
           throw new ConcurrentModificationException();
       }
   } 

readObject读取元素

private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {
        elementData = EMPTY_ELEMENTDATA;

        // Read in size, and any hidden stuff
        s.defaultReadObject();

        // Read in capacity
        s.readInt(); // ignored

        if (size > 0) {
            // be like clone(), allocate array based upon size not capacity
            ensureCapacityInternal(size);

            Object[] a = elementData;
            // Read in all elements in the proper order.
            for (int i=0; i<size; i++) {
                a[i] = s.readObject();
            }
        }
    }

jdk7相关网页

http://www.cnblogs.com/chenssy/p/3498468.html

目录
相关文章
|
1月前
|
安全 前端开发 Java
JDK源码级别彻底剖析JVM类加载机制
JDK源码级别彻底剖析JVM类加载机制
|
1月前
|
缓存 Dubbo Java
趁同事上厕所的时间,看完了 Dubbo SPI 的源码,瞬间觉得 JDK SPI 不香了
趁同事上厕所的时间,看完了 Dubbo SPI 的源码,瞬间觉得 JDK SPI 不香了
|
9月前
|
Java 容器
阿里内部流传的JDK源码剖析手册!GitHub已获上千万的访问量
相信现在已经有很多小伙伴知道了“微软”要对JDK下手了! JDK是什么? jdk是Java语言的软件开发工具包,主要用于移动设备、嵌入式设备上的java应用程序。jdk是整个java开发的核心,它包含了JAVA的运行环境和JAVA工具。相对而言,没有jdk的话,无法编译Java程序(指java源码.java文件),如果想只运行Java程序(指class或jar或其它归档文件),要确保已安装相应的JRE。
215 0
|
1月前
|
缓存 Java Spring
Spring 源码阅读 66:基于 JDK 的 AOP 代理如何获取拦截器链(4)- 将 Advice 封装为拦截器
【1月更文挑战第1天】本文分析了 Advice 被封装成 MethodInterceptor 的过程,Spring AOP 用到的五种 Advice 中,有些本身就是 MethodInterceptor 的实现类,而有些需要通过适配器的封装。
49 0
|
9月前
|
设计模式 Java 程序员
太爆了!阿里最新出品2023版JDK源码学习指南,Github三天已万赞
最近后台收到很多粉丝私信,说的是程序员究竟要不要去读源码?当下行情,面试什么样的薪资/岗位才会被问到源码? 对此,我的回答是:一定要去读,并且要提到日程上来! 据不完全统计,现在市面上不管是初级,中级,还是高级岗,面试的时候都有可能会问到源码中的问题,它已经成为程序员常规必备的一个技术点。如果你当下想通过一个面试,或者想把中级薪资要到相对于比较高的话,源码这块就必须要会。
110 0
|
1月前
|
算法 Java 索引
【数据结构与算法】4、双向链表(学习 jdk 的 LinkedList 部分源码)
【数据结构与算法】4、双向链表(学习 jdk 的 LinkedList 部分源码)
39 0
|
1月前
|
设计模式 Java
根据JDK源码Calendar来看工厂模式和建造者模式
根据JDK源码Calendar来看工厂模式和建造者模式
|
1月前
|
Java Linux iOS开发
Spring5源码(27)-静态代理模式和JDK、CGLIB动态代理
Spring5源码(27)-静态代理模式和JDK、CGLIB动态代理
26 0
|
1月前
|
XML Java 数据格式
Spring 源码阅读 70:基于 JDK 的 AOP 代理拦截器链执行(4)- 容易被忽略的 ExposeInvocationInterceptor
【1月更文挑战第5天】本文分析了 Spring AOP 拦截器链中的一个特殊拦截器 ExposeInvocationInterceptor 的注册的时机以及它的作用。至此,基于 JDK 的 AOP 代理拦截器链执行的逻辑就分析完了。
487 0
|
1月前
|
Java 索引 Spring
Spring 源码阅读 69:基于 JDK 的 AOP 代理拦截器链执行(3)- MethodInterceptor 分析
【1月更文挑战第4天】本文详细分析了 Spring AOP 中五种增强类型对应的拦截器中增强方法的执行逻辑,结合上一篇中分析的 ReflectiveMethodInvocation 中proceed方法的执行逻辑,就组成了完整的拦截器链递归调用的逻辑。
40 0