【Java容器源码】ArrayList 源码分析

Bertha 。 2022-12-05 00:44 345阅读 0赞

先来看 ArrayList 结构，即继承关系，核心成员变量，主要构造函数：

  1. public class ArrayList<E> extends AbstractList<E>
  2.         implements List<E>, RandomAccess, Cloneable, java.io.Serializable{
  5.         // 默认数组大小10
  6.         private static final int DEFAULT_CAPACITY = 10;
  8.         // 数组存放的容器
  9.         private static final Object[] EMPTY_ELEMENTDATA = {
  10.     };
  12.         // 数组使用的大小，注：length是整个数组的大小
  13.         private int size;
  15.         // 空数组，用于空参构造
  16.         private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {
  17.     };
  19.         // 真正保存数据的数组，注：这里是Object类型 ===> 构造时传入泛型是必要的
  20.           transient  Object[] elementData;
  22.         //---------------------------------------------------------------------
  24.         // 无参数直接初始化，数组大小为空
  25.         // 注：ArrayList 无参构造器初始化时，默认大小是空数组，并不是大家常说的 10，
  26.         //   10 是在第一次 add 的时候扩容的数组值
  27.         public ArrayList() {
  29.             this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
  30.         }
  32.         // 指定容量初始化
  33.         public ArrayList(int initialCapacity) {
  35.             if (initialCapacity > 0) {
  37.               this.elementData = new Object[initialCapacity];
  38.             } else if (initialCapacity == 0) {
  40.               this.elementData = EMPTY_ELEMENTDATA;
  41.             } else {
  43.               throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
  44.             }
  45.         }
  47.         // 指定初始数据初始化
  48.         // <? extends E>：类型，E及E的子类们
  49.         // Collection<? extends E>：E及E的子类的集合
  50.         public ArrayList(Collection<? extends E> c) {
  52.             // elementData 是保存数组的容器，默认为 null
  53.             elementData = c.toArray();
  54.             // 如果给定的集合（c）数据有值
  55.             // size
  56.             if ((size = elementData.length) != 0) {
  58.                 // c.toArray might (incorrectly) not return Object[] (see 6260652)
  59.                 // 如果集合元素类型不是 Object 类型，我们会转成 Object
  60.                 if (elementData.getClass() != Object[].class) {
  62.                     elementData = Arrays.copyOf(elementData, size, Object[].class);
  63.                 }
  64.             } else {
  66.                 // 给定集合（c）无值，则默认空数组
  67.                 this.elementData = EMPTY_ELEMENTDATA;
  68.             }
  69.         }
  70.     }

1.增加

add()

增加单个元素到容器中

  1. public boolean add(E e) {
  3.         // 确保数组大小足够，不够需要扩容（期望容量=size+1）
  4.         ensureCapacityInternal(size + 1);  // Increments modCount!!
  5.         // 直接赋值，线程不安全的
  6.         // 注：这里没有非空判断，因此可以加入null
  7.         elementData[size++] = e;
  8.         // 这里虽然是boolean，但一般只会返回true
  9.         return true;
  10.     }

注：add 时没有对 null 做特殊判断，所以，ArrayList 可以的元素可以为 null；而且，因为获取元素时是通过下标直接获取，所以 ArrayList 可以有多个 null 元素。

addAll()

批量增加，即增加多个元素（集合）到容器中

  1. public boolean addAll(Collection<? extends E> c) {
  3.         Object[] a = c.toArray();
  4.         int numNew = a.length;
  5.         // 确保容量充足，整个过程只会扩容一次（期望容量=size+a.length)
  6.         ensureCapacityInternal(size + numNew);  // Increments modCount
  7.         // 直接将要加入的集合拷贝到elementData后面即可
  8.         // 注：Arrays.copyOf适用于1-->2的拷贝,而sys..适用于对原数组或指定数组的操作
  9.         System.arraycopy(a, 0, elementData, size, numNew);
  10.         size += numNew;
  11.         // 只有要增加的集合为空时，返回false
  12.         return numNew != 0;
  13.       }

2.扩容

ensureCapacityInternal()

计算期望的最小容量

  1. private void ensureCapacityInternal(int minCapacity) {
  3.       // 只有当elementData为空（即构造时没有传入容量 && 第一次扩容)，才使用默认大小10
  4.       if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
  6.         minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
  7.       }
  8.       // 判断是否需要扩容
  9.       ensureExplicitCapacity(minCapacity);
  10.     }

ensureExplicitCapacity()

