深入挖掘 ArrayList工作原理及其实现
文章目录
📌ArrayList工作原理及其实现
特点、需要通过源码底层实现查看实现逻辑。
📚1.ArrayList集合使用
✒️1.1 ArrayList集合的简单使用
通过new一个ArrayList集合的对象，调用其添加、删除方法初步认识ArrayList集合。
import java.util.ArrayList;
public class TestDemo {
public static void main(String[] args) {
ArrayList<Integer> list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
list.add(null);
for (Integer i : list) {
System.out.print(i + " ");
}
System.out.println();
//删除集合中下标为1的元素
list.remove(1);
System.out.println("==删除第二个元素后==");
for (Integer i : list) {
System.out.print(i + " ");
}
}
运行结果：
🖋️1.2 ArrayList集合特点
1、ArrayList可以存放重复数据
2、ArrayList中元素存放和插入顺序一致。
3、ArrayList中存放的数据可以为null
4、ArrayList集合底层采用的是数组来存储数据
🖊️1.3 ArrayList集合构造函数
//无参构造
ArrayList <Integer> list = new ArrayList <>();
//通过指定集合容量大小来实例化
ArrayList <Integer> list1 = new ArrayList <>(100);
//通过Collection集合实例来实例化一个新集合
ArrayList <Integer> list2 = new ArrayList <>(list);
📕2.通过JDK源码来研究ArrayList的实现
1、关注继承关系
2、属性和默认值
3、构造函数
4、扩容机制、扩容时机
5、底层数据结构（数组、链表、队列、栈、哈希表…）
6、常见方法实现原理（add、get、remove）
📭2.1 继承关系
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
类结构图
①ArrayList继承自AbstractList，AbstractList是抽象类，实现了List接口，它是一个数组队列，提供了相关的添加、修改、删除、遍历等基本功能实现，方法子类对方法复用，如果子类有特有功能可以重写父类的方法。
②ArrayList实现了List接口，List接口继承自Collection接口，在Collection接口提供的方法基础上，有一些新的方法提供，比如get、set、add等特有方法。
③ArrayList实现了RandomAccess接口，即提供了随机访问功能。
④ArrayList实现了Cloneable接口，即包含了函数clone()，能被克隆。
⑤ArrayList实现了Serializable接口，意味着ArrayList支持序列化，能通过序列化去传输（IO）。
📬2.2 属性和默认值
//默认的初始容量10
private static final int DEFAULT_CAPACITY = 10;
//空数组实例
private static final Object[] EMPTY_ELEMENTDATA = {};
//存储数据：使用的是数组，数组存储的数据类型是Object
private transient Object[] elementData;
//用来记录存放数据的个数
private int size;
ArrayList底层存储元素是使用数组，类型为Object类型。数组中:elementData.length:表示的是当前数组容量，最大存储的数据个数； size：实际存放的数据个数，即数组中有效数据个数。
📪2.3 构造函数
//有参构造函数：通过指定初始容量initialCapacity来实例化ArrayList
public ArrayList(int initialCapacity) {
super();
//参数合法性校验
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);
//实例化一个大小为initialCapacity数组并将数组赋值给elementData
this.elementData = new Object[initialCapacity];
}
//无参构造函数 elementData赋值为空数组
public ArrayList() {
// ArrayList(DEFAULT_CAPACITY);
super();
this.elementData = EMPTY_ELEMENTDATA;
//将默认值的赋值在add中完成
}
//通过集合来实例化ArrayList
public ArrayList(Collection<? extends E> c) {
//将集合转化为数组，直接赋值给elementData
elementData = c.toArray();
//将集合中已有元素的大小赋值给size(有效数据个数)
size = elementData.length;
// c.toArray might (incorrectly) not return Object[] (see 6260652)
//如果elementData类型不是Object类型，将其强转为Object类型
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
}
📫2.4 常见方法原码解析
📃2.4.1 add：添加元素
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
1、 ensureCapacityInternal(size + 1); 检查数组容量是否够
private void ensureCapacityInternal(int minCapacity) {
if (elementData == EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
2 、 如果当前数组是空数组，那么就会初始化数组容量大小为 10 (添加第一个元素，集合是通过无参构造实例的时候)
3、 如果当前数组不是空数组，那么执行ensureExplicitCapacity(minCapacity);
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
1)modcount++: modCount属性是版本控制器，和业务无关，仅仅是做版本控制，在集合进行变更时（修改、删除、添加）会自增1
- 如果size+1 大于 数组的长度 那么进行 扩容 操作 grow(minCapacity);
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
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);
}
- 扩容机制
①拿到数组的长度，把长度扩大到原来的1.5 倍，得到新的数组长度newCapacity
oldCapcity >> 1 效率 比 oldCapcity / 2 高
②如果新的数组长度小于size+1的长度 大于 新的数组长度，更新新的数组长度为size + 1，如果新的数组长度比最大值MAX_ARRAY_SIZE还要大，进入hugeCapacity() 方法来比较 minCapacity 和 MAX_ARRAY_SIZE，如果minCapacity大于最大容量，则新容量则为Integer.MAX_VALUE，否则，新容量大小则为 MAX_ARRAY_SIZE 即为 Integer.MAX_VALUE - 8
③调用Arrays.copyOf()函数将原有的集合数据拷贝到新容量为newCapacity的数组中
📄2.4.2 remove：删除元素
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
1、 如果删除对象是null ，遍历数组，找到null的元素，调用fastRemove() 方法
2、 如果删除对象不是null，遍历数组，找到对应的元素，调用fastRemove() 方法
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
}
3、fastRemove方法
删除对应的元素后，需要将后面的元素一一往前移动一位。先统计需要移动的元素个数（删除元素后的元素个数），调用System.arraycopy()方法进行元素拷贝移动，最后将数组中最后一个元素置为null，有效元素个数-1。
📑2.4.3 get：获取元素
public E get(int index) {
//检查查询位置的合法性 index <size
rangeCheck(index);
return elementData(index);
}
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
E elementData(int index) {
return (E) elementData[index];
}
相关文章
- session 和 flask_session 实现原理(源码解析)
- k8s pod实现共享网络和共享存储机制原理及pod内容器共享存储代码示例
- bInitiallyDisabled实现原理
- Angular 依赖注入机制实现原理的深入介绍
- 深入学习SAP UI5框架代码系列之七：控件数据绑定的三种模式 - One Way, Two Way和OneTime实现原理比较
- Angular 依赖注入机制实现原理的深入介绍
- Hibernate的ORM原理和实现
- atitit.文件上传带进度条的实现原理and组件选型and最佳实践总结O7
- PostgreSQL的学习心得和知识总结（一百零五）|详解PostgreSQL数据库 Add ON CONFLICT DO RETURN clause 实现原理说明
- PostgreSQL的学习心得和知识总结（一百零四）|深入理解PostgreSQL数据库开源MPP扩展Citus 分布表间连接规则的生成以及最佳规则选取 的实现原理
- PostgreSQL的学习心得和知识总结（一百零二）|深入理解PostgreSQL数据库开源MPP扩展Citus 分布表间Inner Join数据重分布 的实现原理
- PostgreSQL的学习心得和知识总结（一百零一）|深入理解PostgreSQL数据库开源MPP扩展Citus 分布表和本地表Join 的实现原理
- PostgreSQL的学习心得和知识总结（八十九）|深入理解PostgreSQL数据库开源MPP扩展Citus再平衡函数rebalance_table_shards的实现原理
- Retrofit工作原理总结
- 四叉树空间索引原理及其实现
- C++ 反汇编：分析类的实现原理
- 【java】Spring Boot -- Spring AOP原理及简单实现
- Mybatis源码分析之（六）mybatis拦截器（Interceptor）的实现原理