ArrayList扩容机制分析线程安全分析

1. ArrayList 简介

ArrayList
的底层是数组队列，相当于动态数组。与 Java 中的数组相比，它的容量能动态增长。在添加大量元素前，应用程序可以使用
ensureCapacity
操作来增加
ArrayList
实例的容量。这可以减少递增式再分配的数量。

ArrayList
继承于

AbstractList

，实现了

List

,

RandomAccess

,

Cloneable

,

java.io.Serializable

这些接口。

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable{

  }

RandomAccess
是一个标志接口，表明实现这个这个接口的 List 集合是支持

快速随机访问

的。在
ArrayList
中，我们即可以通过元素的序号快速获取元素对象，这就是快速随机访问。
ArrayList
实现了

Cloneable
接口

，即覆盖了函数
clone()
，能被克隆。
ArrayList
实现了
java.io.Serializable
接口，这意味着
ArrayList
支持序列化，能通过序列化去传输。

1.1. Arraylist 和 Vector 的区别?

ArrayList
是
List
的主要实现类，底层使用
Object[ ]
存储，适用于频繁的查找工作，线程不安全；
Vector
是
List
的古老实现类，底层使用
Object[ ]
存储，线程安全的。

1.2. Arraylist 与 LinkedList 区别?

是否保证线程安全：

ArrayList
和
LinkedList
都是不同步的，也就是不保证线程安全；
底层数据结构：

Arraylist
底层使用的是

Object
数组

；
LinkedList
底层使用的是

双向链表

数据结构（JDK1.6 之前为循环链表，JDK1.7 取消了循环。注意双向链表和双向循环链表的区别，下面有介绍到！）
插入和删除是否受元素位置的影响：

①

ArrayList
采用数组存储，所以插入和删除元素的时间复杂度受元素位置的影响。

比如：执行
add(E e)
方法的时候，
ArrayList
会默认在将指定的元素追加到此列表的末尾，这种情况时间复杂度就是 O(1)。但是如果要在指定位置 i 插入和删除元素的话（
add(int index, E element)
）时间复杂度就为 O(n-i)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作。 ②

LinkedList
采用链表存储，所以对于
add(E e)
方法的插入，删除元素时间复杂度不受元素位置的影响，近似 O(1)，如果是要在指定位置
i
插入和删除元素的话（
(add(int index, E element)
）时间复杂度近似为
o(n))
因为需要先移动到指定位置再插入。
是否支持快速随机访问：

LinkedList
不支持高效的随机元素访问，而
ArrayList
支持。快速随机访问就是通过元素的序号快速获取元素对象(对应于
get(int index)
方法)。
内存空间占用：

ArrayList
的空间浪费主要体现在在 list 列表的结尾会预留一定的容量空间，而
LinkedList
的空间花费则体现在它的每一个元素都需要消耗比
ArrayList
更多的空间（因为要存放直接后继和直接前驱以及数据）。

2. ArrayList 扩容机制分析

    /**
     * ArrayList扩容的核心方法。
     */
    private void grow(int minCapacity) {
        // oldCapacity为老的容量，newCapacity为新的容量
        int oldCapacity = elementData.length;
        //将oldCapacity 右移一位，也就是老的容量的二分之一，
        //我们知道位运算的速度远远快于整除运算，整句运算式的结果就是将新容量更新为旧容量的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);
    }

int newCapacity = oldCapacity + (oldCapacity >> 1),所以 ArrayList 每次扩容之后容量都会变为原来的 1.5 倍左右（oldCapacity 为偶数就是 1.5 倍，否则是 1.5 倍左右）！

奇偶不同，比如：10+10/2 = 15, 33+33/2=49。如果是奇数的话会丢掉小数.

什么是>>? 这都不知道！！！！大哥果断给我两棒子

在这里插入图片描述

吃棒子可以但

