最常用集合 - ArrayList详解

2024-08-31 04:04
文章标签 详解 常用 arraylist 集合

本文主要是介绍最常用集合 - ArrayList详解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

ArrayList介绍

ArrayList实现了List接口，是顺序容器，即元素存放的数据与放进去的顺序相同，允许放入null元素，底层通过数组实现。除该类未实现同步外，其余跟Vector大致相同。每个ArrayList都有一个容量(capacity)，表示底层数组的实际大小，容器内存储元素的个数不能多于当前容量。当向容器中添加元素时，如果容量不足，容器会自动增大底层数组的大小。

ArrayList 在JDK1.8 前后的实现区别：

  • JDK1.7：像饿汉式，直接创建一个初始容量为10的数组
  • JDK1.8：像懒汉式，一开始创建一个长度为0的数组，当添加add第一个元素时再创建一个初始容量为10的数组

size(), isEmpty(), get(), set()方法均能在常数时间内完成，add()方法的时间开销跟插入位置有关，addAll()方法的时间开销跟添加元素的个数成正比。其余方法大都是线性时间。

为追求效率，ArrayList没有实现同步(synchronized)，如果需要多个线程并发访问，用户可以手动同步，也可使用Vector替代

底层原理介绍

底层数据结构

//集合默认容量10；
private static final int DEFAULT_CAPACITY = 10;//空数组
private static final Object[] EMPTY_ELEMENTDATA = {};//默认容量的空的数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};// 集合中真实存储数据的数组
transient Object[] elementData; // non-private to simplify nested class access//集合中元素的个数，注意，这里不是数组的长度
private int size;

构造方法

public ArrayList() {//将属性中默认的空的数组赋值给了 存储数据的变量this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;//等价于this.elementData = {}
}//有参构造
public ArrayList(int initialCapacity) {//给定初始容量，就创建一个这个容量大小的数组if (initialCapacity > 0) {this.elementData = new Object[initialCapacity];} else if (initialCapacity == 0) {//如果传递的是0 就将{}赋值给elementData this.elementData = EMPTY_ELEMENTDATA;//等价于this.elementData = {}} else {//如果传递的是负数，就会抛异常//java.lang.IllegalArgumentException: Illegal Capacity: -20throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);}
}

自动扩容

每当向数组中添加元素时，都要去检查添加后元素的个数是否会超出当前数组的长度，如果超出，数组将会进行扩容，以满足添加数据的需求。

private void grow(int minCapacity) {// overflow-conscious codeint oldCapacity = elementData.length;//动态扩容，扩容为原来的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:    elementData = Arrays.copyOf(elementData, newCapacity);//数组的复制操作
}

