关于java:年轻人不讲武德一起聊聊List集合一

41次阅读

共计 4392 个字符，预计需要花费 11 分钟才能阅读完成。

前言

业精于勤荒于嬉，行成于思毁于随；

在码农的小道上，唯有本人强才是真正的强人，求人不如求己，静下心来，开始思考…

明天一起来聊一聊 List 汇合，看到这里，笔者懂，大家莫慌，先来宝图镇楼 ~

我要打十个年轻人，敢偷袭我老同志，耗子尾汁..

咳咳.. 置信大家满脑子的 ArrayList 已被保国爷爷经典的画面以及台词冲淡了，那么，目标已达到，那咱们言归正传，对于屏幕前帅气的猿友们来说，ArrayList，LinkedList，Vector，CopyOnWriteArrayList… 张口就来，闭眼能写，然而呢，我置信大部分的猿友们并没有刨根问底真正去看过其源码，此时，笔者帅气的脸庞似有似无弥漫起一抹微笑，毕竟是查看过源码的猿，就是那么的不讲武德，吃我一记闪电五连鞭，话不多说，来吧，展现..

一、List 类图

二、源码分析

1. ArrayList（此篇详解）

  • 构造函数 
    // 默认值 - 空数组
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    // ArrayList 底层为数组 transient 关键字：以后数组不能被序列化
    transient Object[] elementData; 

    /**
     * 构造函数
     */
    public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}

