Java ArrayList源码阅读笔记(基于JDK17)
创始人
2024-11-11 18:07:56
0

Java ArrayList源码阅读笔记(基于JDK17)

虽然不喜欢看源码,但是据说会让人变强啊,看别的大佬的代码也许才知道怎么处理自己的一坨吧,因此冒着秃顶的风险还是来看看吧。。。
第一遍先简单看看吧,搞不清楚的地方也许会在遥远的将来再复习下吧

1、简介

其实在搞不清楚这玩意儿究竟是什么的情况下,已经稀里糊涂地用它写了好多代码了,而且每当找不到数据结构的时候,口袋里一摸就是ArrayList,所以它到底是个啥?

https://www.runoob.com/java/java-arraylist.html

ArrayList 类是一个可以动态修改的数组,与普通数组的区别就是它是没有固定大小的限制,我们可以添加或删除元素

ArrayList 继承了 AbstractList ,并实现了 List 接口

以上便是比较标准的定义,大概就是一个特殊的数组,可以方便地变大变小

2、类图及类定义

在这里插入图片描述
在这里插入图片描述
ArrayList继承自AbstractList类,实现了ListRandomAccessCloneablejava.io.Serializable接口

  • List接口:表明它是一个有序列表支持添加、删除、查找等操作,并且可以通过下标进行访问
  • RandomAccess接口:标记接口,表明实现这个接口的List支持快速随机访问,即直接通过索引下标访问列表的元素
  • Cloneable接口:表明支持拷贝操作,支持深拷贝或浅拷贝操作
  • java.io.Serializable接口:表明支持序列化操作,可以将对象转换为字节流进行持久化存储或网络传输,非常方便

3、扩容机制

这块经常会被提到,并且所谓“动态”指的也就是这个机制,是该数据结构设计的关键

3.1、构造函数

要看ArrayList怎样进行扩容,那么自然绕不开创建类的实例
以下两个常量,其中DEFAULT_CAPACITY 表示创建ArrayList默认的初始容量10,而EMPTY_ELEMENTDATA 表示的是一个空数组,这是一个共享的空对象数组

// 默认的初始容量 private static final int DEFAULT_CAPACITY = 10; // 共享的空数组实例 private static final Object[] EMPTY_ELEMENTDATA = {}; 

ArrayList中,有3个构造函数:

  • ArrayList()
  • ArrayList(int initialCapacity)
  • ArrayList(Collection c)

ArrayList()是无参构造,默认会创建一个空对象数组,在第一次添加元素时会扩容到容量10

public ArrayList() {     this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } 

ArrayList(int initialCapacity)构造函数需要指定一个初始容量,依据给定的初始容量的大小,创建不同长度的对象数组,或是抛出异常

