ArrayList集合深度解析

今天药忘吃喽~ 2021-11-05 05:56 393阅读 0赞

### 一. 手写高仿ArrayList集合 ###

**基本原理思想**

Arraylist集合底层使用动态数组实现，随机查询效率非常快，插入和删除需要移动整个数组、效率低。

**1. 高仿ArrayList集合**

public interface MyList<E> {
        /**
         * 集合的大小(长度)
         * @return
         */
        int size();
        /**
         * 往集合中添加我们的元素
         * @param e
         * @return
         */
        boolean add(E e);
        /**
         * 使用下标查询到我们的集合元素
         * @param index
         * @return
         */
        E get(int index);
        /**
         * 使用下标位置删除我们的元素
         * @param index
         * @return
         */
        public E remove(int index);
    }

public class MyArraylist<E> implements MyList<E> {
        /**
         * elementData数据存放我们Arraylist所有的数据 transient作用不能序列化
         */
        transient Object[] elementData;
        /**
         * 给我们的数组容量赋值为空
         */
        private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
        /*
         * 数组的容量默认大小为0
         */
        private int size;
        /**
         * 数组默认容量大小
         */
        private static final int DEFAULT_CAPACITY = 10;
        /**
         * 2的31次方-1 -8
         */
        private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    
        public MayiktArraylist() {
            // 给我们的数组容量赋值为空
            this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
        }
    
        @Override
        public int size() {
            return size;
        }
    
        @Override
        public boolean add(E e) {
            // 对我们的数组实现【扩容】
            ensureCapacityInternal(size + 1);
            // 对我们的数据元素【赋值】
            elementData[size++] = e;
            return true;
        }
    
        @Override
        public E get(int index) {
            rangeCheck(index);
            // 根据下标从数组中查询到数据
            return (E) elementData[index];
        }
    
        @Override
        public E remove(int index) {
            // 检查我们的下标位置是否越界
            rangeCheck(index);
            // 获取要删除的对象
            E oldValue = get(index);
            //计算移动的位置
            int numMoved = size - index - 1;
            // 判断如果删除数据的时候 不是最后一个的情况下，将删除后面的数据往前移动一位
            if (numMoved > 0) {
                System.arraycopy(elementData, index + 1, elementData, index,
                        numMoved);
            }
            // 如果numMoved 为0的情况下，说明后面不需要往前移动，直接将最后一条数据赋值为null
            elementData[--size] = null; // clear to let GC do its work
            return oldValue ;
        }
    
        private void rangeCheck(int index) {
            if (index >= size)
                throw new IndexOutOfBoundsException("下标位置越界啦index:" + index);
        }
    
        private void ensureCapacityInternal(int minCapacity) {
            // 添加元素的时候 如果我们数组是为空的情况下
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
                //DEFAULT_CAPACITY =10；   minCapacity=0+1  DEFAULT_CAPACITY=10 10>1
                //minCapacity=10;
                minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
            }
            ensureExplicitCapacity(minCapacity);
        }
    
        // modCount++; 增删改的时候  modCount++
        private void ensureExplicitCapacity(int minCapacity) {
            // 10- 数组长度 （0） 10-0 >0  作用:判断我们数组中是否需要继续扩容
            if (minCapacity - elementData.length > 0) {
                // 对我们的数组实现扩容
                grow(minCapacity);
            }
        }
    
        // length 和size区别
        private void grow(int minCapacity) {
            // 获取我们的数组的长度 old原来的 new新的 原来数组容量 0；
            int oldCapacity = elementData.length;
            // 新的容量 = 原来的容量 + 原来的容量/2 = 0
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            // 新的容量(0)-最小的容量(10) < 0  -10
            if (newCapacity - minCapacity < 0) {
                // 新的容量=10 作用：第一次对我们数组做初始化容量操作
                newCapacity = minCapacity;
            }
            // 判断我们扩容长度大于Integer 21 最大值的情况下
            // 限制我们数组扩容最大值
            if (newCapacity - MAX_ARRAY_SIZE > 0)
                newCapacity = hugeCapacity(minCapacity);
            // 开始对我们的数组实现扩容 对我们的数据实现扩容（newCapacity） 将旧的数组数据复制到新的数组中，并可以指定长度
            elementData = Arrays.copyOf(elementData, newCapacity);//这里无非就是把相同的数据复制了一份，并重新指定了数组的length
        }
    
        /**
         * 判断我们最小的初始化容量
         * @param minCapacity minCapacity==最小的容量>Integer 21 最大值的情况下  Integer.MAX_VALUE
         *                    minCapacity 相当于当前添加元素的下标位置
         * @return
         */
        private static int hugeCapacity(int minCapacity) {
            /*
                Integer.MAX_VALUE ： 2147483647
                Integer.MAX_VALUE + 1 ：-2147483648
                只要大于IntegerMAX_VALUE，就会变为负数，所以这里判断是否小于0
             */
            if (minCapacity < 0) // overflow
                throw new OutOfMemoryError();
            return (minCapacity > MAX_ARRAY_SIZE) ?
                    Integer.MAX_VALUE :
                    MAX_ARRAY_SIZE;
        }
    }

