彻底搞懂ArrayList

每天学Java

发布于 2020-09-18 11:16:41

4350

发布于 2020-09-18 11:16:41

文章被收录于专栏：每天学Java

对ArrayList字段，内部类，常用方法和问题进行讲解。文章很长，值得收藏

Java版本:1.8

字段

private static final long serialVersionUID = 8683452581122892189L;

序列化的版本号

private static final int DEFAULT_CAPACITY = 10;

ArrayList默认存储空间为10

private static final Object[] EMPTY_ELEMENTDATA = {};

空的对象数组

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

同样是空的数组对象，和EMPTY_ELEMENTDATA区别在于，无参构造函数的空数组会用DEFAULTCAPACITY_EMPTY_ELEMENTDATA赋值，有参构造函数的空数组会用EMPTY_ELEMENTDATA赋值。

transient Object[] elementData;

存储数据的数组，该字段表明ArrayList底层数据结构是数组。transient表明该字段无需序列化

private int size;

ArrayList存储数据的数量，int类型默认为0。

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

最大容量。减去8是因为数组中保留了一些头信息。避免内存溢出

构造器

ArrayList有三个构造函数

无参构造函数

这里用的是elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA

    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

指定容器大小的构造函数

这里如果initialCapacity等于0，则elementData = 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);
        }
    }

通过指定元素集合的构造函数

需要注意两点:

1.toArray方法是Collection函数，子类根据自己数据结构返回一个对象数组。

2.如果size是0，那么elementData 还是会等于 EMPTY_ELEMENTDATA，如果不是0，且elementData.getClass!=Object[].class，那么会重新拷贝一份数据到新的数组中，并且elementData会指向新的数组。

这里提出第一个问题，为什么不通过c.size来判断长度而是直接使用c.toArray()呢？(答案在文章末尾)

    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)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }

内部类

Itr

提供了遍历和删除的方法。该内部类支持遍历删除，且告诉我们为什么迭代器移除元素，必须要调用next方法(这是第二个问题，重点在于cursor和lastRet字段赋值代码上)。

private class Itr implements Iterator<E> {
        //cursor代表要下一个要返回元素的索引
        //int类型，所以默认初始化为0
        int cursor;    
        //最后返回元素的索引，如果没有返回过则为-1
        int lastRet = -1; 
        //修改次数
        int expectedModCount = modCount;
        //构造器
        Itr() {
        //判断是否还有下元素
        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迁移
            cursor = i + 1;
            //返回元素
            //此时i为当前最后一个返回的元素，赋给lastRet
            return (E) elementData[lastRet = i];
        }
        //移除当前最后一个遍历出的元素
        public void remove() {
            //如果lastRet小于0，表明还没有元素被遍历出
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
               //移除元素
                ArrayList.this.remove(lastRet);
               //cursor前移
                cursor = lastRet;
               //将lastRet设置为-1，表明没有最后一个遍历的原色
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

        //JDK8中增加forEachRemaining用于遍历
        @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();
        }
    }

ListItr

在Itr的基础上增加了一些特性，Itr遍历是从头开始，且不可逆。ListItr可以指定下标位置进行遍历。并且支持previous，set和add方法。其中set方法的下标是最后一个遍历元素的位置lastRet。而add方法则是在cursor(下一个遍历元素的位置)位置增加元素。源码就不贴了，理解Itr就不难理解ListItr。

SubList

该类最重要的作用就是切割ArrayList，然后返回一个List集合的其中一部分视图，这里有第三个问题，ArrayList的subList会得到部分视图，那么对于SubList的操作会影响到ArrayList吗。这个类平时自己使用的比较少。理解中使用场景可能是，这里分析一下源码的字段，内部的方法就不看了

 private final AbstractList<E> parent;
      //父类偏移量
        private final int parentOffset;
      //偏移量
        private final int offset;
      //数量
        int size;

        SubList(AbstractList<E> parent,
                int offset, int fromIndex, int toIndex) {
            this.parent = parent;
           //fromIndex表明从何处开始切割视图
            this.parentOffset = fromIndex;
           //因为内部也存在subList方法，所以存储记录offset + fromIndex 表明索引位置
           //如果构造参数offset为0，那么this.parentOffset实际上等效于offset
            this.offset = offset + fromIndex;
           //toIndex - fromIndex为数量
            this.size = toIndex - fromIndex;
            this.modCount = ArrayList.this.modCount;
        }

ArrayListSpliterator

ArrayListSpliterator实现了Spliterator，Spliterator是JDK8出现的，其含义是可分割迭代器，大大增强并行处理的能力。个人理解重点在于trySplit方法。getFence方法可以认为是获取List的最大边界。然后使用二分对List进行切割。

    public ArrayListSpliterator<E> trySplit() {
           //
            int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
            return (lo >= mid) ? null : // divide range in half unless too small
                new ArrayListSpliterator<E>(list, lo, index = mid,
                                            expectedModCount);
        }