public ArrayList(int initialCapacity) { 	if (initialCapacity > 0) {   // 初始容量大于0     	this.elementData = new Object[initialCapacity];     } else if (initialCapacity == 0) {         // 创建空数组         this.elementData = EMPTY_ELEMENTDATA;     } else {         // 小于0抛出异常         throw new IllegalArgumentException("Illegal Capacity: "+                                                initialCapacity);    } } 

ArrayList(Collection c)构造函数可以指定另一个集合对象作为参数,将其转换为对象数组(存在空指针风险),按顺序进行返回

public ArrayList(Collection c) {     Object[] a = c.toArray();  // 存在空指针风险     if ((size = a.length) != 0) {         if (c.getClass() == ArrayList.class) {             elementData = a;         } else {             elementData = Arrays.copyOf(a, size, Object[].class);         }     } else {         // replace with empty array.         elementData = EMPTY_ELEMENTDATA;     } } 

3.2、扩容时机

那么,到底什么时候需要扩容呢,以及怎样进行扩容呢?
接下来,借助ArrayListadd(E e)方法一探究竟

public boolean add(E e) {     modCount++;   // 修改次数加1     add(e, elementData, size);   // 调用重载方法     return true; } 

add(E e)内部又调用了另一个重载方法add(E e, Object[] elementData, int s),是为了在字节码转化上优化,把方法进行了拆分

/**  * This helper method split out from add(E) to keep method  * bytecode size under 35 (the -XX:MaxInlineSize default value),  * which helps when add(E) is called in a C1-compiled loop.  */ private void add(E e, Object[] elementData, int s) {     if (s == elementData.length)         elementData = grow();   // 长度达到最大,调用grow()扩容     elementData[s] = e;  // 数组索引赋值,并且size+1     size = s + 1; } 

s代表size,用来记录元素的个数,当元素个数达到当前对象数组的长度的时候,就需要进行扩容了,此时会调用grow()方法,扩容后,长度就够应付一阵子了,此时将元素填到对应位置上就可以了,结合前面默认容量为10,可知,第一次扩容将会是在增加第11个元素的时候

3.3、扩容方法

grow()便是用来处理扩容的方法,内部又调用了另一个重载方法,将当前size + 1作为参数

private Object[] grow() {     return grow(size + 1); } 

oldCapacity 代表的就是旧对象数组的长度,判断其大于0也就是有元素,elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA则是判断数组元素是否由默认无参构造器初始化
通过ArraysSupport.newLength(int oldLength, int minGrowth, int prefGrowth)进行扩容
其中oldLength代表的就是旧的数组容量,minGrowth则是最少需要保证的扩容大小,没有富余,prefGrowth则是表示推荐的扩容大小,一般会有富余
oldCapacity >> 1是一个位运算,表示0.5倍的原数组容量,那么对应的含义就是推荐扩容到原数组的1.5倍

 private Object[] grow(int minCapacity) {     int oldCapacity = elementData.length;   // 原来数组的容量     if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {         int newCapacity = ArraysSupport.newLength(oldCapacity,               minCapacity - oldCapacity, /* minimum growth */               oldCapacity >> 1           /* preferred growth */);         return elementData = Arrays.copyOf(elementData, newCapacity);     } else {         return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];     } } 

newLength()是有可能OOM的,如果成功的话就返回扩容后的长度

public static int newLength(int oldLength, int minGrowth, int prefGrowth) {     // preconditions not checked because of inlining     // assert oldLength >= 0     // assert minGrowth > 0      int prefLength = oldLength + Math.max(minGrowth, prefGrowth); // might overflow     if (0 < prefLength && prefLength <= SOFT_MAX_ARRAY_LENGTH) {         return prefLength;     } else {         // put code cold in a separate method         return hugeLength(oldLength, minGrowth);     } } 

Arrays.copyOf(elementData, newCapacity)将原数组依照新的容量进行拷贝

public static  T[] copyOf(T[] original, int newLength) {     return (T[]) copyOf(original, newLength, original.getClass());  } 
public static  T[] copyOf(U[] original, int newLength, Class newType) {     @SuppressWarnings("unchecked")     T[] copy = ((Object)newType == (Object)Object[].class)         ? (T[]) new Object[newLength]         : (T[]) Array.newInstance(newType.getComponentType(), newLength);     System.arraycopy(original, 0, copy, 0,                      Math.min(original.length, newLength));     return copy; } 

最终其实调用的是nativearraycopy(),将源数组src从指定位置srcPos拷贝指定长度length到目标数组destdestPos位置
最终,实现将数据从旧数组拷贝到扩容后的新数组,返回给elementData
这边应该是浅拷贝,但是引用的对象数组地址肯定变了

public static native void arraycopy(Object src,  int  srcPos,                                     Object dest, int destPos,                                     int length); 

比如我们先创建ArrayList,扔10个数据给它,此时引用的对象数组地址为728,然后再增加一个,触发扩容
在这里插入图片描述
新容量计算出来是15,然后创建一个地址在760的新数组,容量为15
在这里插入图片描述
拷贝完成后,原来的元素地址没有变,说明仅仅是拷贝了引用,内容没有变,因此拷贝效率比较高,但是elementData的对象数组地址变了
在这里插入图片描述
先看这么多,如有问题和不足欢迎指正~~

https://www.runoob.com/manual/jdk11api/java.base/java/util/ArrayList.html
https://javaguide.cn/java/collection/arraylist-source-code.html
https://www.cnblogs.com/KRDecad3/p/17800902.html

相关内容

热门资讯

规律教程!xpoker辅助助手... 规律教程!xpoker辅助助手德州辅助app官方最新版本介绍下载(果真真的有挂)1、每一步都需要思考...
详细教程!!wpk私人辅助德扑... 详细教程!!wpk私人辅助德扑之星透视软件(一直真的有挂)1、下载好wpk私人辅助辅助软件之后点击打...
教你教程!cloudpoker... 教你教程!cloudpoker外挂WePOKer有没有透视方法(一般真的有挂)1、cloudpoke...
专业教程!wejoker黑侠辅... 专业教程!wejoker黑侠辅助器HHpoker可以开挂吗(一贯真的有挂);进入游戏-大厅左侧-新手...
透牌教程!哈糖大菠萝辅助器we... 透牌教程!哈糖大菠萝辅助器wepoker到底能不能透视(都是真的有挂);1、首先打开哈糖大菠萝辅助器...
2025新版技巧!wpk模拟器... 2025新版技巧!wpk模拟器是什么天天畅玩德州有挂吗(好像真的有挂);1、首先打开wpk模拟器是什...
新版2025教程!wepoke... 新版2025教程!wepoker有没有透视方法wpk德州辅助(的确是有挂的)1、点击下载安装,wep...
扑克教程!!impoker辅助... 扑克教程!!impoker辅助wepoker私人局作弊开挂方法(其实真的有挂);一、impoker辅...
wpk教程!pokemmo脚本... wpk教程!pokemmo脚本手机版wepoker德州开挂辅助方法(的确是有挂的)1、构建自己的po...
攻略教程!!菠萝辅助器免费版的... 攻略教程!!菠萝辅助器免费版的功能介绍德州大菠萝摆牌攻略(一贯真的有挂)1)菠萝辅助器免费版的功能介...