public class Test {
        public static void main(String[] args) {
    
            MyArraylist<String> list= new MyArraylist<String>();
    
            for (int i = 0; i < 10; i++) {
                list.add("元素" + i);
            }
            System.out.println(list.size());
    
            list.add("元素11");
    
            System.out.println("删除数据之前:");
            for (int i = 0; i < list.size(); i++) {
                System.out.println(list.get(i));
            }
    //        // 下一次数组扩容是在什么时候呢？
            list.remove(2);
            System.out.println("删除数据之后:");
            for (int i = 0; i < list.size(); i++) {
                System.out.println(list.get(i));
            }
    //        // 数组的下标为0 开始 删除第一条数据 10=11
    //        System.out.println(list.get(10));
    
        }
    }

**小结：**第一次add的时候，会扩容/初始化 数组length为10，下一次扩容是在什么时候？

答案：添加第11条数据的时候【原理见ensureExplicitCapacity()方法】

添加第11条数据的时候，length会扩容到多少呢？  
答案：15 【原理见grow()方法】  
                 // 新的容量 = 原来的容量 + 原来的容量/2 = 10 + 10/2 = 15  
                int newCapacity = oldCapacity + (oldCapacity >> 1);  
以此类推，添加第16条的时候，会扩容到16+16/2=24

数组最大容量就是Integer.MAX\_VALUE

**2. 仔细看ArrayList的源码，不难发现，每次add和remove的时候，都会调用全局变量modCount++**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FraXJhTmlja3k_size_16_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FraXJhTmlja3k_size_16_color_FFFFFF_t_70 1][]

为什么这么做呢，此时我们先引入一个理论：**Fail-Fast机制原理**

Fail-Fast是我们Java集合框架为了解决集合中结构发生改变的时候，快速失败的机制。

举例说明：

package com.example;
    
    import java.util.ArrayList;
    import java.util.List;
    import java.util.concurrent.CopyOnWriteArrayList;
    
    public class Test004 {
    
        // 定义一个全局的集合存放 存在在高并发的情况下线程安全的问题
        private List<String> strings = new ArrayList<String>();
    //    private List<String> strings = new CopyOnWriteArrayList<>();
    
        public static void main(String[] args) {
            new Test004().startRun();
        }
    
        public void startRun() {
            new Thread(new ThreadOne()).start();
            new Thread(new ThreadTWo()).start();
        }
    
        // 打印我们的数据
        private void print() {
            strings.forEach((t) -> System.out.println("t:" + t));
        }
    
        class ThreadOne implements Runnable {
            @Override
            public void run() {
                // 存储数据
                for (int i = 0; i < 10; i++) {
                    strings.add("i:" + i);
                    print(); // 打印数据
                }
            }
        }
    
        class ThreadTWo implements Runnable {
            @Override
            public void run() {
                for (int i = 10; i < 20; i++) {
                    strings.add("i:" + i);
                    print();
                }
            }
        }
    }

执行main方法，会报错：ConcurrentModificationException即并发修改异常

![20190814093148672.png][]

那么我们定位到ArrayList的第1252行：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FraXJhTmlja3k_size_16_color_FFFFFF_t_70 2][]

即我们调用下图的时候，会走到上图ArrayList源码（用for each的时候，底层还是用for循环去遍历）

![20190814093504618.png][]

**for each原理**：会把modCount赋值给一个临时变量/期望变量expectedModCount，for循环的时候，判断modCount的值是否发生变化，如果没发生变化，才会进行打印值等操作，如果发生变化，则会抛出并发修改异常。

**为什么会抛出异常：**modCount是全局的，可能会被add，remove进行更改，而我们的临时变量expectedModCount是局部的，不会更改。线程一和线程二可能会同时调用add方法，比如线程一调用完add，在打印之前，线程二调用add方法(modCount++)，此时会导致modCount和expectedModCount不一致，则抛出并发修改异常。