“>>”（移位运算符）：>>1 右移一位相当于除 2，右移 n 位相当于除以 2 的 n 次方。这里 oldCapacity 明显右移了 1 位所以相当于 oldCapacity /2。对于大数据的 2 进制运算,位移运算符比那些普通运算符的运算要快很多,因为程序仅仅移动一下而已,不去计算,这样提高了效率,节省了资源

3.线程安全

3.1加锁

3.1.1使用synchronized关键字

大家都熟，这就不用说了把。

3.1.2使用Collections.synchronizedList()

这个感觉大家也都知道，但是我忘记了

在这里插入图片描述

List<String> list=Collections.synchronizedList(new ArrayList<String>());

3.2使用CopyOnWriteArrayList

CopyOnWriteArrayList 类的所有可变操作（add，set等等）都是通过创建底层数组的新副本来实现的。当 List 需要被修改的时候，并不直接修改原有数组对象，而是对原有数据进行一次拷贝，将修改的内容写入副本中。写完之后，再将修改完的副本替换成原来的数据，这样就可以保证写操作不会影响读操作了。

但是这样也会存在一些缺点例如：

内存占用问题

因为 CopyOnWrite 的写时复制机制，所以在进行写操作的时候，内存里会同时驻扎两个对象的内存，这一点会占用额外的内存空间。在元素较多或复杂的情况下，复制的开销很大的

复制过程不仅会占用双倍内存，还需要消耗 CPU 等资源，会降低整体性能。
数据一致性问题

由于 CopyOnWrite 容器的修改是先修改副本，所以这次修改对于其他线程来说，并不是实时能看到的，只有在修改完之后才能体现出来。如果你希望写入的的数据马上能被其他线程看到，CopyOnWrite 容器是不适用的。

流程的话：从名字可以看出，它是满足 CopyOnWrite 的 ArrayList，也就是对一块内存进行修改时，不直接在原有内存块中进行写操作，而是将内存拷贝一份，在新的内存中进行写操作，写完之后，再将原来指向的内存指针指到新的内存，原来的内存就可以被回收，大概这个样子。

3.2.1 使用场景

读多写少

黑名单是最典型的场景，假如我们有一个搜索网站，用户在这个网站的搜索框中，输入关键字搜索内容，但是某些关键字不允许被搜索。这些不能被搜索的关键字会被放在一个黑名单中，黑名单并不需要实时更新，可能每天晚上更新一次就可以了。当用户搜索时，会检查当前关键字在不在黑名单中，如果在，则提示不能搜索。这种读多写少的场景也很适合使用 CopyOnWrite 集合。

3.2.2CopyOnWriteArrayList 读取操作的实现

读取操作没有任何同步控制和锁操作，理由就是内部数组 array 不会发生修改，只会被另外一个 array 替换，因此可以保证数据安全。

     /** The array, accessed only via getArray/setArray. */
    private transient volatile Object[] array;

    public E get(int index) {
        return get(getArray(), index);
    }

    @SuppressWarnings("unchecked")
    private E get(Object[] a, int index) {
        return (E) a[index];
    }

    final Object[] getArray() {
        return array;
    }

3.2.3 CopyOnWriteArrayList 写入操作的实现

CopyOnWriteArrayList 写入操作 add() 方法在添加集合的时候加了锁，保证同步，避免多线程写的时候会 copy 出多个副本。

/**
  * Appends the specified element to the end of this list.
  *
  * @param e element to be appended to this list
  * @return {@code true} (as specified by {@link Collection#add})
  */
 public boolean add(E e) {
     final ReentrantLock lock = this.lock;
     lock.lock();  // 加锁
     try {
         Object[] elements = getArray();
         int len = elements.length;
         Object[] newElements = Arrays.copyOf(elements, len + 1);  // 拷贝新数组
         newElements[len] = e;
         setArray(newElements);
         return true;
     } finally {
         lock.unlock();  // 释放锁
     }
 }

这些都没有太深入的去了解暂时就先这么多吧

在这里插入图片描述

原文链接：https://blog.csdn.net/weixin_42254034/article/details/121182089