判断是否需要扩容，并修改modCount记录数组变化。这里需要明白一点，该方法没必要返回bool值，因为不能因为容量不够就不放

  1. private void ensureExplicitCapacity(int minCapacity) {
  3.       // 记录数组被修改
  4.       modCount++;
  5.       // 如果我们期望的最小容量大于目前数组的长度，那么就扩容
  6.       // 注：这里当minCapacity=length时也不扩容
  7.       if (minCapacity - elementData.length > 0)
  8.         grow(minCapacity);
  9.     }

grow()

执行扩容，因为数组在创建时大小就确定了，所以所谓的扩容并不是将当前数组变大了，而是创建一个新的大数组，然后将原来数组元素拷贝过去，最后再将elementData指针指向这个新数组。

  1. private void grow(int minCapacity) {
  3.       int oldCapacity = elementData.length;
  4.       // newCapacity = 1.5 oldCapacity
  5.       int newCapacity = oldCapacity + (oldCapacity >> 1);
  7.       // 如果扩容后的值 < 我们的期望值，就以期望值进行扩容
  8.       if (newCapacity - minCapacity < 0)
  9.         newCapacity = minCapacity;
  11.       // 如果扩容后的值 > jvm 所能分配的数组的最大值，那么就用 Integer 的最大值
  12.       if (newCapacity - MAX_ARRAY_SIZE > 0)
  13.         newCapacity = hugeCapacity(minCapacity);
  15.       // 通过复制进行扩容
  16.       elementData = Arrays.copyOf(elementData, newCapacity);
  17.     }

我们需要注意的四点是：

  1. 新增时，并没有对值进行严格的校验，所以 ArrayList 是允许 null 值的。
  2. 扩容的规则并不是翻倍，是原来容量大小 + 容量大小的一半，即原来容量的 1.5 倍。
  3. ArrayList 中的数组的最大值是 Integer.MAX_VALUE，超过这个值，JVM 就不会给数组分配内存空间了。
    源码在扩容的时候，有数组大小溢出意识，就是说扩容后数组下界不能小于 0，上界不能大于 Integer 的最大值
  4. 扩容完成之后，赋值是非常简单的，直接往数组上添加元素即可：elementData [size++] = e。也正是通过这种简单赋值，没有任何锁控制，所以这里的操作是线程不安全的

扩容的本质

扩容是通过这行代码来实现的：Arrays.copyOf(elementData, newCapacity);，这行代码描述的本质是数组之间的拷贝，扩容是会先新建一个符合我们预期容量的新数组，然后把老数组的数据拷贝过去，我们通过 System.arraycopy 方法进行拷贝，此方法是 native 的方法，源码如下：

  1. /**
  2.      * @param src     被拷贝的数组
  3.      * @param srcPos  从数组那里开始
  4.      * @param dest    目标数组
  5.      * @param destPos 从目标数组那个索引位置开始拷贝
  6.      * @param length  拷贝的长度 
  7.      * 此方法是没有返回值的，通过 dest 的引用进行传值
  8.      */
  9.     public static native void arraycopy(Object src, int srcPos,
  10.                                         Object dest, int destPos,
  11.                                         int length);

我们可以通过下面这行代码进行调用，newElementData 表示新的数组：

  1. System.arraycopy(elementData, 0, newElementData, 0,Math.min(elementData.length,newCapacity))

3.删除

在 ArrayList 中有两种删除，一种是删除指定元素（如上），一种是删除指定索引元素

  • 删除元素：public boolean remove(Object o) ，返回是否删除成功
  • 删除索引：public E remove(int index) ，返回删除的元素

删除指定索引元素很简单，只要一个简单的拷贝就能完成

在这里插入图片描述

所以下面我们来看 ArrayList 是如何删除指定元素的

remove()

寻找要删除元素的索引

  1. public boolean remove(Object o) {
  3.       // 如果要删除的值是 null，找到第一个值是 null 的删除
  4.       // 注：这里把null单独出来，是因为e[idx]==o, 而非空是e[idx].equals(o)
  5.       if (o == null) {
  7.         for (int index = 0; index < size; index++)
  8.           if (elementData[index] == null) {
  10.             fastRemove(index);
  11.             return true;
  12.           }
  13.       } else {
  15.         // 如果要删除的值不为 null，找到第一个和要删除的值相等的删除
  16.         for (int index = 0; index < size; index++)
  17.           // 这里是根据  equals 来判断值相等的，相等后再根据索引位置进行删除
  18.           if (o.equals(elementData[index])) {
  20.             fastRemove(index);
  21.             return true;
  22.           }
  23.       }
  24.       return false;
  25.     }

