ArrayList的扩容机制

news/2024/4/25 17:15:32/文章来源:https://blog.csdn.net/weixin_55697693/article/details/130380200

前置知识

ArrayList的底层实现是一个Object[]，而LinkedList的底层实现是一个链表
ArrayList与LinkedList相对比：

ArrayList在随机访问时可以做到O(1)，但是LinkedList的随机访问就是遍历链表，所以时间复杂度是O(N)
ArrayList在插入/删除元素时，需要移动额外的很多元素，但是LinkedList在插入/删除时无需移动其他元素，效率更高
如果数据需要频繁的插入/删除，那么建议使用LinkedList
如果数据较为稳定，希望高效的访问元素，建议使用ArrayList

利用反射获取ArrayList容量

由于ArrayList中并没有提供获取底层数组的方法，如何利用反射来获取ArrayList的真实容量

public static int getCapatity(ArrayList list) {  int len = 0;  try {  // 获取Class对象  Class<?> clazz = Class.forName("java.util.ArrayList");  // 获取类属性  Field field = clazz.getDeclaredField("elementData");  // 暴力打开权限  field.setAccessible(true);  Object[] objList = (Object[]) field.get(list);  // 返回数组长度  len = objList.length;  } catch (ClassNotFoundException | NoSuchFieldException | IllegalAccessException e) {  e.printStackTrace();  }  // 返回数组长度  return len;  
}

ArrayList的扩容机制

首先，创建ArrayList的方式有哪些
ArrayList提供了三个构造方法来创建ArrayList

// 1. 无参构造
public ArrayList() // 2. 指定容量大小
public ArrayList(int initialCapacity) // 3. 指定元素来创建  
public ArrayList(Collection<? extends E> c)

无参构造

当调用无参构造来创建ArrayList时，看此无参构造方法的源码

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

其中elementData就是ArrayList实现的Object[ ]，在无参构造中，直接为数据赋了一个默认的空元素值，也就是此时的容量为0
当ArrayList的容量不足时，扩容的机制是：
当目前的容量是0时，第一次扩容后的容量为10，以后每次扩容后的容量都是原始容量的1.5倍！！！
但是此处的1.5倍并不是在算术意义上的size*1.5，因为计算机并不能真正处理浮点数
此处是1.5倍是位运算的右移1位，能够避免浮点数的问题
即：

扩容后的容量 = 原始容量 + 原始容量 >> 1

当容量不足时，会创建一个新的指定大小的新数组，将原始数组中的内容拷贝到新的数组中（旧的数组不被再引用，就会被垃圾回收掉）
分析以下代码来试试:

// 1. 通过无参构造创建,此时容量为0
ArrayList list = new ArrayList();
// 2. 向容器中添加元素
list.add(5);
// 此时容量不足，触发第一次扩容，此时容量为10// 3. 继续添加10个元素，添加后共有11个元素
for(int i = 1; i <= 10 ;i ++){list.add(i);
}
// 当要插入第11个元素时，检查发现此时容量不足，触发第二次扩容
// 扩容后的容量为 = 10 + 10 >> 1 = 15;// 4. 此时有11个元素，容量为15
// 继续添加
for(int i = 1;i <= 10 ; i ++){list.add(i);
}
// 当添加第16个元素时，发现容量又不足了，所以此时触发第三次扩容
// 新的容量 = 15 + 15 >> 1 = 22

有参构造指定容量大小

来看利用ArrayList的指定容量大小的源码：如果指定的容量大于0，就会创建指定容量大小的数组。如果指定的容量小于0，抛出异常。

public ArrayList(int initialCapacity) {  if (initialCapacity > 0) {  this.elementData = new Object[initialCapacity];  } else if (initialCapacity == 0) {  this.elementData = EMPTY_ELEMENTDATA;  } else {  throw new IllegalArgumentException("Illegal Capacity: "+  initialCapacity);  }  
}

当指定了ArrayList的初始容量后，以后每次的扩容就是 扩容后的容量 = 原始容量 + 原始容量 >> 1，如果初始容量为0，还是会第一次扩容为10

指定元素创建

直接传入一个集合，来创建包含指定元素的ArrayList

ArrayList list = new ArrayList(Arrays.asList(1,2,3));

此时会使用指定的元素大小作为起始容量，以后的扩容规则还是同上。

addAll()

add()方法是一次添加一个元素，当使用addAll()方法可以一次添加多个元素。
以上的扩容机制都是在add()方法触发的情况下，新的容量 = 原始容量 + 原始容量 >> 1
当addAll()触发扩容时，扩容机制是不一样的。
会在 默认下次扩容后的容量大小 与 当前所有的元素数量 之间选择一个较大值

ArrayList list = new ArrayList();
// 此时容量为0
list.add(Arrays.asList(1,2,3));
// 此时容量不足，触发扩容，
// 此时的元素数量是3，默认下次扩容后的容量是10
// 选择10 作为扩容后的容量

再来看一个例子

Array list = new ArrayList();
// 刚创建,此时容量为0
// 继续添加，容量不足,触发扩容
list.addAll(Arrays.asList(1,2,3,4,5,6,7,8,9,10,11));
// 默认下次扩容后的容量是10, 但是此时的元素数量是11，
// 所以扩容后的容量为11

再来看一个例子

ArrayList list = new ArrayList();
for(int i = 1;i <= 10 ;i ++){list.add(i);
}
// 此时容量为10，容量不足
list.addAll(Arrays.asList(1,2,3))
// 下次扩容后的容量为15，元素数量是13，
//  所以扩容后的容量是15