Java(List接口)集合ArrayList源码分析
2021/12/15 14:20:52
本文主要是介绍Java(List接口)集合ArrayList源码分析,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
Java(List接口)集合ArrayList源码分析
概述
ArrayList本质上就是一个动态数组,所以通过下标访问的效率高,但是在增删操作时,需要消耗的性能较大。
类关系结构图
相关的接口抽象类的介绍
类名 | 说明 |
---|---|
AbstractCollection | 实现了Collection中大量的函数,除了特定的几个函数iterator()和size()之外的函数 |
AbstractList | 该接口继承于AbstractCollection,并且实现List接口的抽象类。 它实现了List中除size()、get(int location)之外的函数。 AbstractList的主要作用:它实现了List接口中的大部分函数 和AbstractCollection相比,AbstractList抽象类中,实现了iterator()接口 |
RandomAccess | RandmoAccess接口,即提供了随机访问功能。RandmoAccess是java中用来被List实现,为List提供快速访问功能的。在ArrayList中,我们即可以通过元素的序号快速获取元素对象;这就是快速随机访问 |
List | 有序队列接口,提供了一些通过下标访问元素的函数 List是有序的队列,List中的每一个元素都有一个索引;第一个元素的索引值是0,往后的元素的索引值依次+1 |
关键字段
/** * Default initial capacity. * 默认的数组的长度 */ private static final int DEFAULT_CAPACITY = 10; /** * Shared empty array instance used for empty instances. * 空数组 */ private static final Object[] EMPTY_ELEMENTDATA = {}; /** * Shared empty array instance used for default sized empty instances. We * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when * first element is added. */ private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; /** * The array buffer into which the elements of the ArrayList are stored. * The capacity of the ArrayList is the length of this array buffer. Any * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA * will be expanded to DEFAULT_CAPACITY when the first element is added. * 集合中存储数据的 数组对象 */ transient Object[] elementData; // non-private to simplify nested class access /** * The size of the ArrayList (the number of elements it contains). * 集合中元素的个数 * @serial */ private int size;
初始操作
无参构造
elementData=null;无参构造去并不会真实的创建数组,数组会在add方法中去创建,有助于性能的提升,懒加载的方式。
public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; // this.elementData = {} }
有参构造
public ArrayList(int initialCapacity) { if (initialCapacity > 0) { // 初始长度大于0 就创建一个指定大小的数组 this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { // {}数组赋值给 this.elementData this.elementData = EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); } }
add 方法
第一次添加
/** * 将元素添加到集合的尾部 * * @param e element to be appended to this list * @return <tt>true</tt> (as specified by {@link Collection#add}) */ public boolean add(E e) { // 确定容量 动态扩容 size 初始 0 ensureCapacityInternal(size + 1); // Increments modCount!! // 将要添加的元素 添加到数组中 elementData[0] = 1 --> size = 1 elementData[size++] = e; return true; }
private void ensureCapacityInternal(int minCapacity) { // ensureExplicitCapacity(10) ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); }
/** * elementData {} minCapacity 1 */ private static int calculateCapacity(Object[] elementData, int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { // 10 1 return 10 return Math.max(DEFAULT_CAPACITY, minCapacity); } // 5 return minCapacity; }
private void ensureExplicitCapacity(int minCapacity) { modCount++; // 增长 操作次数 // minCapacity 10 if (minCapacity - elementData.length > 0) grow(minCapacity); }
private void grow(int minCapacity) { // 10 // 记录原来的容量 int oldCapacity = elementData.length; // 0 // newCapacity = 0 // 计算新的容量 新容量为老容量的1.5倍,第一次为0 int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity < 0) // newCapacity = 10 newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // {} {,,,,,,,,,} 返回一个新的数组 长度为10 // 把原来的数组中的内容拷贝到一个新建的指定容量为newCapacity的数组中,扩容 elementData = Arrays.copyOf(elementData, newCapacity); }
第二次添加
elementData = {1,,,,,,,,,}; size = 1;
public boolean add(E e) { // 2 ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; // elementData[1] = 2 size = 2 return true; }
private static int calculateCapacity(Object[] elementData, int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { return Math.max(DEFAULT_CAPACITY, minCapacity); } // 2 return minCapacity; }
private void ensureExplicitCapacity(int minCapacity) { modCount++; // overflow-conscious code 2 - 10 if (minCapacity - elementData.length > 0) grow(minCapacity); }
第十一次添加
elementData = {1,2,3,4,5,6,7,8,9,10}; size = 10;
public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; }
private void ensureCapacityInternal(int minCapacity) { // ensureExplicitCapacity(11) ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); }
private void ensureExplicitCapacity(int minCapacity) { modCount++; // 11 - 10 > 0 if (minCapacity - elementData.length > 0) grow(minCapacity); }
private void grow(int minCapacity) { // 11 // 10 int oldCapacity = elementData.length; // 15 newCapacity 是oldCapacity的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: // {1,2,3,4,5,6,7,8,9,10} -- > {1,2,3,4,5,6,7,8,9,10,,,,,} elementData = Arrays.copyOf(elementData, newCapacity); }
get方法
public E get(int index) { // 检查下标是否合法 rangeCheck(index); // 通过下标获取数组对应的元素 return elementData(index); }
set方法
public E set(int index, E element) { rangeCheck(index); // 检查下标 // 获取下标原来的值 E oldValue = elementData(index); elementData[index] = element; return oldValue; }
remove方法
public E remove(int index) { // 检查下标 rangeCheck(index); modCount++; E oldValue = elementData(index); // 获取要移动的元素的个数 {1,2,3,4,5,6,7,8,9} // 3 size=9 index=3 // {1,2,3,5,6,7,8,9,null} int numMoved = size - index - 1; // 5 if (numMoved > 0) // 源数组 开始下标 目标数组 开始下标 长度 System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size] = null; // clear to let GC do its work // 删除的节点对应的信息 return oldValue; }
FailFast机制
快速失败机制,也就是在多线程操作一个List数据的时候如果出现数据安全问题会直接抛异常(java.util.ConcurrentModificationException)。
这篇关于Java(List接口)集合ArrayList源码分析的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-03万字长文聊聊Web3的组成架构
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?