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

源码阅读之ArrayList(JDK8)

程序员文章站 2022-04-04 17:52:26
ArrayList概述 ArrayList是一个的可变数组的实现,实现了所有可选列表操作,并允许包括 null 在内的所有元素。每个ArrayList实例都有一个容量,该容量是指用来存储列表元素的数组的大小。它总是至少等于列表的大小。随着向ArrayList中不断添加元素,其容量也自动增长。自动增长 ......

ArrayList概述

ArrayList是一个的可变数组的实现,实现了所有可选列表操作,并允许包括 null 在内的所有元素。每个ArrayList实例都有一个容量,该容量是指用来存储列表元素的数组的大小。它总是至少等于列表的大小。随着向ArrayList中不断添加元素,其容量也自动增长。自动增长会带来数据向新数组的重新拷贝,因此,如果可预知数据量的多少,可在构造ArrayList时指定其容量。在添加大量元素前,应用程序也可以使用ensureCapacity操作来增加ArrayList实例的容量,这可以减少递增式再分配的数量。 
注意,此实现不是同步的。如果多个线程同时访问一个ArrayList实例,而其中至少一个线程从结构上修改了列表,那么它必须保持外部同步。

ArrayList的源码阅读:

  • 底层容器

  ArrayList是一个Object的数组,还有一个size属性来记录当前容器的容量。

transient Object[] elementData; // non-private to simplify nested class access
private int size;
  • 构造函数

ArrayList提供了三种方式的构造器,可以构造一个默认初始容量为0的空列表、构造一个指定初始容量的空列表以及构造一个包含指定collection的元素的列表,这些元素按照该collection的迭代器返回它们的顺序排列的。

    private static final Object[] EMPTY_ELEMENTDATA = {};

    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

   
  // 传入初始容量的构造函数
  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 ArrayList(Collection<? extends E> c) {
     //持有传入集合的内部数组的引用 elementData = c.toArray();
     //更新集合元素个数大小 if ((size = elementData.length) != 0) { // c.toArray might (incorrectly) not return Object[] (see 6260652) if (elementData.getClass() != Object[].class)
          //判断引用的数组类型, 并将引用转换成Object数组引用 elementData = Arrays.copyOf(elementData, size, Object[].class); } else { // replace with empty array. this.elementData = EMPTY_ELEMENTDATA; } }
  •  添加元素

ArrayList有四种添加元素的方法:add(E e),add(int index, E element),addAll(Collection<? extends E> c),addAll(int index, Collection<? extends E> c)

    // 添加一个元素
  public boolean add(E e) {
    //添加前先检查是否需要拓展数组, 此时数组长度最小为size+1 ensureCapacityInternal(size + 1); // Increments modCount!!
    //将元素添加到数组末尾 elementData[size++] = e; return true; }   // 插入一个元素 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;
    //将容器的容量+1 size++; }
  // 添加一个集合数据 public boolean addAll(Collection<? extends E> c) {
    // 把Collection中的数据按照迭代器的排列复制到临时数组a中 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; }   // 插入一个集合数据 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)
       // 在elementData的index位置开始,往后移动numNew个位置 System.arraycopy(elementData, index, elementData, index + numNew, numMoved);     // 将数据插入的index处 System.arraycopy(a, 0, elementData, index, numNew); size += numNew; return numNew != 0; }

细读里面上的代码:

  1. System.arraycopy

  System.arraycopy(elementData, index, elementData, index + numNew,numMoved);

  源码阅读之ArrayList(JDK8)

这时的index=1 numNew=3,numMoved=4,那么执行上面的代码后:

源码阅读之ArrayList(JDK8)

然后执行

System.arraycopy(a, 0, elementData, index, numNew);

 源码阅读之ArrayList(JDK8)

  2. ensureCapacityInternal

  //集合最大容量    
  private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; private void ensureCapacityInternal(int minCapacity) {
    // 如果是空数组(默认初始化时的数组) if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
       // 容量不能小于默认容量10 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;
    // 新数组容量,在原来的基础上增加1.5倍 int newCapacity = oldCapacity + (oldCapacity >> 1);
    //检查新的容量是否小于最小容量 if (newCapacity - minCapacity < 0) newCapacity = minCapacity;
    //检查新的容量是否超过最大数组容量 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); } private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError(); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; }

每次添加元素前会调用ensureCapacityInternal这个方法进行集合容量检查。在这个方法内部会检查当前集合的内部数组是否还是个空数组,如果是就新建默认大小为10的Object数组。如果不是则证明当前集合已经被初始化过,那么就调用ensureExplicitCapacity方法检查当前数组的容量是否满足这个最小所需容量,不满足的话就调用grow方法进行扩容。

在grow方法内部可以看到,每次扩容都是增加原来数组长度的一半,扩容实际上是新建一个容量更大的数组,将原先数组的元素全部复制到新的数组上,然后再抛弃原先的数组转而使用新的数组。

  •  删除元素
   // 删除指定下标的元素
    public E remove(int index) {
    //index不能大于size rangeCheck(index);     //更新容器被修改的次数 modCount++; E oldValue = elementData(index); int numMoved = size - index - 1; if (numMoved > 0)
       //将index后面的值往前移一位 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) { 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 E set(int index, E element) {
        rangeCheck(index);

        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }
  • 查询元素
    public E get(int index) {
        rangeCheck(index);

        return elementData(index);
    }
  •  增删改查总结

增(添加):仅是将这个元素添加到末尾。操作快速。如果有扩容的情况,会涉及数组的复制,操作较慢。

增(插入):由于需要移动插入位置后面的元素,并且涉及数组的复制,所以操作较慢。

删:由于需要将删除位置后面的元素向前挪动,也会设计数组复制,所以操作较慢。

改:直接对指定位置元素进行修改,不涉及元素挪动和数组复制,操作快速。

查:直接返回指定下标的数组元素,操作快速。

  •  Fail-Fast机制

ArrayList也采用了快速失败的机制,通过记录modCount参数来实现。在面对并发的修改时,迭代器很快就会完全失败,而不是冒着在将来某个不确定时间发生任意不确定行为的风险。在看下面iterator()方法的源代码时会发现,再通过迭代器操作ArrayList时都会调用checkForComodification方法,如果modCount被修改了会抛出ConcurrentModificationException.

 public Iterator<E> iterator() {
        return new Itr();
    }

    /**
     * An optimized version of AbstractList.Itr
     */
    private class Itr implements Iterator<E> {
        int cursor;       // index of next element to return
        int lastRet = -1; // index of last element returned; -1 if no such
        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;
            return (E) elementData[lastRet = i];
        }

        public void remove() {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
                ArrayList.this.remove(lastRet);
                cursor = lastRet;
                lastRet = -1;
          // 把modCount重新赋值,所以我们可以使用iterator的remove方法来删除ArrayList里的元素,而不会导致ConcurrentModificationException. expectedModCount = modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } @Override @SuppressWarnings("unchecked") public void forEachRemaining(Consumer<? super E> consumer) { Objects.requireNonNull(consumer); final int size = ArrayList.this.size; int i = cursor; if (i >= size) { return; } final Object[] elementData = ArrayList.this.elementData; if (i >= elementData.length) { throw new ConcurrentModificationException(); } while (i != size && modCount == expectedModCount) { consumer.accept((E) elementData[i++]); } // update once at end of iteration to reduce heap write traffic cursor = i; lastRet = i - 1; checkForComodification(); } final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); } }