ArrayList实现分析（二）——常用操作

2019.08.20 15:42:01字数 1,605阅读 187

上一篇文章ArrayList实现分析（一）——对象创建
)主要是介绍了ArrayList对象创建的三种方式的实现原理，下面重点介绍一下ArrayList提供的常用操作的实现原理。

ArrayList主要提供了两大类的添加元素的方法：添加单个元素和添加多个元素:
下面的两个方法是添加单个元素

//在ArrayList尾部追加新元素e
public boolean add(E e) 
//在index索引指向的位置添加新元素element，原List中处于index索引位置的元素及其后面的元素向右移
public void add(int index, E element)

下面看add(E e)的实现逻辑：

public boolean add(E e) {
        // 判断elementData数组是否需要进行扩容，当前并且对modCount字段进行加1
        ensureCapacityInternal(size + 1);  
        //把的新值E增加到elementData数组最后一位
        elementData[size++] = e;
        return true;
}

首先需要调用ensureCapacityInternal来判断是否需要对elementData数组进行扩容。具体实现如下：

private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

第一个构造函数表示创建一个空的ArrayList，第二个构造函数创建一个初始大小为initialCapacity的ArrayList，第三个构造函数表示使用一个集合对象来创建一个ArrayList对象。
无论调用哪个构造函数，在内部都是使用elementData指向ArrayList存储的数据元素。

ArrayList添加更新元素

ArrayList列表提供了add方法添加元素，add方法有四个重载方法：

public boolean add(E e)
public void add(int index, E element) 
public boolean addAll(Collection<? extends E> c) 
public boolean addAll(int index, Collection<? extends E> c)

这四个重载方法一共分为两类，一类是往ArrayList队列尾添加元素，另一类是往队列指定的索引位置添加元素。首先看第一个add方法的具体实现：

public boolean add(E e) {
        // 判断elementData数组是否需要进行扩容，当前并且对modCount字段进行加1
        ensureCapacityInternal(size + 1);  
        //把的新值E增加到elementData数组最后一位
        elementData[size++] = e;
        return true;
  }

ensureCapacityInternal方法的实现如下：

private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private static int calculateCapacity(Object[] elementData, int minCapacity) {
       //如果elementData是空,那么就返回默认值和minCapacity最大的值
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
}

private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
}

由上面的源码可知，首先执行calculateCapacity方法，来获取添加新元素之后list的大小，然后执行ensureExplicitCapacity进行数组大小的扩容，这里需要对modCount做加一操作，记录了该list对象的变更次数。然后判断当前数组的大小是否可以容纳新的数据。如果不能，则需要进行对数组elementData进行扩容。那些重点看一下grow的实现原理：

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);
        elementData = Arrays.copyOf(elementData, newCapacity);
 }

对数组的进行扩展的算法：首先通过老数组计算第一次新数组的大小（newCapacity）=老数组大小+老数组大小/2，当扩展后的newCapacity仍然小于minCapacity，那么执行newCapacity=minCapacity，让新数组的大小等于minCapacity。如果newCapacity大于MAX_ARRAY_SIZE，那么执行hugeCapacity，找到最大的newCapacity,然后利用Arrays.copy把旧数组数据复制到新数组中，新数组的大小是newCapacity，使用elementData指向新的数组，最后完成数组扩容。

注意：MAX_ARRAY_SIZE是数组可分配的最大大小，有些VM会给数组保留8个字节的数组头部，因此MAX_ARRAY_SIZE=Integer.MAX_VALUE - 8
下面说一下public void add(int index, E element) 与add方法逻辑基本相同，add方法是往队列尾增加元素，该方法是往指定的index位置增加元素，并且把原来index只有的所有数据都往后移动一个位置，具体实现如下：

public void add(int index, E element) {
        //对索引index合法性进行判断
        rangeCheckForAdd(index);
        ensureCapacityInternal(size + 1);  
        //把index后的所有元素进行后移操作
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
}

rangeCheckForAdd会对index的合法性进行判断，ArrayList虽然是可以动态变化的集合对象，但是它不允许在超过ArrayList大小的位置插入新数据。

 private void rangeCheckForAdd(int index) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
 }

ensureCapacityInternal方法实现如上面介绍的，对数据进行扩容。然后调用System.arraycopy把扩展后的elementData中的index之后的所有数据往右边移动一位，最后把新原始赋值到index位置上。
下面介绍一下批量添加元素的方法实现addAll：

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

