ArrayList代码分析
2024-09-02 21:44:59
集合算是java中最常用的部分了,阅读该部分jdk代码可以让我们更加清楚的了解其实现原理,在使用时也能心中有数,有利于写出高质量的代码。
ArrayList
底层数组实现,初始长度10,超过长度后的自增实际是数组拷贝,拷贝用的System.copy()调用了本地方法,效率相对较高。
先看new ArrayList()
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
可见,开始new ArrayList()的时候,数组长度其实是0,并不是10,是个空数组。
通过add(E e)方法进行查看:
public boolean add(E e) {
ensureCapacityInternal(size + 1); // 确认容量,看下一个位置是不是没了
elementData[size++] = e; // 容量允许的话,放在当前元素的下一个位置
return true;
}
确认容量的方法:
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { // 如果当前数组为空
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); // 数组容量取 默认容量跟给定数据的较大者
}
ensureExplicitCapacity(minCapacity); // 确定明确的容量数值
}
这里要了解的是两个变量的初始值:
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData;
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
可以看到,elementData这个初始值是个null,但ArrayList创建的时候进行了赋值,因此这里有这个(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)判断。
确定明确数值的方法:
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;
int newCapacity = oldCapacity + (oldCapacity >> 1); // 新长度为原来的+原来的一半(初始10,变为15)
if (newCapacity - minCapacity < 0) // 加一半后长度还是不够,则用传递过来的数值(addAll来说,就是原长度+新集合长度)
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);
}
---------------------------------
解释:
按代码分析,新增一个元素,调用add方法,如果长度没超出,那么就在数组下个位置放置该元素,如果超出了,按照当前长度的一半增长(其实不是严格一半,比如长度是15的时候,下次增长长度为15(1111)右移一位为111=7)。新增的如果是一个集合,则根据原数组长度跟新集合的长度得出需要的最小容量,在grew方法中如果当前长度增长一半超过了计算出的容量,则用增长一半的长度,否则用计算的容量;而且,如果新容量到了十亿级别,则进行最大容量判断是否增长为Integer.MAX_VALUE。
这里有个内置的变量,private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;为什么-8呢,注释写的很清楚:
/**
* The maximum size of array to allocate.
* Some VMs reserve some header words in an array.
* Attempts to allocate larger arrays may result in
* OutOfMemoryError: Requested array size exceeds VM limit
*/
就是说有些虚拟机会预留出一定长度作为数组的一些头信息,所以数组最大长度达不到Integer的最大值2~32-1 = 2147483647(21亿..)左右,这个-8是为了避免内存溢出。
-------------------------------------------------------
一些其它的内容:
modCount只记录arraylist被修改次数,在每次添加修改删除的时候进行+1,参数名称也是modifyCount修改计数的意思;这个参数的作业就是在多线程并发的时候,由于arraylist不是线程安全的,在当前线程进行遍历等操作的时候,如果其它线程修改了程序,那么当前线程能检测到该参数发生变化,会报异常。
最新文章
- Neural Pathways of Interaction Mediating the Central Control of Autonomic Bodily State 自主神经系统-大脑调节神经通路
- C语言字符串拷贝
- (转)Xcode调试技巧
- uva 11134 fabled rooks (贪心)——yhx
- jsp 页面 性别回显
- Win2012 R2 IIS8.5+PHP(FastCGI)+MySQL运行环境搭建教程
- ThinkPhp3.2 无法加载模块:Index
- [Boost基础]并发编程——asio网络库——同步socket处理
- 深入浅出java并发
- R语言数据分析系列六
- javascript执行原理
- Rotational Region CNN
- Temple Build~dp(01背包的变形)
- JMX的l理解
- Forth-83 多任务解析
- robot framework关键词记录单(更新中)
- 网络协议抓包分析——ARP地址解析协议
- Lucene实战之基于StandardAnalyzer读写索引
- maven 排除test测试类
- JVM——垃圾回收(GC)