Java ArrayList源码深入分析
作者:niuyongzhi 发布时间:2023-06-16 16:30:26
标签:Java,ArrayList,源码
1.ArrayList 是基数组结构的,需要连续的内存空间
从构造函数可以看出,ArrayList内部用一个Object数组来保存数据。
对于无参构造,ArrayList会创建一个大小为10的初始数组,第一次扩容时会创建默认大小数组。
//无参构造函数,会构造一个空数组。第一次扩容时会创默认大小为10的数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData;
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
private static final Object[] EMPTY_ELEMENTDATA = {};
//如果给定集合大小,会创建一个对应大小的数组
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);
}
}
2.对于set和get方法ArrayList效率高,因为可以直接通过下标获取存储对象。
//直接通过角标从数组中取出元素
public E get(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
return (E) elementData[index];
}
//set 方法,直接通过index 拿到元素,进行修改就行。
public E set(int index, E element) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
E oldValue = (E) elementData[index];
elementData[index] = element;
return oldValue;
}
3.对于add方法,有两种情况:
第一种是在尾部添加,不需要移动数组。
//Add 方法 ,在末端插入不需要
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
第二种情况在指定位置添加或插入数据,则需要移动数组,效率比较低。如果插入在第0个位置则需要移动整个数组。
public void add(int index, E element) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
ensureCapacityInternal(size + 1); // Increments modCount!!
// * 入的元素在index。则移动的数组应该从index开始,向后移动一个,
//移动的数组长度 size-index 从index开始的数组长度
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
在add时还需要考虑到数组的扩容问题,看ensureCapacityInternal方法
private void ensureCapacityInternal(int minCapacity) {
//通过无参构造创建为设置初始大小时,判断条件为true
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
//创建默认大小的数组,初始大小是10
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
添加元素后,元素数量大于数组长度时,进行扩容grow,扩容大小是原数组的1.5倍
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倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//创建一个新长度的数组。
elementData = Arrays.copyOf(elementData, newCapacity);
}
4.对应remove 删除元素操作。如果删除元素在最后一个,不需要移动数组,否则会将被删除元素之后的所有元素都要向前移动,效率比较低。
//删除
public E remove(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
modCount++;
//取出被删除的元素
E oldValue = (E) elementData[index];
int numMoved = size - index - 1;
//移动的数组长度,大于0才需要移动,小于0说明被删元素在最后一个
if (numMoved > 0)
//第一个参数是源数组,
//第二个参数是移动的起始位置:index+1,从被删元素的后一个位置开始
//第三个参数是目标数组
//第四个参数是移动目标位置:index,被删除元素的位置
//第五个参数是移动的数组长度 size - index - 1,从index+1位置开始之后的数组长度
//最终会调用到native方法进行移动。
System.arraycopy(elementData, index+1, elementData, index,numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
5.System.arraycopy方法参数分析。
第二个参数 index+1是被移动数组的起始位置,即被删元素后一个位置
第四个参数index,是被移动数组的起始位置,即被删元素的位置。
最后一个参数size-index-1,被移动数组的长度,即被删元素后一个位置到元素末尾的长度
public static native void arraycopy(java.lang.Object src, int srcPos, java.lang.Object dest, int destPos, int length);
通过对源码的阅读,也许会对ArrayList有一个更加直接的了解。
来源:https://blog.csdn.net/niuyongzhi/article/details/125814050
0
投稿
猜你喜欢
- idea激活码破解教程亲测试以下版本成功激活附激活教程。idea下载链接(对应版本号下载):https://www.jetbrains.co
- 无论哪种界面框架输入文本框都是非常重要的控件, 但是发现flutter中的输入框TextField介绍的虽然多,但是各个属性怎么组合满足需要
- 背景最近好几个项目在运行过程中客户都提出文件上传大小的限制能否设置的大一些,用户经常需要上传好几个G的资料文件,如图纸,视频等,并且需要在上
- 本文实例讲述了java实现的简单猜数字游戏代码。分享给大家供大家参考。具体代码如下:import java.util.InputMismat
- 本文实例为大家分享了C# GDI+实现时钟表盘的具体代码,供大家参考,具体内容如下一、设计如下图界面按键“打开时钟&am
- 需求: 给定一个URL地址, 例如: http://www.cncounter.com/tools/shorturl.php, 解析对应的I
- 前言之前我们提到了 CustomPaint er 的 Paint 可以使用渐变(GradientShader)来填充绘制的图形,本篇我们来介
- 1.map遍历快速实现边距,文字自适应改变大小Container( // padding: EdgeI
- 本文实例讲述了Java实现接口的枚举类。分享给大家供大家参考,具体如下:一 点睛枚举类也可以实现一个或多个接口。与普通类实现一个或多个接口完
- 因为mybatis好使,所以几乎需要操作数据库的时候,我都会使用mybatis,而且在一个正式的项目中,同时存在BS和CS的程序,都使用的M
- [LeetCode] 2. Add Two Numbers 两个数字相加You are given two non-empty&n
- 引语:工作中有时候需要在普通的对象中去调用spring管理的对象,但是在普通的java对象直接使用@Autowired或者@Resource
- 目录前言使用自写代码预览完整代码使用第三个插件编码结论前言本文将带您了解在 Flutter 中制作翻转卡片动画的两个完整示例。第一个示例从头
- 前言最近看插件库上少有的取色器大都是圆形的或者奇奇怪的的亚子,所以今天做两个矩形的颜色取色器提示:以下是本篇文章正文内容,下面案例可供参考一
- 背景大家在使用Selenium + Chromedriver爬取网站信息的时候,以为这样就能做到不被网站的反爬虫机制发现。但是实际上很多参数
- forward_list 概述forward_list 是 C++ 11 新增的容器,它的实现为单链表。forward_list 是支持从容
- 本文实例讲述了C++语言实现线性表之链表实现方法。分享给大家供大家参考。具体分析如下:插入、删除结点的代码有点多,但这样提高了代码的可读性,
- 在windows环境下,我们通常在IDE如VS的工程中开发C++项目,对于生成和使用静态库(*.lib)与动态库(*.dll)可能都已经比较
- 一、写在前面 数据结构中的队列应该是比较熟悉的
- 一、百度百科Sentinel 是面向分布式服务架构的高可用流量防护组件,主要以流量为切入点,从限流、流量整形、熔断降级、系统负载保护、热点防