• java集合源码学习（七）ArrayList

    ArrayList 是 Java 集合框架中 List接口 的一个实现类。
    可以说 ArrayList 是我们使用最多的 List 集合，它有以下特点：

    • 容量不固定，想放多少放多少（当然有最大阈值，但一般达不到）
    • 有序的（元素输出顺序与输入顺序一致）
    • 元素可以为 null
    • 效率高
    • size(), isEmpty(), get(), set() iterator(), ListIterator() 方法的时间复杂度都是 O(1)
    • add() 添加操作的时间复杂度平均为 O(n)
    • 其他所有操作的时间复杂度几乎都是 O(n)
    • 占用空间更小
    • 对比 LinkedList，不用占用额外空间维护链表结构


    ArrayList 的成员变量

    1.底层数据结构，数组：

    transient Object[] elementData
    • 由于数组类型为 Object，所以允许添加 null 。
    • transient 说明这个数组无法序列化。
    • 初始时为 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 。
    • 当添加第一个元素时，任何带elementData==DEFAULTCAPACITY_EMPTY_ELEMENTDATA的空数组列表将被扩展为DEFAULT_CAPACITY。 
    • 数组列表的元素存储在数组缓冲区中。 ArrayList的容量就是这个数组缓冲区的长度。

    2.数组初始容量为 10：

    private static final int DEFAULT_CAPACITY = 10;

    3.默认的空数组：

    1. private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    2.  
    3. private static final Object[] EMPTY_ELEMENTDATA = {};

    DEFAULTCAPACITY_EMPTY_ELEMENTDATA和EMPTY_ELEMENTDATA的区别

    • 当无参构造时，Obeject数组elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    • 当有参构造时，如果给定初始容量为0，或者传入集合为空集合（不是null），那么，将空数组EMPTY_ELEMENTDATA赋给elementData；

    4.数组中当前元素个数：

    private int size;

    size <= capacity 。元素个数必定小于数组容量

    5.数组最大容量：

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

    Integer.MAX_VALUE = 0x7fffffff

    换算成二进制： 2^31 - 1，1111111111111111111111111111111

    十进制就是 ：2147483647，二十一亿多。

    一些虚拟器需要在数组前加个 头标签，所以减去 8 。
    当想要分配比 MAX_ARRAY_SIZE 大的个数就会报 OutOfMemoryError。
     

    ArrayList 的关键方法

    1.构造函数

    ArrayList 有三种构造函数：

    1.无参构造

     初始为空数组

    1.  
    2. public ArrayList() {
    3.     
    4.     this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    5. }

    当调用无参构造方法时，elementData数组会被赋于DEFAULTCAPACITY_EMPTY_ELEMENTDATA，且在添加第一位元素时，elementData数组的容量被扩容为10。

    2.有参构造

     根据指定容量，创建个对象数组

    1.  
    2. public ArrayList(int initialCapacity) {
    3.     if (initialCapacity > 0) {
    4.         this.elementData = new Object[initialCapacity];
    5.     } else if (initialCapacity == 0) {
    6.         this.elementData = EMPTY_ELEMENTDATA;
    7.     } else {
    8.         throw new IllegalArgumentException("Illegal Capacity: "+
    9.                                            initialCapacity);
    10.     }
    11. }

      构造一个包含指定集合的元素列表

    1.  
    2. public ArrayList(Collection c) {
    3.     elementData = c.toArray();
    4.     if ((size = elementData.length) != 0) {
    5.         // c.toArray 有可能不返回一个 Object 数组
    6.         if (elementData.getClass() != Object[].class)
    7.             //使用 Arrays.copy 方法拷创建一个 Object 数组
    8.             elementData = Arrays.copyOf(elementData, size, Object[].class);
    9.     } else {
    10.         // replace with empty array.
    11.         this.elementData = EMPTY_ELEMENTDATA;
    12.     }
    13. }

    调用有参构造方法时，如果给定初始容量为0，或者传入集合为空集合（不是null），那么，将空数组EMPTY_ELEMENTDATA赋给elementData，此时在添加第一位元素时，不会扩容为10。

    2.添加元素（add,addAll）：

    1.add(E e)

    1. public boolean add(E e) {
    2.     //对数组的容量进行调整
    3.     ensureCapacityInternal(size + 1);  // Increments modCount!!  modCount+1
    4.     //如果elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
    5.     //在进行第一次元素增加后，列表将被扩展为DEFAULT_CAPACITY=10
    6.     //size=1,elementData.length=10
    7.     elementData[size++] = e;
    8.     return true;
    9. }

    2.add(int index, E element)

    1. //在指定位置添加一个元素
    2. public void add(int index, E element) {
    3.     rangeCheckForAdd(index);
    4.  
    5.     //对数组的容量进行调整
    6.     ensureCapacityInternal(size + 1);  // Increments modCount!!
    7.     //整体后移一位，效率不太好啊
    8.     System.arraycopy(elementData, index, elementData, index + 1,
    9.                      size - index);
    10.     elementData[index] = element;
    11.     size++;
    12. }

    System.arraycopy()方法详解

    3.addAll(Collection c)

      在原来的集合的末尾，添加一个集合

    1.  
    2. public boolean addAll(Collection c) {
    3.     //把该集合转为对象数组
    4.     Object[] a = c.toArray();
    5.     int numNew = a.length;
    6.     //增加容量
    7.     ensureCapacityInternal(size + numNew);  // Increments modCount
    8.     //挨个向后迁移
    9.     System.arraycopy(a, 0, elementData, size, numNew);
    10.     size += numNew;
    11.     //新数组有元素，就返回 true
    12.     return numNew != 0;
    13. }

    4.addAll(int index, Collection c)

      在指定位置，添加一个集合

    1.  
    2. public boolean addAll(int index, Collection c) {
    3.     rangeCheckForAdd(index);
    4.  
    5.     Object[] a = c.toArray();
    6.     int numNew = a.length;
    7.     ensureCapacityInternal(size + numNew);  // Increments modCount
    8.  
    9.     int numMoved = size - index;
    10.     //原来的数组挨个向后迁移
    11.     if (numMoved > 0)
    12.         System.arraycopy(elementData, index, elementData, index + numNew,
    13.                          numMoved);
    14.     //把新的集合数组 添加到指定位置
    15.     System.arraycopy(a, 0, elementData, index, numNew);
    16.     size += numNew;
    17.     return numNew != 0;
    18. }

    3.对数组的容量进行调整：

    1.ensureCapacityInternal(int minCapacity)

    1. private void ensureCapacityInternal(int minCapacity) {
    2.     //还没有添加元素，即elementData=={}
    3.     if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
    4.         //最小容量取默认容量和 当前元素个数 最大值
    5.         minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    6.     }
    7.  
    8.     ensureExplicitCapacity(minCapacity);
    9. }

    2.ensureExplicitCapacity(int minCapacity)

    1. private void ensureExplicitCapacity(int minCapacity) {
    2.     modCount++;
    3.  
    4.     // 容量不够了，需要扩容
    5.     if (minCapacity - elementData.length > 0)
    6.         grow(minCapacity);
    7. }

    3.ensureCapacity(int minCapacity)

    1. public void ensureCapacity(int minCapacity) {
    2.     int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
    3.         // 不是默认的数组，说明已经添加了元素
    4.         ? 0
    5.         // 默认的容量
    6.         : DEFAULT_CAPACITY;
    7.  
    8.     if (minCapacity > minExpand) {
    9.         //当前元素个数比默认容量大
    10.         ensureExplicitCapacity(minCapacity);
    11.     }
    12. }

    我们可以主动调用 ensureCapcity 来增加 ArrayList 对象的容量，这样就避免添加元素满了时扩容、挨个复制后移等消耗。

    4.扩容：

    1.grow(int minCapacity)

    1. private void grow(int minCapacity) {
    2.     int oldCapacity = elementData.length; //elementData数组的容量,不是元素数量
    3.     // 1.5 倍 原来容量
    4.     int newCapacity = oldCapacity + (oldCapacity >> 1);//右移一位
    5.  
    6.     //如果当前容量还没达到 1.5 倍旧容量，就使用当前容量，省的站那么多地方
    7.     if (newCapacity - minCapacity < 0)
    8.         newCapacity = minCapacity;
    9.  
    10.     //新的容量居然超出了 MAX_ARRAY_SIZE
    11.     if (newCapacity - MAX_ARRAY_SIZE > 0)
    12.         //最大容量可以是 Integer.MAX_VALUE
    13.         newCapacity = hugeCapacity(minCapacity);
    14.  
    15.     // minCapacity 一般跟元素个数 size 很接近，所以新建的数组容量为 newCapacity 更宽松些
    16.     elementData = Arrays.copyOf(elementData, newCapacity);
    17. }

    minCapacity一般等于元素个数或者默认容量10

    2.hugeCapacity(int minCapacity)

    1. private static int hugeCapacity(int minCapacity) {
    2.     if (minCapacity < 0) // overflow
    3.         throw new OutOfMemoryError();
    4.     //判断元素个数是否大于最大容量
    5.     return (minCapacity > MAX_ARRAY_SIZE) ?  //MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    6.         Integer.MAX_VALUE :
    7.         MAX_ARRAY_SIZE;
    8. }

    5.查询，修改等操作，直接根据角标对数组操作，都很快：

    1.elementData(int index)

    1. E elementData(int index) {
    2.     return (E) elementData[index];
    3. }

    2.get(int index)

    1. //获取
    2. public E get(int index) {
    3.     //判断index是否在范围内
    4.     rangeCheck(index);
    5.     //直接根据数组角标返回元素，快的一比
    6.     return elementData(index);
    7. }

    3.set(int index, E element)

    将列表中指定位置的元素替换为指定的元素。

    1. //修改
    2. public E set(int index, E element) {
    3.     rangeCheck(index);
    4.     E oldValue = elementData(index);
    5.  
    6.     //直接对数组操作
    7.     elementData[index] = element;
    8.     //返回原来的值
    9.     return oldValue;
    10. }

    6.删除，还是有点慢：

    1.remove(int index)

    1. //根据位置删除
    2. public E remove(int index) {
    3.     rangeCheck(index);
    4.  
    5.     modCount++;
    6.     E oldValue = elementData(index);
    7.  
    8.     //numMoved等于数组元素-索引位置-1.如果numMoved等于0。说明删除的元素是最后一位，
    9.     //然后跳过if语句。
    10.     int numMoved = size - index - 1;
    11.     if (numMoved > 0)
    12.         System.arraycopy(elementData, index+1, elementData, index,
    13.                          numMoved);
    14.     //原数组中最后一个元素删除，数组容量不变
    15.     elementData[--size] = null; // clear to let GC do its work
    16.  
    17.     return oldValue;
    18. }

    2.remove(Object o) 删除某个元素

    1. public boolean remove(Object o) {
    2.     if (o == null) {
    3.         //挨个遍历找到目标
    4.         for (int index = 0; index < size; index++)
    5.             if (elementData[index] == null) {
    6.                 //快速删除
    7.                 fastRemove(index);
    8.                 return true;
    9.             }
    10.     } else {
    11.         for (int index = 0; index < size; index++)
    12.             if (o.equals(elementData[index])) {
    13.                 fastRemove(index);
    14.                 return true;
    15.             }
    16.     }
    17.     return false;
    18. }

    3.fastRemove(int index)

    1. private void fastRemove(int index) {
    2.     modCount++;
    3.     int numMoved = size - index - 1;
    4.     if (numMoved > 0)
    5.         System.arraycopy(elementData, index+1, elementData, index,
    6.                          numMoved);
    7.     elementData[--size] = null; // clear to let GC do its work
    8. }

    4.retainAll(Collection c) 删除两个数组中不同的元素，保留相同的

    1. public boolean retainAll(Collection c) {
    2.     Objects.requireNonNull(c);
    3.     return batchRemove(c, true);
    4. }

    5.batchRemove(Collection c, boolean complement)  删除或者保留指定集合中的元素

    1. private boolean batchRemove(Collection c, boolean complement) {
    2.     final Object[] elementData = this.elementData;
    3.     //使用两个变量，一个负责向后扫描，一个从 0 开始，等待覆盖操作
    4.     int r = 0, w = 0;
    5.     boolean modified = false;
    6.     try {
    7.         //遍历 ArrayList 集合
    8.         for (; r < size; r++)
    9.             //如果指定集合中是否有这个元素，根据 complement 判断是否往前覆盖删除
    10.             if (c.contains(elementData[r]) == complement)
    11.                 elementData[w++] = elementData[r];
    12.     } finally {
    13.         //发生了异常，直接把 r 后面的复制到 w 后面
    14.         if (r != size) {
    15.             System.arraycopy(elementData, r,
    16.                              elementData, w,
    17.                              size - r);
    18.             w += size - r;
    19.         }
    20.         if (w != size) {
    21.             // 清除多余的元素，clear to let GC do its work
    22.             for (int i = w; i < size; i++)
    23.                 elementData[i] = null;
    24.             modCount += size - w;
    25.             size = w;
    26.             modified = true;
    27.         }
    28.     }
    29.     return modified;
    30. }
    31.

    6.clear() 使所有元素置空

    1. public void clear() {
    2.     modCount++;
    3.     //并没有直接使数组指向 null,而是逐个把元素置为空
    4.     //下次使用时就不用重新 new 了
    5.     for (int i = 0; i < size; i++)
    6.         elementData[i] = null;
    7.  
    8.     size = 0;
    9. }

    7.判断状态：

    1.contains(Object o)

    1. public boolean contains(Object o) {
    2.     return indexOf(o) >= 0;
    3. }

    2.indexOf(Object o)遍历，第一次找到就返回

    1. public int indexOf(Object o) {
    2.     if (o == null) {
    3.         for (int i = 0; i < size; i++)
    4.             if (elementData[i]==null)
    5.                 return i;
    6.     } else {
    7.         for (int i = 0; i < size; i++)
    8.             if (o.equals(elementData[i]))
    9.                 return i;
    10.     }
    11.     return -1;
    12. }

    3.lastIndexOf(Object o)倒着遍历

    1. public int lastIndexOf(Object o) {
    2.     if (o == null) {
    3.         for (int i = size-1; i >= 0; i--)
    4.             if (elementData[i]==null)
    5.                 return i;
    6.     } else {
    7.         for (int i = size-1; i >= 0; i--)
    8.             if (o.equals(elementData[i]))
    9.                 return i;
    10.     }
    11.     return -1;
    12. }

    8.转换成 数组：

    1.toArray()

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

    2.toArray(T[] a)

    1. public  T[] toArray(T[] a) {
    2.     //如果只是要把一部分转换成数组
    3.     if (a.length < size)
    4.         // Make a new array of a's runtime type, but my contents:
    5.         return (T[]) Arrays.copyOf(elementData, size, a.getClass());
    6.     //全部元素拷贝到 数组 a
    7.     System.arraycopy(elementData, 0, a, 0, size);
    8.     if (a.length > size)
    9.         a[size] = null;
    10.     return a;
    11. }

    3. Arrays.copyOf()

    1. public static  T[] copyOf(U[] original, int newLength, Classextends T[]> newType) {
    2.     @SuppressWarnings("unchecked")
    3.     T[] copy = ((Object)newType == (Object)Object[].class)
    4.         ? (T[]) new Object[newLength]
    5.         : (T[]) Array.newInstance(newType.getComponentType(), newLength);
    6.     System.arraycopy(original, 0, copy, 0,
    7.                      Math.min(original.length, newLength));
    8.     return copy;
    9. }

    如果 newType 是一个对象对组，就直接把 original 的元素拷贝到 对象数组中；
    否则新建一个 newType 类型的数组。

    9.（rangeCheckForAdd与rangeCheck）

    1.rangeCheck

    1.    private void rangeCheck(int index) {
    2.         if (index >= size)
    3.             throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    4.     }

    检查给定索引是否在范围内，它总是在数组访问之前立即使用，如果索引为负数，则抛出ArrayIndexOutOfBoundsException异常。 

    2.rangeCheckForAdd

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

    一个由add和addAll使用的rangeCheck版本。

    3.outOfBoundsMsg

    1.     private String outOfBoundsMsg(int index) {
    2.         return "Index: "+index+", Size: "+size;
    3.     }

    在 Java 集合深入理解：Abstractist 中我们介绍了 RandomAccess，里面提到，支持 RandomAccess 的对象，遍历时使用 get 比 迭代器更快。

    由于 ArrayList 继承自 RandomAccess， 而且它的迭代器都是基于 ArrayList 的方法和数组直接操作，所以遍历时 get 的效率要 >= 迭代器。

    1. int i=0, n=list.size(); i < n; i++)
    2.       list.get(i);

    比用迭代器更快：

    1. for (Iterator i=list.iterator(); i.hasNext(); )
    2.      i.next();

    另外，由于 ArrayList 不是同步的，所以在并发访问时，如果在迭代的同时有其他线程修改了 ArrayList, fail-fast 的迭代器 Iterator/ListIterator 会报 ConcurrentModificationException 错。


    因此我们在并发环境下需要外部给 ArrayList 加个同步锁，或者直接在初始化时用 Collections.synchronizedList 方法进行包装：
     

    List list = Collections.synchronizedList(new ArrayList(...));

  • 相关阅读:
    【电商API接口的应用：电商数据分析入门】初识Web API(一)
    VUE3 ＜component＞“元组件” 渲染$slots传的插槽
    360智慧生活旗舰产品率先接入“360智脑”能力实现升级
    jvm性能调优实战 - 61常用的JVM调优网站
    免费开源！常用策略函数的复用与累积
    html中的换行(\n)或回车(\r)符号不起作用的解决办法、br、white、space、pre、line
    设计模式：享元模式
    java毕业生设计医院取药系统计算机源码+系统+mysql+调试部署+lw
    ThreadLocal原理和使用场景
    扫雷（蓝桥杯）
  • 原文地址：https://blog.csdn.net/qq_51741292/article/details/125684302