我们需要注意的两点是：

  • 新增的时候是没有对 null 进行校验的，所以删除的时候也是允许删除 null 值的
  • 找到值在数组中的索引位置，是通过 equals 来判断的，如果数组元素不是基本类型（Integer，String等），而是自定义类型（如User，Item等），则需要重写equals方法

fastRemove()

执行删除，即数组拷贝

  1. private void fastRemove(int index) {
  3.       // 记录数组的结构要发生变动了
  4.       modCount++;
  5.       // numMoved 表示删除 index 位置的元素后，需要从 index 后移动多少个元素到前面去
  6.       // 减 1 的原因，是因为 size 从 1 开始算起，index 从 0开始算起
  7.       int numMoved = size - index - 1;
  8.       if (numMoved > 0)
  9.         // 从 index +1 位置开始被拷贝，拷贝的起始位置是 index，长度是 numMoved
  10.         System.arraycopy(elementData, index+1, elementData, index, numMoved);
  11.       // 数组最后一个位置赋值 null，帮助 GC
  12.       elementData[--size] = null;
  13.     }

removeAll()

批量删除

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

batchRemove()

ArrayList 在批量删除时，如果程序执行正常，只有一次 for 循环，如果程序执行异常，才会加一次拷贝

  1. // complement 参数默认是 false,false 的意思是数组中不包含 c 中数据的节点往头移动
  2.     // true 意思是数组中包含 c 中数据的节点往头移动，这个是根据你要删除数据和原数组大小的比例来决定的
  3.     // 如果你要删除的数据很多，选择 false 性能更好，当然 removeAll 方法默认就是 false。
  4.     private boolean batchRemove(Collection<?> c, boolean complement) {
  6.       final Object[] elementData = this.elementData;
  7.       // r 遍历原数组，表示当前循环的位置
  8.       // w 构建新数组，w 位置之前都是不需要被删除的数据，w 位置之后都是需要被删除的数据
  9.       int r = 0, w = 0;
  10.       boolean modified = false;
  12.         // 双指针执行删除
  13.         try {
  15.         // 从 0 位置开始判断，当前数组中元素是不是要被删除的元素，不是的话移到数组头
  16.         for (; r < size; r++)
  17.           if (c.contains(elementData[r]) == complement)
  18.             elementData[w++] = elementData[r];
  19.           } finally {
  21.         // r 和 size 不等，说明在 try 过程中发生了异常，在 r 处断开
  22.         // 把 r 位置之后的数组移动到 w 位置之后(r 位置之后的数组数据都是没有判断过的数据，
  23.         // 这样不会影响没有判断的数据，判断过的数据可以被删除）
  24.         if (r != size) {
  26.           System.arraycopy(elementData, r,
  27.                            elementData, w,
  28.                            size - r);
  29.           w += size - r;
  30.         }
  32.         // w != size 说明数组中是有数据需要被删除的
  33.         // 如果 w、size 相等，说明没有数据需要被删除
  34.         if (w != size) {
  36.           // w 之后都是需要删除的数据，赋值为空，帮助 gc。
  37.           for (int i = w; i < size; i++)
  38.             elementData[i] = null;
  39.           modCount += size - w;
  40.           size = w;
  41.           modified = true;
  42.         }
  43.       }
  44.       return modified;
  45.     }

4.修改

set()

修改指定索引的元素

  1. public E set(int index, E element) {
  3.         rangeCheck(index);
  5.         E oldValue = elementData(index);
  6.         // 简单通过索引修改就就行
  7.         elementData[index] = element;
  9.         // 返回修改前的值
  10.         return oldValue;
  11.     }

5.迭代器

iterator()

iterator 方法的作用是给用户返回迭代器

  1. public Iterator<E> iterator() {
  3.         return new Itr();
  4.     }
  6.     /**
  7.     * Itr是对迭代器的实现（因为底层是数组，所以可以通过索引实现遍历）
  8.     */
  9.     private class Itr implements Iterator<E>{
  12.         // 迭代过程中，下一个元素的位置，默认从 0 开始。
  13.         int cursor;
  15.         // 记录当前元素索引，因为next获取到元素后cursor++
  16.         // 单独出来的意义还在于多线程下防止重复删除
  17.         int lastRet = -1; 
  19.         // expectedModCount 表示迭代过程中，期望的版本号；modCount 表示数组实际的版本号
  20.         int expectedModCount = modCount;
  22.         //...
  23.     }
  • modCount：保证在当前迭代中，不在对集合进行增加删除操作，add/remove均会改变modCount
  • expectedModCount：记录在迭代开始前的modCount，在迭代过程中若出现变化则抛异常

