无锡网站制作优化推广公司,网站建设财务处理,windows搭建wordpress博客,最新公司名字大全文章目录 简介ArrayList底层数据结构初始化集合操作追加元素插入数据删除数据修改数据查找 扩容操作总结 简介
ArrayList是Java提供的线性集合#xff0c;本篇笔记将从源码(java SE 17)的角度学习ArrayList#xff1a;
什么是ArrayList#xff1f;ArrayList底层数据结构是… 文章目录 简介ArrayList底层数据结构初始化集合操作追加元素插入数据删除数据修改数据查找 扩容操作总结 简介
ArrayList是Java提供的线性集合本篇笔记将从源码(java SE 17)的角度学习ArrayList
什么是ArrayListArrayList底层数据结构是怎么实现的作为一个容器分析增删改查的过程ArrayList的扩容机制
ArrayList底层数据结构
public class ArrayListE extends AbstractListEimplements ListE, RandomAccess, Cloneable, java.io.Serializable
{java.io.Serialprivate static final long serialVersionUID 8683452581122892189L;/*** 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;...}
由ArrayList的定义可知ArrayList继承了AbstractList抽象类实现了List、RandomAccess、Cloneable、Serializable接口
通过这一行
/*** 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
这就是ArrayList维护的底层数据结构用于存放元素是一个Object数组。还注意到使用了一个关键字transient 该关键字是在对ArrayList进行序列化时禁止对该字段进行序列化。该字段是默认访问权限
初始化 /*** Constructs an empty list with the specified initial capacity.** param initialCapacity the initial capacity of the list* throws IllegalArgumentException if the specified initial capacity* is negative*/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);}}/*** Constructs an empty list with an initial capacity of ten.*/public ArrayList() {this.elementData DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}/*** Constructs a list containing the elements of the specified* collection, in the order they are returned by the collections* iterator.** param c the collection whose elements are to be placed into this list* throws NullPointerException if the specified collection is null*/public ArrayList(Collection? extends E c) {Object[] a c.toArray();if ((size a.length) ! 0) {if (c.getClass() ArrayList.class) {elementData a;} else {elementData Arrays.copyOf(a, size, Object[].class);}} else {// replace with empty array.elementData EMPTY_ELEMENTDATA;}}
ArrayList提供了三个构造器
空的构造器
public ArrayList() {this.elementData DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}使用该构造器创建一个ArrayList时统一使用默认的空的一个数组来初始化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);}
}当使用一个整型变量初始化ArrayList时根据initialCapacity的大小- 小于0会抛出非法参数异常
- 等于0使用内部维护的EMPTY_ELEMENTDATA来创建
- 大于0此时创建一个指定大小的Object数组通过Collection来创建主要用于从其他类型的集合创建ArrayList
集合操作
ArrayList源码中提供了一堆add函数但是可以将添加元素的操作分为两类
追加元素插入元素
追加元素
在末尾追加数据调用的都是同一个方法 private void add(E e, Object[] elementData, int s) {if (s elementData.length)elementData grow();elementData[s] e;size s 1;}这里的elementData.length其实就是当前数组的容量s这里传入的是size也就是当前数组中实际元素的个数首先会判断是否需要扩容,然后将数据追加到数组末尾。
插入数据 public void add(int index, E element) {rangeCheckForAdd(index);modCount;final int s;Object[] elementData;if ((s size) (elementData this.elementData).length)elementData grow();System.arraycopy(elementData, index,elementData, index 1,s - index);elementData[index] element;size s 1;}这里的操作也比较常规就是将数组index后面的元素向后面一次迁移然后将index的位置设置为指定元素
删除数据 public E remove(int index) {Objects.checkIndex(index, size);final Object[] es elementData;SuppressWarnings(unchecked) E oldValue (E) es[index];fastRemove(es, index);return oldValue;}private void fastRemove(Object[] es, int i) {modCount;final int newSize;if ((newSize size - 1) i)System.arraycopy(es, i 1, es, i, newSize - i);es[size newSize] null;}逻辑也很简单没啥说的就是使用后面的数据覆盖掉index位置的数据
修改数据 public E set(int index, E element) {Objects.checkIndex(index, size);E oldValue elementData(index);elementData[index] element;return oldValue;}没什么说的
查找
E elementData(int index) {return (E) elementData[index];
}public E get(int index) {Objects.checkIndex(index, size);return elementData(index);
}扩容操作
从上面有些方法的API中看到如果向集合中添加元素时此时会检查ArrayList的容量如果容量不足会引发扩容主要调用grow方法 private Object[] grow() {return grow(size 1);}private Object[] grow(int minCapacity) {int oldCapacity elementData.length;if (oldCapacity 0 || elementData ! DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {int newCapacity ArraysSupport.newLength(oldCapacity,minCapacity - oldCapacity, /* minimum growth */oldCapacity 1 /* preferred growth */);return elementData Arrays.copyOf(elementData, newCapacity);} else {return elementData new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];}}这里的preferred growth(参考增量)是原数组大小的一半minGrowth是最小增量。
扩容可以分为四种情况 如果原数组长度为0或者为默认的空数组对象 其实就是第一次向一个空的ArrayList添加元素此时返回一个默认容量的数组, 默认容量为 10 如果根据计算得到的参考分配长度小于等于SOFT_MAX_ARRAY_LENGTH ,就返回该参考长度(这里我看网上很多文章说是扩容1.5倍这其实是当最小增量小于原长度的一半时才发生的所以并不准确或者通过for循环依次追加时会发生但是当批量添加时并不一定是1.5倍) public static int newLength(int oldLength, int minGrowth, int prefGrowth) {// preconditions not checked because of inlining// assert oldLength 0// assert minGrowth 0int prefLength oldLength Math.max(minGrowth, prefGrowth); // might overflowif (0 prefLength prefLength SOFT_MAX_ARRAY_LENGTH) {return prefLength;} else {// put code cold in a separate methodreturn hugeLength(oldLength, minGrowth);}}如果参考长度(prefLength)大于SOFT_MAX_ARRAY_LENGTH , 如果实际需要的容量小于SOFT_MAX_ARRAY_LENGTH就分配SOFT_MAX_ARRAY_LENGTH private static int hugeLength(int oldLength, int minGrowth) {int minLength oldLength minGrowth;if (minLength 0) { // overflowthrow new OutOfMemoryError(Required array length oldLength minGrowth is too large);} else if (minLength SOFT_MAX_ARRAY_LENGTH) {return SOFT_MAX_ARRAY_LENGTH;} else {return minLength;}}实际需要的长度大于SOFT_MAX_ARRAY_LENGTH要多少给多少
总结
通过简单分析ArrayList的源码学习了Java中ArrayList的一些通用操作增删改查以及扩容当然翻看源码还可以发现ArrayList还提供了很多批量操作的API其逻辑也不复杂。
ArrayList内部包含了一个实现了Iterator接口的内部类用于遍历操作但是Java的集合框架中迭代器是一个通用的操作接口后面再独立拿出来进行分析。
ArrayList中扩容操作涉及到内存的分配和数据迁移操作如果程序频繁发生扩容将会降低程序的性能此时可以考虑提前预估ArrayList的大小提前进行内存分配减少内存重分配发生的次数。
ArrayList的查找和插入操作的平均时间复杂度是O(N), 如果在频繁插入和查找的场景可以尝试使用更高效的数据结构来代替。
