当前位置:网站首页>ArrayList扩容详解
ArrayList扩容详解
2022-07-01 17:47:00 【全栈程序员站长】
大家好,又见面了,我是你们的朋友全栈君。
本文探讨一下ArrayList的扩容过程
ArrayList底层是数组elementData,用于存放插入的数据。初始大小是0,当有数据插入时,默认大小DEFAULT_CAPACITY = 10。如果在创建ArrayList时指定了initialCapacity,则初始大小是ArrayList
1. 验证扩容的代码示例
从示例中可以看到,当添加元素时,如果元素个数+1> 当前数组长度 【size + 1 > elementData.length】时,进行扩容,扩容后的数组大小是: oldCapacity + (oldCapacity >> 1)
将旧数组内容通过Array.copyOf全部复制到新数组,此时新旧列表的size大小相同,但elementData的长度即容量不同
注意:扩容并不是严格的1.5倍,是扩容前的数组长度右移一位 + 扩容前的数组长度
public class SimpleTest {
public static void main(String[] args) {
ArrayList list = new ArrayList();
int size = 0;
for (int i = 0; i < 100; i++) {
list.add(i);
if(getCapacity(list)>size) {
System.out.println("capacity:"+getCapacity(list) + ",size:"+list.size());
size = getCapacity(list);
}
}
}
public static Integer getCapacity(ArrayList list) {
Integer length = null;
Class clazz = list.getClass();
Field field;
try {
field = clazz.getDeclaredField("elementData");
field.setAccessible(true);
Object[] object = (Object[]) field.get(list);
length = object.length;
return length;
} catch (Exception e) {
e.printStackTrace();
}
return length;
}
}
运行结果如下:
capacity:10,size:1 capacity:15,size:11 capacity:22,size:16 capacity:33,size:23 capacity:49,size:34 capacity:73,size:50 capacity:109,size:74
2. 扩容相关的源代码
public boolean add(E e) {
//调用了一ensureCapacityInternal方法,确保数组下标不越界
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//新容量扩大到原容量的大约1.5倍,右移一位相当于原数值除以2,扩容并不是严格的1.5位
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
3. 为什么按大约1.5倍扩容
扩容因子的大小选择,需要考虑如下情况:
- 扩容容量不能太小,防止频繁扩容,频繁申请内存空间 + 数组频繁复制
- 扩容容量不能太大,需要充分利用空间,避免浪费过多空间;
为了能充分使用之前分配的内存空间,最好把增长因子设为 1<k<2.
k=1.5时,就能充分利用前面已经释放的空间。如果k >= 2,新容量刚刚好永远大于过去所有废弃的数组容量
并且充分利用移位操作(右移一位),减少浮点数或者运算时间和运算次数
详见参见: C++ STL 中 vector 内存用尽后, 为什么每次是 2 倍的增长, 而不是 3 倍或其他值?
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/130890.html原文链接:https://javaforall.cn
边栏推荐
- Reflective XSS vulnerability
- Iommu/smmuv3 code analysis (10) page table operation
- 剑指 Offer 20. 表示数值的字符串
- (十六)ADC转换实验
- Object. fromEntries()
- Yyds dry inventory MySQL RC transaction isolation level implementation
- Key points on February 15, 2022
- 中国氮化硅陶瓷基板行业研究与投资前景报告(2022版)
- 网上股票开户安全吗?是否可靠?
- The reviewboard has 500 errors when submitting a review. Solutions
猜你喜欢
(十七)DAC转换实验
Cassette helicopter and alternating electric field magnetic manometer DPC
From comedians to NBA Zhan Huang, check the encrypted advertisements during this super bowl
剑指 Offer 20. 表示数值的字符串
[splishsplash] about how to receive / display user parameters, MVC mode and genparam on GUI and JSON
荣威 RX5 的「多一点」产品策略
Common design parameters of solid rocket motor
(1) CNN network structure
June issue | antdb database participated in the preparation of the "Database Development Research Report" and appeared on the list of information technology and entrepreneurship industries
Mysql database - Advanced SQL statement (2)
随机推荐
Technical secrets of ByteDance data platform: implementation and optimization of complex query based on Clickhouse
Penetration practice vulnhub range Keyring
中国酶制剂市场预测与投资战略研究报告(2022版)
(17) DAC conversion experiment
为什么你要考虑使用Prisma
Glidefast consulting was selected as the elite partner of servicenow in 2022
DNS
期货先锋这个软件正规吗安全吗?选择哪家期货公司更安全?
Research Report on China's enzyme Market Forecast and investment strategy (2022 Edition)
官宣!香港科技大学(广州)获批!
Cookies and session keeping technology
Is the software of futures pioneer formal and safe? Which futures company is safer to choose?
[C supplement] [string] display the schedule of a month by date
Rotation order and universal lock of unity panel
多线程使用不当导致的 OOM
Key points on February 15, 2022
剑指 Offer 20. 表示数值的字符串
Software construction scheme of smart factory collaborative management and control application system
Official announcement! Hong Kong University of science and Technology (Guangzhou) approved!
中国冰淇淋市场深度评估及发展趋势预测报告(2022版)