hasNext()

判断是否还有下一个被迭代元素，即是否已经到数组尾部了（index=length-1）

  1. public boolean hasNext() {
  3.            // cursor 表示下一个元素的位置，size 表示实际大小，如果两者相等，说明已经没有元素可以迭代了，        
  4.            // 如果不等，说明还可以迭代
  5.              return cursor != size;
  6.     }

next()

返回当前元素，并为下一次迭代做准备（cursor+1）。这里注意一点，如果在迭代时，数组被修改了，那迭代就出错了，所以迭代时原则上不允许增删(可以修改set)

  1. public E next() {
  3.            // 迭代过程中，判断版本号有无被修改，有被修改，抛 ConcurrentModificationException 异常
  4.            // 注：增、删都会引起modCount改变，但修改（set）不会
  5.            checkForComodification();
  6.            //本次迭代过程中，元素的索引位置
  7.            int i = cursor;
  8.            if (i >= size)
  9.               throw new NoSuchElementException();
  10.            // 注：ArrayList.this.~可以拿到外部类的属性
  11.            Object[] elementData = ArrayList.this.elementData;
  12.            if (i >= elementData.length)
  13.               throw new ConcurrentModificationException();
  14.             // 下一次迭代时，元素的位置，为下一次迭代做准备
  15.             cursor = i + 1;
  16.             // 返回元素值
  17.             return (E) elementData[lastRet = i];
  18.         }
  20.         // 版本号比较
  21.         final void checkForComodification() {
  23.           if (modCount != expectedModCount)
  24.             throw new ConcurrentModificationException();
  25.         }

remove()

提供一个迭代时，可以删除当前元素的方法，

  1. public void remove() {
  3.           // 如果上一次操作时，数组的位置已经小于 0 了，说明数组已经被删除完了
  4.           if (lastRet < 0)
  5.             throw new IllegalStateException();
  6.           //迭代过程中，判断版本号有无被修改，有被修改，抛 ConcurrentModificationException 异常
  7.           checkForComodification();
  9.           try {
  11.             // 调用ArrayList的删除方法，即modCount也会++
  12.             ArrayList.this.remove(lastRet);
  13.             // 更新cursor，其实也就是回退一位
  14.             cursor = lastRet;
  15.             // -1 表示元素已经被删除，这里也防止重复删除
  16.             lastRet = -1;
  17.             // 删除元素时 modCount 的值已经发生变化，在此赋值给 expectedModCount，保证下次迭代时一致
  18.             expectedModCount = modCount;
  19.           } catch (IndexOutOfBoundsException ex) {
  21.             throw new ConcurrentModificationException();
  22.           }
  23.      }

把 lastRet 再解释一下，我们一般对 remove() 的用法是：

  1. if (itr.next() == obj) {
  3.     itr.remove()
  4. }

而此时 curson 已经移动到下一个了，所以有定义了一个 lastRet 记录上一个位置

6.toArray()

常用于将List转为数组

  1. public Object[] toArray() {
  3.         return Arrays.copyOf(elementData, size);
  4.     }

在ArrayList中还有一个方法：toArray(T[])。但该方法需注意size与length的关系，注意避免出现错误

  1. public <T> T[] toArray(T[] a) {
  3.       // 如果数组长度不够，按照 List 的大小进行拷贝，return 的时候返回的都是正确的数组
  4.       if (a.length < size)
  5.         return (T[]) Arrays.copyOf(elementData, size, a.getClass());
  7.       // 长度刚好则对传入数组进行拷贝
  8.       System.arraycopy(elementData, 0, a, 0, size);
  10.       // 数组长度大于 List 大小的，赋值为 null（其后空间GC）
  11.       if (a.length > size)
  12.         a[size] = null;
  13.       return a;
  14.     }

发表评论

表情：
评论列表 （有 0 条评论，345人围观）

还没有评论，来说两句吧...

相关阅读

    相关 Java容器ArrayList源码分析

    一、什么是容器 容器，用来存储一类相同的数据。数组是一种容器，它是一种线性结构，在查找方面，效率非常高，但是数组的长度需要我们在创建的时候，就设定好。这一性质，让它有些时

    电玩女神电玩女神/ 0 赞/ 406 阅读