扩容方法流程：

  1. 首先获取数组长度

  2. 将数组新容量扩容为原数组容量的1.5倍取整

  3. 将新容量和当前所需最小容量做对比，(最小容量是在add方法中得到的，minCapacity=size+1，即原数组中元素数量加1)，而newCapacity=elementData.length*1.5，一般来说肯定是1.5倍比+1的大。但是这里要考虑当数组为空时的情况。数组为空又分为两种情况：①指定了数组容量为0 ②没有显式指定数组大小。

    • 当数组为空时进行插入操作，因为元素个数size为0，数组容量也为0，那么就会进行扩容操作，对于空数组，扩容1.5倍后你的容量还是为0，那么此时就会小于我所需的最小容量（也就是1）,此时会令 newCapacity = minCapacity;

    • 而对于①，传入到grow方法的minCapacity = 1 ，因此它扩容后的容量就是1

    • 对于②，在ensureCapacityInternal方法中，使minCapacity = DEFAULT_CAPACITY（10），因此扩容后的数组长度就是DEFAULT_CAPACITY，也就是10。

      • 原因在于在有参构造方法中使this.elementData = EMPTY_ELEMENTDATA;（无参构造方法中this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;），此时在ensureCapacityInternal方法中会对this.elementData进行判断，因此对于①，传入到grow方法的minCapacity = 1；而对于②，minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity)，即minCapacity = 10
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {//比较大小，此时 minCapacity = 10minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
  1. 最后判断新容量大小是否大于默认数组的最大值（Integer.MAX_VALUE-8），则赋予它整型的最大值
  2. 扩容之后，会调用Arrays.copyOf()方法对数组进行拷贝。

实际上，对数组的copy需要创建一个新数组，并对原数组进行复制的操作，这会造成资源消耗。因此在添加大量元素前，建议使用ensureCapacity操作先增加 ArrayList 实例的容量，先进行稍少量数组数据的copy，再添加元素

add(), addAll()

add 操作可能会导致capacity不足，因此在添加元素之前，都需要进行剩余空间检查，如果需要则自动扩容。扩容操作最终是通过grow()方法完成的。

假设使用的是空参构造，第一次添加元素 add(1)

public boolean add(E e) {//确保内部容量 0 + 1ensureCapacityInternal(size + 1);  // Increments modCount!!//将要添加的元素添加到数组有数据的下一个位置elementData[size++] = e;return true;
}private void ensureCapacityInternal(int minCapacity) {//第一次添加： minCapacity = 1//有参构造的情况：new Object[10] != {}，不会执行if内的语句。即使有参构造给的是0，也不会执行，因为此时elementData = EMPTY_ELEMENTDATA，不等于DEFAULTCAPACITY_EMPTY_ELEMENTDATA// 无参构造的情况下：{} = {} 会执行Math.max语句if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {//比较大小，此时 minCapacity = 10minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);}//明确数组的容量ensureExplicitCapacity(minCapacity);
}private void ensureExplicitCapacity(int minCapacity) {modCount++;//记录当前集合操作的次数// overflow-conscious codeif (minCapacity - elementData.length > 0)grow(minCapacity);//扩容操作
}

addAll()方法能够一次添加多个元素，根据位置不同也有两个版本，

  • 在末尾添加的addAll(Collection<? extends E> c)方法，

  • 从指定位置开始插入的addAll(int index, Collection<? extends E> c)方法

跟add()方法类似，在插入之前也需要进行空间检查，如果需要则自动扩容；如果从指定位置插入，也会存在移动元素的情况。 addAll()的时间复杂度不仅跟插入元素的多少有关，也跟插入的位置相关。

set()

由于底层是数组，因此set()方法就是直接对数组的指定位置赋值。

public E set(int index, E element) {rangeCheck(index);//下标越界检查E oldValue = elementData(index);elementData[index] = element;//赋值到指定位置，复制的仅仅是引用return oldValue;
}

get()

由于底层是数组，get()方法也是直接从数组索引处获取值，唯一要注意的是由于底层数组是Object[]，得到元素后需要进行类型转换。

public E get(int index) {rangeCheck(index);return (E) elementData[index];//注意类型转换
}

remove方法

remove()方法也有两个

  • remove(int index)删除指定位置的元素，

  • remove(Object o)删除第一个满足o.equals(elementData[index])的元素。

删除操作是add()操作的逆过程，会需要将删除点之后的元素向前移动一个位置

public E remove(int index) {rangeCheck(index);modCount++;E oldValue = elementData(index);int numMoved = size - index - 1;if (numMoved > 0)//判断要删除的索引是否是最后一个，，如果不是最后一个，就需要进行数组的复制操作System.arraycopy(elementData, index+1, elementData, index,numMoved);//然后把最后一个元素置为空，让GC起作用elementData[--size] = null; // clear to let GC do its workreturn oldValue;
}

trimToSize()

将底层数组的容量调整为当前列表保存的实际元素的大小的功能

 /*** Trims the capacity of this <tt>ArrayList</tt> instance to be the* list's current size.  An application can use this operation to minimize* the storage of an <tt>ArrayList</tt> instance.*/public void trimToSize() {modCount++;if (size < elementData.length) {elementData = (size == 0)? EMPTY_ELEMENTDATA: Arrays.copyOf(elementData, size);}}

indexOf(), lastIndexOf()

获取元素的第一次出现的index:

public int indexOf(Object o) {if (o == null) {for (int i = 0; i < size; i++)if (elementData[i]==null)return i;} else {for (int i = 0; i < size; i++)if (o.equals(elementData[i]))return i;}return -1;}

获取元素的最后一次出现的index:

public int lastIndexOf(Object o) {if (o == null) {for (int i = size-1; i >= 0; i--)if (elementData[i]==null)return i;} else {for (int i = size-1; i >= 0; i--)if (o.equals(elementData[i]))return i;}return -1;}

遍历时删除（添加）常见陷阱

for循环遍历list

删除某个元素后，list的大小发生了变化，而索引也在变化，所以会导致遍历的时候漏掉某些元素。比如当删除第1个元素后，继续根据索引访问第2个元素时，因为删除的关系后面的元素都往前移动了一位，所以实际访问的是第3个元素。因此，这种方式可以用在删除特定的一个元素时使用，但不适合循环删除多个元素时使用。

for(int i=0;i<list.size();i++){if(list.get(i).equals("del"))list.remove(i);
}

解决办法：

//从list最后一个元素开始遍历

//从list最后一个元素开始遍历
for(int i=list.size()-1;i>+0;i--){if(list.get(i).equals("del"))list.remove(i);
}

增强for循环

删除元素后继续循环会抛异常java.util.ConcurrentModificationException，因为元素在使用的时候发生了并发的修改

for(String x:list){if(x.equals("del"))list.remove(x);
}

解决方法：但只能删除一个"del"元素

//解决：删除完毕马上使用break跳出，则不会触发报错
for(String x:list){if (x.equals("del")) {list.remove(x);break;}
}

iterator遍历

这种方式可以正常的循环及删除。但要注意的是，使用iterator的remove方法，如果用list的remove方法同样会报上面提到的ConcurrentModificationException错误。

Iterator<String> it = list.iterator();
while(it.hasNext()){String x = it.next();if(x.equals("del")){it.remove();}
}

FailFast机制

上面提到的ConcurrentModificationException异常，都是有这个机制的存在，通过记录modCount参数来实现。在面对并发的修改时，迭代器很快就会完全失败，而不是冒着在将来某个不确定时间发生任意不确定行为的风险。

fail-fast 机制是java集合(Collection)中的一种错误机制。当多个线程对同一个集合的内容进行操作时，就可能会产生fail-fast事件。例如：当某一个线程A通过iterator去遍历某集合的过程中，若该集合的内容被其他线程所改变了；那么线程A遍历集合时，即出现expectedModCount != modCount 时，就会抛出ConcurrentModificationException异常，产生fail-fast事件。

if (modCount != expectedModCount)throw new ConcurrentModificationException();

fail-fast 机制并不保证在不同步的修改下抛出异常，他只是尽最大努力去抛出，所以这种机制一般仅用于检测 bug

解决 fail-fast的解决方案：

  1. 在遍历过程中所有涉及到改变modCount值得地方全部加上synchronized或者直接使用Collections.synchronizedList，这样就可以解决(实际上Vector结构就是这样实现的)。但是不推荐，因为增删造成的同步锁可能会阻塞遍历操作。
List<Integer> arrsyn = Collections.synchronizedList(arr);
  1. 使用CopyOnWriteArrayList来替换ArrayList。推荐使用该方案。CopyOnWriteArrayList是兼顾了并发的线程安全

ArrayList和Vector和CopyOnWriteArrayList和LinkedList

继承关系结构图：

ArrayList和Vector和CopyOnWriteArrayList的区别：

  • ArrayList非线程安全的，如果需要考虑到线程安全问题，那么可以使用Vector和CopyOnWriteArrayList；

  • Vector和CopyOnWriteArrayList的区别是：Vector增删改查方法都加了synchronized，保证同步，但是每个方法执行的时候都要去获得锁，性能就会大大下降，而CopyOnWriteArrayList 只是在增删改上加锁，但是读不加锁，在读方面的性能就好于Vector，CopyOnWriteArrayList支持读多写少的并发情况。

ArrayList和LinkedList的区别：

  • ArrayList基于动态数组实现；

  • LinkedList基于链表实现。对于随机index访问的get和set方法，ArrayList的速度要优于LinkedList。因为ArrayList直接通过数组下标直接找到元素；LinkedList要移动指针遍历每个元素直到找到为止。

  • 对于 add(int index, E element)，remove(int index)的操作：LinkedList 和 ArrayList的时间复杂度一样，都是O(n)；虽然时间复杂度一样，但实际执行时间是不一样的，如下代码所示：

    List<Integer> a = Lists.newArrayList();
List<Integer> b = Lists.newLinkedList();Random r = new Random();
a.add(0);
b.add(0);long startTime = System.currentTimeMillis();
for (int i = 0; i <= 20000; i++) {int p = r.nextInt(a.size());a.add(p, 0);
}
System.out.println(System.currentTimeMillis() - startTime);// 6startTime = System.currentTimeMillis();
for (int i = 0; i <= 20000; i++) {int p = r.nextInt(b.size());b.add(p, 0);
}
System.out.println(System.currentTimeMillis() - startTime);// 205

    虽然ArrayList在索引位置新增或删除数据时需要移动数据（往前移、往后移），但是在连续内存中的块的数据，是可以操作整片内存的。而LinkedList需要一个一个的先查找到具体索引位置的元素，所以在寻址方面数组的效率高于链表。

  • 对于add新增元素：理论上来说LinkedList的速度（O(1)）要优于ArrayList（O(n)），因为ArrayList在新增和删除元素时，可能会扩容和复制数组；LinkedList只需要修改指针即可。但在实际测试中，在数据量小的情况下，两者执行时间几乎一致；增大数据量后，就能看出区别了，如下代码所示：

    List<Integer> a = Lists.newArrayList();
List<Integer> b = Lists.newLinkedList();a.add(0);
b.add(0);long startTime = System.currentTimeMillis();
for (int i = 0; i <= 2000000; i++) {int p = r.nextInt(a.size());a.add(0);
}
System.out.println(System.currentTimeMillis() - startTime);// 34startTime = System.currentTimeMillis();
for (int i = 0; i <= 2000000; i++) {int p = r.nextInt(b.size());b.add(0);
}
System.out.println(System.currentTimeMillis() - startTime);// 271

    这是因为LinkedList 存在一定的性能问题

关于作者

来自一线程序员Seven的探索与实践，持续学习迭代中~

本文已收录于我的个人博客：https://www.seven97.top

公众号：seven97，欢迎关注~

这篇关于最常用集合 - ArrayList详解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1122830。

相关文章

Mysql 中的多表连接和连接类型详解

Mysql 中的多表连接和连接类型详解

《Mysql中的多表连接和连接类型详解》这篇文章详细介绍了MySQL中的多表连接及其各种类型,包括内连接、左连接、右连接、全外连接、自连接和交叉连接,通过这些连接方式,可以将分散在不同表中的相关数据... 目录什么是多表连接？1. 内连接（INNER JOIN）2. 左连接（LEFT JOIN 或 LEFT
阅读更多...
Java中ArrayList的8种浅拷贝方式示例代码

Java中ArrayList的8种浅拷贝方式示例代码

《Java中ArrayList的8种浅拷贝方式示例代码》：本文主要介绍Java中ArrayList的8种浅拷贝方式的相关资料,讲解了Java中ArrayList的浅拷贝概念,并详细分享了八种实现浅... 目录引言什么是浅拷贝？ArrayList 浅拷贝的重要性方法一：使用构造函数方法二：使用 addAll(
阅读更多...
Java中switch-case结构的使用方法举例详解

Java中switch-case结构的使用方法举例详解

《Java中switch-case结构的使用方法举例详解》：本文主要介绍Java中switch-case结构使用的相关资料,switch-case结构是Java中处理多个分支条件的一种有效方式,它... 目录前言一、switch-case结构的基本语法二、使用示例三、注意事项四、总结前言对于Java初学者
阅读更多...
Linux内核之内核裁剪详解

Linux内核之内核裁剪详解

《Linux内核之内核裁剪详解》Linux内核裁剪是通过移除不必要的功能和模块,调整配置参数来优化内核,以满足特定需求,裁剪的方法包括使用配置选项、模块化设计和优化配置参数,图形裁剪工具如makeme... 目录简介一、 裁剪的原因二、裁剪的方法三、图形裁剪工具四、操作说明五、make menuconfig
阅读更多...
详解Java中的敏感信息处理

详解Java中的敏感信息处理

《详解Java中的敏感信息处理》平时开发中常常会遇到像用户的手机号、姓名、身份证等敏感信息需要处理,这篇文章主要为大家整理了一些常用的方法,希望对大家有所帮助... 目录前后端传输AES 对称加密RSA 非对称加密混合加密数据库加密MD5 + Salt/SHA + SaltAES 加密平时开发中遇到像用户的
阅读更多...
Java 枚举的常用技巧汇总

Java 枚举的常用技巧汇总

《Java枚举的常用技巧汇总》在Java中,枚举类型是一种特殊的数据类型,允许定义一组固定的常量,默认情况下,toString方法返回枚举常量的名称,本文提供了一个完整的代码示例,展示了如何在Jav... 目录一、枚举的基本概念1. 什么是枚举？2. 基本枚举示例3. 枚举的优势二、枚举的高级用法1. 枚举
阅读更多...
Springboot使用RabbitMQ实现关闭超时订单(示例详解)

Springboot使用RabbitMQ实现关闭超时订单(示例详解)

《Springboot使用RabbitMQ实现关闭超时订单(示例详解)》介绍了如何在SpringBoot项目中使用RabbitMQ实现订单的延时处理和超时关闭,通过配置RabbitMQ的交换机、队列和... 目录1.maven中引入rabbitmq的依赖：2.application.yml中进行rabbit
阅读更多...
C语言线程池的常见实现方式详解

C语言线程池的常见实现方式详解

《C语言线程池的常见实现方式详解》本文介绍了如何使用C语言实现一个基本的线程池,线程池的实现包括工作线程、任务队列、任务调度、线程池的初始化、任务添加、销毁等步骤,感兴趣的朋友跟随小编一起看看吧... 目录1. 线程池的基本结构2. 线程池的实现步骤3. 线程池的核心数据结构4. 线程池的详细实现4.1 初
阅读更多...
Python绘制土地利用和土地覆盖类型图示例详解

Python绘制土地利用和土地覆盖类型图示例详解

《Python绘制土地利用和土地覆盖类型图示例详解》本文介绍了如何使用Python绘制土地利用和土地覆盖类型图,并提供了详细的代码示例,通过安装所需的库,准备地理数据,使用geopandas和matp... 目录一、所需库的安装二、数据准备三、绘制土地利用和土地覆盖类型图四、代码解释五、其他可视化形式1.
阅读更多...
SpringBoot使用Apache POI库读取Excel文件的操作详解

SpringBoot使用Apache POI库读取Excel文件的操作详解

《SpringBoot使用ApachePOI库读取Excel文件的操作详解》在日常开发中,我们经常需要处理Excel文件中的数据,无论是从数据库导入数据、处理数据报表,还是批量生成数据,都可能会遇到... 目录项目背景依赖导入读取Excel模板的实现代码实现代码解析ExcelDemoInfoDTO 数据传输
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2