需要注意的是，并行处理能力的前提是先进行切割，切割完的数据，可使用多线程去处理，而不是并行的切割处理。

核心方法

ArrayList的核心方法(主要以public为主)从前往后依次来看

trimToSize

如果容器元素数量size小于数组长度，则将其调整为size大小的长度，该方法可以预防浪费空间。

       modCount++;
        if (size < elementData.length) {
            elementData = (size == 0)
              ? EMPTY_ELEMENTDATA
              : Arrays.copyOf(elementData, size);
        }

ensureCapacity

增加ArrayList实例的容量。该方法链中grow方法是核心，第四个问题的答案也在grow中，多线程的情况下，增加元素数据为什么导致集合中出现null值

   public void ensureCapacity(int minCapacity) {
        int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            ? 0
            : DEFAULT_CAPACITY;
        if (minCapacity > minExpand) {
            ensureExplicitCapacity(minCapacity);
        }
    }
    //该方法是扩容的前置方法
    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        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);
       //下面两个判断是针对特殊情况对newCapacity赋值
        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);
    }

size

返回元素数量

isEmpty 判断集合是否为空
contains 判断集合是否包含某个元素。通过遍历方式判断。

    public boolean contains(Object o) {
        return indexOf(o) >= 0;
    }

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

lastIndexOf 元素最后出现的位置，倒叙遍历集合

    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 通过Arrays.copyOf返回一个新的集合

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

toArray 一个返回Object数组，一个返回指定类似的数组 public Object[] toArray() { return Arrays.copyOf(elementData, size); } public <T> T[] toArray(T[] a) { 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(elementData, 0, a, 0, size); if (a.length > size) a[size] = null; return a; }
get

获取指定位置的集合元素，rangeCheck是判断数组是否越界

    public E get(int index) {
        rangeCheck(index);
        return elementData(index);
    }
    E elementData(int index) {
        return (E) elementData[index];
    }

覆盖指定位置的元素

    public E set(int index, E element) {
        rangeCheck(index);

        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }

add 增加元素，其中ensureCapacityInternal方法在上面ensureCapacity聊过，扩容逻辑在该方法链中 public boolean add(E e) { 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; size++; }
remove 该方法提供通过索引删除和通过元素删除

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

** clear** 清空元素 public void clear() { modCount++; // clear to let GC do its work for (int i = 0; i < size; i++) elementData[i] = null; size = 0; }
iterato和listIteratorr 获取迭代器，也就是前面我们说的内部类Itr和ListItr

public ListIterator<E> listIterator(int index) {
        if (index < 0 || index > size)
            throw new IndexOutOfBoundsException("Index: "+index);
        return new ListItr(index);
    }

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

subList 获取SubList对象 public List<E> subList(int fromIndex, int toIndex) { subListRangeCheck(fromIndex, toIndex, size); return new SubList(this, 0, fromIndex, toIndex); }
spliterator

切割对象，提高并行能力

    public Spliterator<E> spliterator() {
        return new ArrayListSpliterator<>(this, 0, -1, 0);
    }

问题答案

第一个问题:通过元素集合Collection<? extends E> c构造ArrayList，为什么先调用c.toArray()，然后再判断size大小呢，而不是先调用c.size判断大小后，再调用c.toArray()？

答案:我们并未对c做任何同步操作，多线程的情况下，如果线程A调用c.size()得到结果是1，还未来得及调用c.toArray()方法时，线程将c的元素移除掉，那么ArrayList就会出现size为1的，elementData.length=0的情况，所以优先使用c.toArray。

第二个问题:为什么ArrayList通过迭代器支持遍历删除，此外为什么迭代器移除元素，必须要调用next方法？

答案:不通过迭代器删除元素时，由于数据会进行前移，可能(不是一定，要考虑元素的位置)会造成数组越界和数据遗漏(i+1的元素前移到i的位置，那么原来i+1的元素就会被遗漏掉)，通过迭代器remove删除元素后，cursor = lastRet(cursor前移，保证正确的遍历)。至于为什么移除元素必须调用next方法是因为迭代器remove的元素必须要遍历过，如果没有遍历过那么lastRet=-1，迭代器会抛出异常，而且删除后lastRet重新等于-1，所以每次删除都需要调用next方法。

第三个问题:ArrayList的subList会得到部分视图，那么对于SubList的操作会影响到ArrayList吗?

答案:会影响到，在SubList源码中我们可以发现，其内部的操作函数实际上都是对ArrayList的elementData的操作。

第四个问题:多线程的情况下，增加元素数据为什么出现null值

因为grow并非线程安全的操作，elementData会重新指向新的数组，如果size发生自增，那么会跨过一个索引下标赋值。

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2020-09-15，如有侵权请联系 cloudcommunity@tencent.com 删除

java