天津网站建设电话,企业网,WordPress 编辑器修改默认字号,阿里云网站备案资料Java中的ArrayList是一个动态数组#xff0c;可以自动扩展容量以适应数据的添加和删除。它可以用来存储各种类型的数据#xff0c;例如String#xff0c;Integer#xff0c;Boolean等。ArrayList实现了List接口#xff0c;可以进行常见的List操作#xff0c;例如添加、插…Java中的ArrayList是一个动态数组可以自动扩展容量以适应数据的添加和删除。它可以用来存储各种类型的数据例如StringIntegerBoolean等。ArrayList实现了List接口可以进行常见的List操作例如添加、插入、删除和访问元素等。 ArrayList具有以下特点
有序的 元素按照添加顺序排列。可重复的 同一元素可以重复出现在不同位置。可变的 可以动态调整数组大小。线程不安全 在多线程环境下需要进行额外的同步措施。查询效率快。这是由于底层的数据结构是基于Object 数组实现的且数组在内存中是一块连续的空间所以每次执行get方法获取元素时可以通过索引 地址的方式能够快速的在数组上的指定位置获取元素增删效率低。在执行add方法时可能存在 扩容 就需要生成一个新的数组然后将旧数组中的元素复制到新数组中最后将新增的元素放在数组上执行remove方法时将指定位置元素删除后后面所有元素向 左移 动一位因为增删需要对数组的结构进行调整所以效率低支持序列化: 实现 Serializable标记性接口。支持克隆功能: 实现 Cloneable 标记性接口。支持随机访问功能: 实现 RandomAccess 标记性接口。也就是通过下标获取元素对象的功能继承 Iterable 接口可以使用 for-each 迭代 源码分析JDK1.8 成员变量属性
/*** 默认长度为10*/private static final int DEFAULT_CAPACITY 10;/*** 用于空实例的共享空数组实例* 是为了优化创建ArrayList空实例时产生不必要的空数组使所有的ArrayList空实例底* 层数据结构都指向同一个空数组* 例如当构造参数是指定的长度且为0 * 当构造参数是一个集合且该参数集合中的元素个数为0*/private static final Object[] EMPTY_ELEMENTDATA {};/*** 用于默认大小的空实例的共享空数组实例。* 将其与EMPTY_ELEMENTDATA区分开来以了解添加第一个元素时要扩容多少* 用于标记当前ArrayList是使用空参构造的在第一次使用add添加元素时数组的最大长度直接使用默认的10*/private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA {};/*** ★ 存储ArrayList元素的数组缓冲区ArrayList的容量就是这个数组缓冲区的长度* 添加第一个元素时任何elementDataDEFAULTCAPACITY_empty_elementData的空ArrayList* 都将扩展为DEFAULT_CAPACITY(默认初始容量10)*/transient Object[] elementData; /*** ★ 记录ArrayList 的元素个数*/private int size;/*** ★ 数组最大的长度*/private static final int MAX_ARRAY_SIZE Integer.MAX_VALUE - 8;构造方法
ArrayList 有三个构造函数空参构造方法指定初始容量值构造方法和指定集合元素列表的构造方法如果集合中的元素不为空新建的ArrayList集合中的元素顺序就是构造参数中的元素顺序
空参构造 之前在网上看到一个说法 使用空参构造一个ArrayList时默认会创建一个容量为10的数组这个说法其实不准确。在JDK1.8以前是这样的但是为了节省内存资源在JDK1.8版本之后使用空参构造方法只会创建一个空底层数据结构长度为0的空数组结构当第一次执行add添加元素时才会将数组容量扩充到默认10 public ArrayList() {this.elementData DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}指定初始容量值构造 如果在构建ArrayList之前就能明确元素的个数那么就可以在构造ArrayList时指定容量大小这样就可以节省因扩容而造成的资源浪费 public ArrayList(int initialCapacity) {if (initialCapacity 0) {//当指定参数大于0时真实存储数据的数据长度就是指定值this.elementData new Object[initialCapacity];} else if (initialCapacity 0) {//当指定参数等于0时使用空数组this.elementData EMPTY_ELEMENTDATA;} else {//指定的长度参数不能小于0throw new IllegalArgumentException(Illegal Capacity: initialCapacity);}}构造参数是一个集合并按照参数集合中元素个数和顺序返回新的ArrayList public ArrayList(Collection? extends E c) {Object[] a c.toArray();if ((size a.length) ! 0) {if (c.getClass() ArrayList.class) {//如果构造参数集合的类型是ArrayList那么构造参数的数组结构直接使用elementData a;} else {//如果构造参数集合的类型不是ArrayList//先初始化的数组长度 构造参数集合元素个数//再将构造参数集合中的数据信息copy到新的数组中elementData Arrays.copyOf(a, size, Object[].class);}} else {//如果构造参数elementData EMPTY_ELEMENTDATA;}}ArrayList 的增删查 add(), 插入元素方法
ArrayList 的add方法有两个尾部插入和指定位置插入
末尾添加 顾名思义就是直接在数组中最后一个元素的下一个位置上存放新添的元素在添加元素之前会校验数组容量是否已经到达临界值如果到达临界值了就先扩容再将新元素添加到扩容后的新数组结构中的最后一个元素后面
public boolean add(E e) {//确定底层elementData的数组长度且校验是否需要扩容//size 1 可以理解为假设长度后面会和当前数组的实际长度相比较以判断是否需要扩容ensureCapacityInternal(size 1); // ★ 扩容核心代码//添加元素实际上就是赋值的操作elementData[size] e;return true;
}指定位置插入 也叫插队添加会打乱原本数组中元素的存储顺序。大致步骤如下: 1.校验数组是否有足够的空间 2.如果空间足够,直接将index及其之后的所有元素向后移动一位 3.如果空间不够,那么先进行扩容,扩容后的新数组长度是旧数组长度的1.5倍,然后将index位置之前的元素全部等位copy到新数组中,index之后的元素全部以index 1 的形式偏移一位copy到新数组中
public void add(int index, E element) {//校验参数index值是否大于数组的长度rangeCheckForAdd(index);//确定底层elementData的数组长度且校验是否需要扩容//size 1 可以理解为假设长度后面会和当前数组的实际长度相比较以判断是否需要扩容ensureCapacityInternal(size 1); //指定位置后面的元素全部copy一份并向右移动一位以便于空出位置System.arraycopy(elementData, index, elementData, index 1,size - index);//最后对指定位置赋值elementData[index] element;size;
}扩容机制
上面有描述ArrayList底层是一个动态数组何为动态就是在ArrayList每次在执行add方法时都会先计算一下假设当前元素添加成功后数组的长度是否已经超过实际长度如果超过那么就自动进行扩容。 简单看一下扩容机制源码
/*** 计算数组长度*/
private void ensureCapacityInternal(int minCapacity) {ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}private static int calculateCapacity(Object[] elementData, int minCapacity) {if (elementData DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {//这里可以看到当使用空参或者指定长度参数指定构造参数集合元素为0时//计算结果此处所需的最小数组长度为10return Math.max(DEFAULT_CAPACITY, minCapacity);}return minCapacity;
}private void ensureExplicitCapacity(int minCapacity) {modCount; //记录数组长度修改次数// overflow-conscious codeif (minCapacity - elementData.length 0)//当所需最小数组长度 大于 当前实际长度时进行扩容grow(minCapacity); //★ 核心扩容机制
}/*** 扩容机制*/private void grow(int minCapacity) {// overflow-conscious codeint oldCapacity elementData.length; //扩容前的数组长度//扩容后的新数组长度 扩容前的数组长度 * 1.5int 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://按照新的长度创建一个新数组然后将原数组的数据copy到新数组中并将add的元素加入到数组中elementData Arrays.copyOf(elementData, newCapacity);}remove(), 删除元素方法
ArrayList 的remove方法有两个指定元素删除和指定位置删除
指定元素删除 由于ArrayList 允许元素重复所以指定元素删除方法可能存在删除多个。
public boolean remove(Object o) {if (o null) {//如果指定删除的元素是null那么循环去校验是由有元素为null//如果存在为null的元素那么就匹配上然后在内存中新开辟一个数组空间将旧数组上//从匹配上位置左边全部 按原index位置copy到新数组中右边的全部按照index -1 的位置copy到新数组中//匹配几次,就需要重新修改几次数组的数组结构for (int index 0; index size; index)if (elementData[index] null) {fastRemove(index);return true;}} else {//如果指定删除的元素不是null那么循环去校验去匹配//同理for (int index 0; index size; index)if (o.equals(elementData[index])) {fastRemove(index);return true;}}return false;
}/** 快速删除方法*/
private void fastRemove(int index) {modCount; //记录数组结构修改的次数int numMoved size - index - 1; //统计需要移动的元素个数if (numMoved 0)//参数1elementData 旧数组//参数2index1 源数组起点//参数3elementData 新数组//参数4index 新数组起点//参数5numMoved 复制多少位System.arraycopy(elementData, index1, elementData, index,numMoved);//数组中的最后一位置为null地址引用删除方便GC清除 elementData[--size] null;
}指定位置删除 最多只会删除一个元素如果指定位置index超出数组结构长度报错 IndexOutOfBoundsException public E remove(int index) {//校验指定index是否超出数组结构长度rangeCheck(index);modCount; //记录数组结构发生调整的次数//通过指定索引index获取数组元素信息E oldValue elementData(index);//统计需要移动的元素个数int numMoved size - index - 1;if (numMoved 0)System.arraycopy(elementData, index1, elementData, index,numMoved);//数组中的最后一位置为null地址引用删除方便GC清除 elementData[--size] null; // clear to let GC do its workreturn oldValue;}/*** 校验指定index是否超出数组结构长度*/private void rangeCheck(int index) {if (index size)throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}ArrayList在执行remove()方法做删除之后,数组中可能会出现大量的空闲空间。而ArrayList没有自动缩容机制,导致底层大量的空闲空间不能被释放,造成内存浪费。对于这种场景,ArrayList也提供了相应的处理方法,如下:
/*** 将此ArrayList实例的容量修改为列表的当前大小。*/public void trimToSize() {//记录数组结构发生调整的次数modCount;//size 是当前数组中的元素个数//当元素个数小于数组实际长度时,做缩容处理; 比例按照元素个数进行缩容if (size elementData.length) {//实际元素个数为0,直接将数组置为空数组elementData (size 0)? EMPTY_ELEMENTDATA: Arrays.copyOf(elementData, size); //生成新数组, 长度 元素个数,将元素copy到新数组中}}ArrayList 的增删方法总结, 为什么ArrayList是增删慢的? 从上文介绍可知, add() 方法会存在扩容场景, remove() 会存在移动元素的场景, 这些都会对性能产生很大的影响。用时间复杂度来表示是O(n),所以增删效率低
get(), 取元素方法
ArrayList 的get方法只有一个只能通过索引下标index获取
public E get(int index) {//校验指定index是否超出数组结构长度rangeCheck(index);//直接通过索引index获取指定位置的value值return elementData(index);
}/*** 校验index的有效性* index 不能超过数组元素的个数,否则会报数组越界异常*/
private void rangeCheck(int index) {if (index size)throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}首先数组是存在堆内存中,一块连续的内存空间,并且ArrayList的底层是Object[]数组, 那么数组中的所有元素所占用的字节大小是一致的,所以想要从堆内存中获取元素信息,就必须知道index位置元素在堆内存中的内存地址。数组上元素的内存地址,主要就是看index下标对应的偏移量,这里就需要计算: 公式: 数组上元素的内存地址 数组的起始地址 index * 元素的大小(单位是字节,) 计算出index对应的元素内存地址后, 即可获取到对应数组上元素信息, 而数组中存放的是元素实际数据信息的内存地址,再通过此地址获取到实际元素数据信息 由于get()取元素方法,是通过下标index 精准定位,继而获取元素信息的, 这期间没有所谓的扩容,copy,迁移等等场景, 用时间复杂度来表示是O(1),所以效率高。
set(), 修改元素方法
ArrayList 中的修改方法只有一个,通过index下标来精准修改, 修改元素信息的步骤,其实就是同一个位置的信息覆盖操作 public E set(int index, E element) {//校验指定index是否超出数组结构长度rangeCheck(index);//通过index,获取旧的元素信息E oldValue elementData(index);//然后覆盖替换elementData[index] element;return oldValue;}/*** 校验index的有效性* index 不能超过数组元素的个数,否则会报数组越界异常*/
private void rangeCheck(int index) {if (index size)throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}