解决上面Fail-Fast场景，可以使用**CopyOnWriteArrayList**，该集合是，添加和修改的时候都加了Lock锁。

**CopyOnWriteArrayList特点：**

*  内部持有一个ReentrantLock lock = new ReentrantLock();
 *  底层是用volatile transient声明的数组 array
 *  读写分离，写时复制出一个新的数组，完成插入、修改或者移除操作后将新数组赋值给array

**3. ArrayList删除原理**

** 这里我们重点分析System.arraycopy方法，首先贴出ArrayList的remove方法**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FraXJhTmlja3k_size_16_color_FFFFFF_t_70 3][]

System提供了一个静态方法arraycopy(),我们可以使用它来实现数组之间的复制，其函数原型是：

public static void arraycopy(Object src, int srcPos, Object dest, int destPos, int length) ；参数解析如下：

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td style="width:118px;">src</td> 
   <td style="width:379px;">源数组</td> 
  </tr> 
  <tr> 
   <td style="width:118px;">srcPos</td> 
   <td style="width:379px;">源数组要复制的起始位置</td> 
  </tr> 
  <tr> 
   <td style="width:118px;">dest</td> 
   <td style="width:379px;">目的数组</td> 
  </tr> 
  <tr> 
   <td style="width:118px;">destPos</td> 
   <td style="width:379px;">目的数组放置的起始位置</td> 
  </tr> 
  <tr> 
   <td style="width:118px;">length</td> 
   <td style="width:379px;">复制的长度</td> 
  </tr> 
 </tbody> 
</table>

注意：src 和 dest都必须是同类型或者可以进行转换类型的数组。下面举例讲解：

package com.example;
    
    public class Test003 {
        public static void main(String[] args) {
    
            Object[] objects = new Object[]{"0", "1", "2", "3"};
    
            // 要删除元素的索引，也就是目的数组放置的起始位置
            int index = 0;
            // 源数组要复制的起始位置
            int destPos = index + 1;
            // 要复制的长度
            int numMoved = objects.length - index - 1;
    
            System.arraycopy(objects, destPos, objects, index, numMoved);
            objects[objects.length - 1] = null;
            for (int i = 0; i < objects.length; i++) {
                System.out.println(objects[i]);
            }
    
        }
    }

运行结果为：

![20190814105042244.png][]

那么疑问来了，我都删了，为什么还有四个元素？

答案：这是数组的长度为4，在实际ArrayList删除的时候，会发现![2019081410524750.png][]，即集合的size会减1，但是数组的容量还是没变的，这点不要混淆了~  。如果要删除1，即前面的元素不会影响，只移动后面的，并把最后一个置为null。

--------------------

下面贴出一段代码：

public class AAA {
        public static void main(String[] args) {
            ArrayList list = new ArrayList();
            list.add("a");
            list.add("b");
            list.add("c");
            list.add("d");
            System.out.println(list.size());
    
            list.remove(3);
            System.out.println(list.size());
            System.out.println(list.get(4));
    }

执行结果为：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FraXJhTmlja3k_size_16_color_FFFFFF_t_70 4][]

说好的删了会置为null呢？原因是ArrayList源码中调用get()方法时有个下标监测判断~

private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException("下标位置越界啦index:" + index);
        }
    }

--------------------

ArrayList的remove方法核心就是使用了System的静态方法arraycopy( )；再次贴出我们手写的ArrayList源码：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FraXJhTmlja3k_size_16_color_FFFFFF_t_70 5][]

可以发现，会先判断numMoved，如果numMoved大于0，证明要删除的不是最后一个元素，则执行System.arraycopy方法进行数组复制；复制完成后，会执行 elementData\[--size\] = null； 将最后一个元素置为null。并且size减1。（--size代表先执行size=size-1，然后再使用size的值，所以将数组的第size-1个元素，也就是最后一个元素置为null【注意索引从0开始】）

### 二. ArrayList，Vector，**CopyOnWriteArrayList 对比** ###

**1. ArrayList与Vector的区别**

说到这里，我们又会想到一个集合Vector，该集合是ArrayList的前身，相信有一定基础的小伙伴都了解过该集合。

这里我结合源码，列举一下ArrayList与Vector的区别：

**相同点：**底层都是采用数组实现

**不同点：**

**① 默认初始化时候**

Arraylist 默认 不会对我们数组做初始化

![20190814101121998.png][]

![2019081410113470.png][]

（第一次调用add方法的时候 才会初始化）