从源码中能够看出，结构只为底层数组进行初始化，默认值为空数组；

  • add() – 增加元素办法 
    // ArrayList 元素个数
    private int size;

    // 默认初始容量
    private static final int DEFAULT_CAPACITY = 10;

    // 记录对 ArrayList 操作次数
    protected transient int modCount = 0;

    // ArrayList 最大元素个数
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    /**
     * 增加入口
     */
    public boolean add(E e) {
        // 对数组进行初始化以及扩容
        ensureCapacityInternal(size + 1);
        // 数组中增加元素
        elementData[size++] = e;
        return true;
    }

    // 1. 对数组进行初始化以及扩容
    private void ensureCapacityInternal(int minCapacity) {ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

    // 2. 计算最小容量
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        // 判断数组是否为空，即为第一次增加元素
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            // max 办法：a >= b ? a : b
            // eg: 10 >= 1 -> 10
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

    // 3. 判断是否须要扩容
    private void ensureExplicitCapacity(int minCapacity) {// modCount( 记录批改次数) -> 在以后线程应用迭代器的过程中，如有其余线程批改了 modCount(会判断是否批改操作有误 ( 线程平安问题)) -> 抛出 ConcurrentModificationException 异样
        //      Fail-Fast 机制，疾速失败机制，modCount 申明为 volatile，保障线程之间批改的可见性
        modCount++;

        // 判断是否进行扩容
        if (minCapacity - elementData.length > 0)
            // 具体扩容办法
            grow(minCapacity);
    }

    // 4. 具体扩容
    private void grow(int minCapacity) {
        // 获取数据长度
        int oldCapacity = elementData.length;
        // 计算扩容后长度，第一次为例：0 + (0 >> 1) = 0 + 0 = 0
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        // 判断如果扩容后长度 - 最小容量 <0, 扩容后的长度为最小容量，此判断作用于第一次增加元素时
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        // 计算扩容后长度最大值，最大值为 Integer 的最大值 (2^31-1)
        if (newCapacity - MAX_ARRAY_SIZE > 0) {if (minCapacity < 0) // overflow
                throw new OutOfMemoryError();
            newCapacity = (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
        }

        // 应用 Arrays.copyOf 对咱们数组容量实现扩容
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

从源码中能够看出，增加元素时且会对数组进行初始化或者扩容；

知识点：
第一次扩容也就是第一次 add 时：数组长度 length 扩容为 10，汇合 size 为 1；
第二次扩容也就是第十一次 add 时：数组长度 length 扩容为 15，汇合 size 为 11；
之后每次扩容遵循以下规定，oldCapacity + (oldCapacity >> 1)；

论断：
每扩容后为之前数组长度的 1.5 倍，最大值：Integer 最大值 (2^31-1)，最小值：10；

  • get() – 获取元素办法 
    /**
     * 入口
     */
    public E get(int index) {
        // 校验是否越界
        rangeCheck(index);

        // so easy：通过下标获取元素
        return elementData(index);
    }

    // 校验下标是否越界
    private void rangeCheck(int index) {if (index >= size)
            throw new IndexOutOfBoundsException("Index:"+index+", Size:"+size);
    }

从源码中能够看出，获取元素时就是获取数组元素，通过下标间接获取即可；

  • remove() – 删除元素办法 
    /**
     * 入口
     */
    public E remove(int index) {
        // 校验下标是否越界
        rangeCheck(index);

        // add() 办法中已详情形容
        modCount++;

        // 获取要删除的元素
        E oldValue = elementData(index);

        /**
         * public static native void arraycopy(Object src, int srcPos, Object dest, int destPos, int length);
         *  阐明此办法参数作用：*      src：源数组
         *      srcPos：源数组复制的起始地位
         *      dest：目标数组
         *      destPos：指标数组搁置的起始地位
         *      length：数组元素被复制的数量
         */
        // 对应参数中 length
        int numMoved = size - index - 1;
        // 删除元素其实就是一个数组整体挪动的过程，再将最初一个元素置空即可
        if (numMoved > 0)
            // 此每个参数都需各位猿友细品下，慢慢来，只是一个过程... 如此如此，这般这般，暖男的我在下方提供图，便于猿友们了解
            System.arraycopy(elementData, index+1, elementData, index, numMoved);

        // 将最初一个元素置空，如只有一个元素，置空即可，便于 GC 工作
        elementData[--size] = null; // clear to let GC do its work

        // 返回删除的元素值
        return oldValue;
    }

从源码中能够看出，删除元素实则为数组挪动笼罩的过程，已下图为例，便于大家了解：

  • 源数组：

  • 指标数组 (删除元素后的数组)：

  • 删除下标为 0 的元素 (不)

联合 arraycopy(Object src, int srcPos, Object dest, int destPos, int length) 来讲，可得悉：

  1. src：为上述源数组；
  2. srcPos：源数组要复制的起始地位为 (index+1 = 0+1 = 1)
  3. dest：为上述指标数组
  4. destPos：指标数组搁置的起始地位为 (index=0)；
  5. length：复制的长度为 (size-index-1 = 4-0-1 = 3)
  • 过程演示：

  • == 划重点：==

置信之前没认真钻研过的猿友们，对 ArrayList 删除元素大略过程已有一些理解；

但对于有教训的开发猿来说，笔者大略能猜到两种，一种是二心追寻本心道心坚硬的猿友，另一种呢就是谋求小道扫视局势的猿友；

前者：看到这里，不论是从笔者的形容还是图文联合的了解，貌似有肯定的情理，但过后的我看并不是如此，既然是 arraycopy，那就不应该是挪动笼罩，而是从新复制一个新数组。

后者：我过后查阅源码如同感觉也并不是这样的，记得也是复制一个新数组，而不是挪动笼罩。但笔者形容确又很在理，难道 … 脱漏了什么？

邪魅一笑，嘴角微起，来吧，展现 …

其实嘛，大家说的都没错，实际上的确是复制新的数组，但 ArrayList 这里，源数组和指标数组是用一个呢.

哎 … 人生么，如此这般，细节决定成败。

  • ArrayList 总结：
  1. 底层为数组；
  2. 结构初始化，数组为空数组，汇合 size 为 0，数组 length 为 0；
    第一次扩容也就是第一次 add 时：数组长度 length 扩容为 10，汇合 size 为 1；

第二次扩容也就是第 11 次 add 时：数组长度 length 扩容为 15，汇合 size 为 11；
之后每次扩容遵循以下规定，oldCapacity + (oldCapacity >> 1)，故每次扩容为之前数组长度的 1.5 倍；
最大值：Integer 最大值 2147483647(2^31-1)，最小值：10；

  1. 通过下标去获取元素，故查问效率高，增删效率低；
  2. 线程不平安；
  3. 有 modCount；

2. LinkedList

不讲武德，一起聊聊 List 汇合之 LinkedList

3. Vector

不讲武德，一起聊聊 List 汇合之 Vector

4. CopyOnWriteArrayList

不讲武德，一起聊聊 List 汇合之 CopyOnWriteArrayList

5. List 汇合比照剖析 - 总结篇

不讲武德，一起聊聊 List 汇合之总结篇

~~   码上福利

大家好，我是猿医生：

在码农的小道上，唯有本人强才是真正的强人，求人不如求己，静下心来，开始学习吧 …

正文完
java
发表至： java
2021-01-05
 0
关于java:Java-集合ListSetMap-等相关问答归纳再整理
关于java:Java数组排序和查找
关于java:java培训面试序列化的理解
Sentinel: 接入控制台实时查看监控数据