ArrayList 实现探索

ArrayList 实现探索

捡破烂的诗人 410 2022-07-10
  • 联系方式：1761430646@qq.com
  • 菜狗摸索，有误勿喷，烦请联系

1. 接口实现

  • 1-1657428654711

    • Serializable：序列化接口

    • Cloneable：克隆接口

    • RandomAcess：这是一个标记接口，意味着实现此接口的类，具有可以快速随机访问的特点

      2-1657428654720

    • List：具有List接口的特征

2. 基本属性

2.1 默认初始容量–DEFAULT_CAPACITY

  • 3-1657428654723

  • 这是数组初始化时的默认大小，但并不是空参初始化ArrayList时数组容量就直接赋予这么大，后面具体会讲

2.2 空数组实例–DEFAULTCAPACITY_EMPTY_ELEMENTDATA

  • 4-1657428657004

  • 这个【空数组实例】是专门用来进行无参构造ArrayList时的一个临时代替品，感觉这个其实没必要存在

2.3 实际装载元素的数组–elementData

  • 5-1657428657017

  • 存入ArrayList中的元素都是放置在此数组中，也正是如此，才会说ArrayList的底层是由数组构成的

  • 注意这是由transient修饰的，也即是对象序列化时此成员变量不会进行序列化操作，但实际上ArrayList是重写了序列化与反序列化方法，实现自定义过程。其目的在于这个数组中可能会存在部分位置未存放元素，为了避免这些没有存储数据的内存空间被序列化

2.4 集合大小–size

  • 6-1657428657011

  • 这是集合大小，也即实际装载元素的数组中装载的元素的个数

2.5 数组容量最大值–MAX_ARRAY_SIZE

  • 11-1657428661872

  • 这个值代表的是数组的最大长度，也即意味着ArrayList能够装载的最大元素数量

3. 构造方法

3.1 无参构造方法

  • 7-1657428659386

  • 可以从源码中得知，当使用无参构造方法时，实际上是让装载元素的数组指向一个【空数组实例】，也就是说初始化的时候，数组长度为 0，而不是为 【默认的初始化容量】 10，后续存放元素进来时才会容量首次扩充为 10

    8-1657428659397

    • 这个DEFAULTCAPACITY_EMPTY_ELEMENTDATA就是一个【空数组实例】，跟EMPTY_ELEMENTDATA一样，感觉这样没事定义一个【空数组实例】可能是为了进行语意上的区分

3.2 指定大小的有参构造方法

  • 9-1657428659405

  • 注意一下，指定大小值为 0 时，会直接让elementData指向EMPTY_ELEMENTDATA

3.3 追加指定集合元素的有参构造方法

  • 10-1657428661881

  • 注意一下，指定集合为一个空集合时时，还是会直接让elementData指向EMPTY_ELEMENTDATA

4. 常用方法

4.1 扩充方法–grow

  •     private void grow(int minCapacity) {
        // 获得当前数组实际存放元素的个数
        int oldCapacity = elementData.length;
        // x = n + 0.5 * n,也就是得到一个按照 1.5 倍扩充的扩充值
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        // 如果扩充值比期望值小，那么扩充值 = 期望值，也就是此时按照期望值来扩充
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        // 如果扩充值 > 预期的最大值，那么就用 Integer 的最大值
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // 旧数组的元素复制到新长度数组中去
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

  • 总结起来就是，扩充方法会接受一个预期值，在内部又会计算得到一个按照 1.5 倍扩充后的值，然后取两者种最大值作为实际扩充后的容量值

4.2 查找某个元素–find

  • 12-1657428661874

  • 13-1657428664269

  • 可以看到，查找元素是区分元素是否为null来进行，并且是遍历数组，找到第一个即返回

4.3 往尾部添加元素–add

  • 15

  • 往数组尾部添加元素时会传一个【当前元素数量值 + 1】作为期望值去判断需不需要扩充先，然后再往尾部添加元素

4.4 往指定位置添加元素–add

  • 16

  • 可以看到会先对【指定位置值 index】做合法性检验，接着传一个【当前元素数量值 + 1】作为期望值去判断需不需要扩充先，然后就是对于【指定位置】后半部分的元素整体进行一次移动，最后才是设置【指定位置】的元素值，并且【size】+ 1

4.5 获取指定位置的元素–get

  • 17

  • 18

  • 这个没啥好讲，先做个【索引值 index】合法性检验，然后直接在数组中取即可

4.6 删除指定位置的元素–remove

  • 19

  • 注意【指定位置】后面的元素会整体向前移动

4.7 序列化方法–writeObject

  • 20

  • 特别注意，只会序列化数组中的元素，后面的空位置不会理

5. 总结

  1. 虽然【默认初始容量】为 10，但是使用无参构造ArrayList时实际上指向的是一个【空数组实例】，也即此时数组长度为 0，并不是理所当然的 10，后续存放元素时才会首次扩充为 10

  2. 数组进行扩充时会传进来一个预期值，然后再会计算一个按照【当前存放元素数量 1.5 倍】扩充后的值，两者取最大值决定数组实际扩充后的容量大小

  3. 到某个位置上添加/删除元素时都会导致后面的元素整体移动一波

  4. ArrayList序列化时不会把这个数组序列化进去，而是序列化那些实际存在的元素而已

6. 参考

# 源码 # Java # ArrayList