![20190814101232209.png][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FraXJhTmlja3k_size_16_color_FFFFFF_t_70 6][]

![2019081410130760.png][]

Vector 默认初始化的大小为10

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FraXJhTmlja3k_size_16_color_FFFFFF_t_70 7][]

**② 扩容区别**

ArrayList扩容：在原来数组的基础之上增加50%，即新容量是旧容量的1.5倍

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FraXJhTmlja3k_size_16_color_FFFFFF_t_70 8][]

Vector扩容：在原来数组基础之上再增加100%，即新容量是旧容量的2倍（如果没自定义容量capacityIncrement），所以新容量newCapacity = oldCapacity + oldCapacity；

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FraXJhTmlja3k_size_16_color_FFFFFF_t_70 9][]

那么如何自定义capacityIncrement，直接调用如下Vector的方法：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FraXJhTmlja3k_size_16_color_FFFFFF_t_70 10][]

**③ 线程是否安全（主要看增删，查的时候不存在线程安全问题）**

ArrayList  默认的情况下 线程不安全的，因为没加线程同步，没加锁。

Vector 线程是安全的 效率是非常低的 查询 增加 、删除都加上了锁。

![20190814102429143.png][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FraXJhTmlja3k_size_16_color_FFFFFF_t_70 11][]

![20190814102555506.png][]

**2. CopyOnWriteArrayList和Vector区别：**

**Vector**：读，写，查都加上了synchronized同步锁（不建议使用）

**CopyOnWriteArrayList**：写，删的时候加了Lock锁，但读的时候没加锁；CopyOnWriteArrayList支持读多写少的并发情况

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FraXJhTmlja3k_size_16_color_FFFFFF_t_70]: /images/20211104/8c416116eb354c11bfe8089e09e32714.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FraXJhTmlja3k_size_16_color_FFFFFF_t_70 1]: /images/20211104/1c8a79c8ad4c4431b82ca62db7513106.png
[20190814093148672.png]: /images/20211104/0afb6f808a2441ea87a28253c18b9484.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FraXJhTmlja3k_size_16_color_FFFFFF_t_70 2]: /images/20211104/98ee556c68c04c118ab68e3d353d4113.png
[20190814093504618.png]: /images/20211104/e91bf57cb6734c53934616aeec61f147.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FraXJhTmlja3k_size_16_color_FFFFFF_t_70 3]: /images/20211104/61585d50b5db487a8bddf0fa98d0b7dd.png
[20190814105042244.png]: /images/20211104/627248971dcd45ed929973771a91525b.png
[2019081410524750.png]: /images/20211104/7d28ea4d418c4c2898def85ea7f1b3ff.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FraXJhTmlja3k_size_16_color_FFFFFF_t_70 4]: /images/20211104/1015cb43cd29422a9006867c6378989a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FraXJhTmlja3k_size_16_color_FFFFFF_t_70 5]: /images/20211104/d09e5e7601c6423e9749809bdde5d751.png
[20190814101121998.png]: /images/20211104/cea9e874886442b494ac606ed8dca9a0.png
[2019081410113470.png]: /images/20211104/0f6b85ffa82a47378aea32f0b8d19e8f.png
[20190814101232209.png]: /images/20211104/6d7cf0ba03f547ae95d4f9c60efdf42b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FraXJhTmlja3k_size_16_color_FFFFFF_t_70 6]: /images/20211104/1db6cf201f5d44959174fe2a7ea70d20.png
[2019081410130760.png]: /images/20211104/a355f8c6a9fa475a856044d5e6b3b054.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FraXJhTmlja3k_size_16_color_FFFFFF_t_70 7]: /images/20211104/1fc37dfef86e4f628c9482907ebc1477.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FraXJhTmlja3k_size_16_color_FFFFFF_t_70 8]: /images/20211104/9226ede25b5c4560b233409bf968aa18.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FraXJhTmlja3k_size_16_color_FFFFFF_t_70 9]: /images/20211104/e624e5e2617a4a219eeeace270d4610f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FraXJhTmlja3k_size_16_color_FFFFFF_t_70 10]: /images/20211104/f7429c21cdf2416bb3c8a1b8d5f1c790.png
[20190814102429143.png]: /images/20211104/bec30cae51b54e4da030141c697a9197.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FraXJhTmlja3k_size_16_color_FFFFFF_t_70 11]: /images/20211104/461c74fbe358490e92d600118eec2621.png
[20190814102555506.png]: /images/20211104/ef05a98795f04fdea7e4d811851d560c.png