当前位置：首页 > news >正文

Java集合源码解析之ArrayList

news 2025/9/3 6:35:27

1.ArrayList源码解析

整体流程图概览

构造方法

无参构造方法

有参构造方法

add()

重点子方法grow(xxx)

2.LinkedList 源码解析

3.HashMap源码解析****※

1.ArrayList源码解析

整体流程图概览

构造方法

arrayList的构造方法就做一件事情，就是初始化一下储存数据的容器，其实本质上就是一个数组，在其中就叫elementData

无参构造方法

/*** 构造一个空容量的数组（DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}）*/public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}

有参构造方法

   /*** Constructs an empty list with the specified initial capacity.** @param initialCapacity the initial capacity of the list* @throws IllegalArgumentException if the specified initial capacity*                                  is negative*/public ArrayList(int initialCapacity) {if (initialCapacity > 0) {this.elementData = new Object[initialCapacity];} else if (initialCapacity == 0) {this.elementData = EMPTY_ELEMENTDATA;// /将自定义的容量大小当成初始化elementData的大小} else {throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);}}

add()

/*** 新增元素操作，执行如下操作：*      List list = new ArrayList();*      list.add("a1");*/// eg1：第一次新增元素e="a1"public boolean add(E e) {/** 确定是否需要扩容，如果需要，则进行扩容操作*/ensureCapacityInternal(size + 1); // eg1：size=0// eg1：size=0，elementData[0]="a1"，然后a自增为1elementData[size++] = e;return true;}// eg1：第一次新增元素，size=0，则：minCapacity=size+1=0+1=1private void ensureCapacityInternal(int minCapacity) {// eg1：第一次新增元素，calculateCapacity方法返回值为DEFAULT_CAPACITY=10ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));}/*** 计算ArrayList的容量，如果elementData数组中没有已存储的元素，则返回默认值10，否则，返回minCapacity。*/// eg1：第一次新增元素，elementData={} minCapacity=1private static int calculateCapacity(Object[] elementData, int minCapacity) {if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) // DEFAULTCAPACITY_EMPTY_ELEMENTDATA={}return Math.max(DEFAULT_CAPACITY, minCapacity); // eg1：return 10return minCapacity;}/*** 确保明确的ArrayList的容量*/// eg1：minCapacity=10private void ensureExplicitCapacity(int minCapacity) {/** 变化次数加1 */modCount++; // eg1: modCount++后，modCount=1/** 如果所需的【最小容量】大于elementData数组的容量，则进行扩容操作 */if (minCapacity - elementData.length > 0)  // eg1：elementData.length=0grow(minCapacity); // eg1：minCapacity=10}

重点子方法grow(xxx)

grow(xxx); arrayList核心的方法，能扩展数组大小的真正秘密

/*** 增加容量以确保它至少可以容纳最小容量参数指定的元素数量。*/// eg1：minCapacity=10private void grow(int minCapacity) {/** 原有数组elementData的长度 */int oldCapacity = elementData.length; // eg1：oldCapacity=0/*** A >> 1 等于 A/2* eg: 3 >> 1 = 3/2 = 1*     4 >> 1 = 4/2 = 2* ------------------------* A << 1 等于 A*2* eg: 3 << 1 = 3*2 = 6*     4 << 1 = 4*2 = 8** 000100 >> 1 = 000010* 000100 << 1 = 001000*//** 新增oldCapacity的一半整数长度作为newCapacity的额外增长长度 */int newCapacity = oldCapacity + (oldCapacity >> 1); // eg1：newCapacity=0+(0>>1)=0/** 新的长度newCapacity依然无法满足需要的最小扩容量minCapacity，则新的扩容长度为minCapacity */if (newCapacity - minCapacity < 0) // eg1：truenewCapacity = minCapacity; // eg1：newCapacity=10/** 新的扩容长度newCapacity超出了最大的数组长度MAX_ARRAY_SIZE（huge：巨大的） */if (newCapacity - MAX_ARRAY_SIZE > 0)newCapacity = hugeCapacity(minCapacity);/** 扩展数组长度为newCapacity，并且将旧数组中的元素赋值到新的数组中 */elementData = Arrays.copyOf(elementData, newCapacity); // eg1：newCapacity=10， 扩容elementData的length=10}private static int hugeCapacity(int minCapacity) {if (minCapacity < 0) { // overflowthrow new OutOfMemoryError();}return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;}

正常情况下会扩容1.5倍，特殊情况下（新扩展数组大小已经达到了最大值）则只取最大值。当我们调用add方法时，实际上的函数调用如下：

重点总结　

1）arrayList可以存放null。
2）arrayList本质上就是一个elementData数组。
3）arrayList区别于数组的地方在于能够自动扩展大小，其中关键的方法就是gorw()方法。
4）arrayList中removeAll(collection c)和clear()的区别就是removeAll可以删除批量指定的元素，而clear是全是删除集合中的元素。
5）arrayList由于本质是数组，所以它在数据的查询方面会很快，而在插入删除这些方面，性能下降很多，有移动很多数据才能达到应有的效果
6）arrayList实现了RandomAccess，所以在遍历它的时候推荐使用for循环。

部分参考：ArrayList源码解析-CSDN博客　　　　　