addAll的实现方式和add类似，都是需要ensureCapacityInternal进行数据扩展,如果是addAll(int index, Collection<? extends E> c)，需要把index后的元素向elementData右边移动numNew个大小。根据源码分析，应该尽量避免使用add(index,e)和addAll(index,c)操作，因为这样会有大量的数据移动操作。
下面介绍set(int index, E element)方法，该方法的作用是用新元素element替换ArrayList中index的位置上的旧元素，并且返回旧元素，实现如下：

public E set(int index, E element) {
        rangeCheck(index);
        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
}

根据源码内容，set方法的实现比较简单。
下面介绍sort方法，这个方法是通过传入的Comparator对象，对list进行排序：

public void sort(Comparator<? super E> c) {
        final int expectedModCount = modCount;
        Arrays.sort((E[]) elementData, 0, size, c);
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
        modCount++;
 }

在sort方法中，首先先获取当前的modCount值，然后再调用 Arrays.sort方法完成对list中的原始数组按照Comparator的要求进行排序，在sort返回之前，检查一下list是否被其他线程进行了修改过，如果有其他线程对list进行过修改，抛出ConcurrentModificationException异常，最后修改modCount。
下面介绍一下lastIndexOf方法和indexOf方法，lastIndexOf是获取list中出现当前元素的最后一个索引值，indexOf是在list中出现当前元素出现的一个索引值。

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

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方法，从后向前遍历list，如果是indexOf方法，从前往后遍历list。
还有一个比较重要的方法： retainAll(Collection<?> c) ,该方法的作用是从当前list中删除c中不包含的元素，也就是获取与c的交集，具体实现如下：

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

    private boolean batchRemove(Collection<?> c, boolean complement) {
        final Object[] elementData = this.elementData;
        int r = 0, w = 0;
        boolean modified = false;
        try {
            for (; r < size; r++)
                if (c.contains(elementData[r]) == complement)
                    elementData[w++] = elementData[r];
        } finally {
            if (r != size) {
                System.arraycopy(elementData, r,
                                 elementData, w,
                                 size - r);
                w += size - r;
            }
            if (w != size) {
                for (int i = w; i < size; i++)
                    elementData[i] = null;
                modCount += size - w;
                size = w;
                modified = true;
            }
        }
        return modified;
}

由上面源码可知，retainAll核心的实现在batchRemove方法中，batchRemove方法在ArrayList中有两个地方使用到：removeAll(Collection<?> c)和retainAll(Collection<?> c)。batchRemove有两个参数，第一个参数c是list，第二个参数是布尔型，当在removeAll中使用的时候，传入false，表示需要从当前ArrayList中删除掉c中所有元素。在retainAll方法中调用的batchRemove传入的是true，表示需要保留c中出现的元素。下面列出核心代码，

 for (; r < size; r++)
                if (c.contains(elementData[r]) == complement)
                    elementData[w++] = elementData[r];

上面的代码是根据complement的值，对elementData进行数据删除等处理，通过elementData[w++] = elementData[r];把需要保留的元素放到elementData数组的左边。下面的代码是当该list被其他线程操作使得当前的ArrayList增加了数据量，把新增元素的追加到保留的数据元素中。

  if (r != size) {
                System.arraycopy(elementData, r,
                                 elementData, w,
                                 size - r);
                w += size - r;
   }

然后是是对elementData中需要删除的元素的所在位置进行赋null。这样的可以使得GC在合适的是对垃圾数据进行清理。

ArrayList实现分析（二）——常用操作 - 简书

ArrayList实现分析（二）——常用操作

ArrayList添加更新元素

Recommend

GitHub - prprprus/softest: Recording Browser Interactions And Generating Test Sc...

使用pprof比较两个时间点的内存占用 | 鸟窝

关于微内核的对话

OpenResty 社区王院生：APISIX 的高性能实践 - 知乎

ReactNative分布式热更新系统 - 前端杂谈 - SegmentFault 思否

JVM优化之循环展开（附有详细的汇编代码） - Java译站

Spring Cloud 源码学习之 Ribbon|springcloud,ribbon,负载均衡,源码|陈一乐

Golang中使用断路器

在实时音视频中，基于 TensorFlow 实现图像识别 - 知乎

端到端一致性,流系统Spark/Flink/Kafka/DataFlow对比总结(压箱宝具呕血之作) - 知乎

About Joyk