个人中心
gpt4 book ai didi

Java ArrayList使用总结

转载 作者：qq735679552 更新时间：2022-09-29 22:32:09 25 4
gpt4 key购买 nike

CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章Java ArrayList使用总结由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.

提起ArrayList,相信很多小伙伴都用过，而且还不少用。但在几年之前，我在一场面试中，面试官要求说出ArrayList的扩容机制。很显然，那个时候的我并没有关注这些，从而错过了一次机会。不过好在我还算比较喜欢搞事情的，所以今天这篇文章也算是填坑吧。 看完这边文章你将了解到:

  • ArrayList底层实现
  • ArrayList为什么允许null值
  • ArrayList为什么可重复
  • ArrayList查询效率和插入效率对比

类图

下图是ArrayList的类图结构 。

Java ArrayList使用总结

ArrayList继承于 AbstractList，实现了 List, RandomAccess, Cloneable, java.io.Serializable 这些接口。 这里逐个分析一下这里接口的意义:

  • RandomAccess是一个标志接口，表明实现这个这个接口的 List集合是支持快速随机访问的。有兴趣可以看看Collections类中哪个方法用到了这个标志性接口。
  • 实现 Cloneable接口并覆盖了方法clone()，能被克隆。
  • 实现了java.io.Serializable 接口，这意味着ArrayList支持序列化，能通过序列化去传输（请注意，ArrayList的序列化是有点小特殊的，后面会讲解）。

源码解析

成员变量 在正式进入源码分析之前，我们有必要先看看它的成员变量都有哪些，这里列举比较重要的成员变量:

?
1
2
3
private int size; // 实际元素个数
transient Object[] elementData; //真正保存元素的数组
private static final int DEFAULT_CAPACITY = 10 ; //默认的初始容量大小

构造方法 我们有三种初始化办法：无参数直接初始化、指定大小初始化、指定初始数据初始化，源码如下

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//1、无参数直接初始化，数组大小为空
public ArrayList() {
  this .elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
//2、指定初始数据初始化
public ArrayList(Collection<? extends E> c){
  //elementData是保存数组的容器，默认为null
  elementData=c.toArray();
  //如果给定的集合（c)数据有值
  if ((size=elementData.length)!= 0 ){
     //c.toArray might(incorrectly)not return Object[](see 6260652)
     //如果集合元素类型不是Object类型，我们会转成Object
      if (elementData.getClass()!=Object[]. class ){
       elementData=Arrays.copyOf(elementData,size,Object]. class );
      }
     } else {
     //给定集合（c)无值，则默认空数组
     this .elementData=EMPTY_ELEMENTDATA
     }
}
//3、指定初始容量
public ArrayList( int initialCapacity) {
     //指定的初始容量大于0，将elementData初始化为指定大小的数组
  if (initialCapacity > 0 ) {
   this .elementData = new Object[initialCapacity];
  } else if (initialCapacity == 0 ) {
     //否则初始化成一个空数组
   this .elementData = EMPTY_ELEMENTDATA;
  }
}

除过源码中注释外，补充几点:

  1. ArrayList无参构造器初始化时，默认大小是空数组，并不是大家常说的10,10是在第一次add的时候扩容的数组值。
  2. 使用方式二进行创建对象时，如果入参容器保存的对象不是Object，则转换为Object。

DEFAULTCAPACITY_EMPTY_ELEMENTDATA和EMPTY_ELEMENTDATA又是什么鬼？它其实是定义在成员变量的两个空数组， 。

?
1
2
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
private static final Object[] EMPTY_ELEMENTDATA = {};

很明显问题来了，既然都是空数组，为什么要声明两个？一个不行吗？读者请先思考一下，带着疑问往下看.

新增和扩容实现

通过构造方法可以很清楚的看到，ArrayList的确是基于数组的，但动态又从何说起？ 新增时就是给数组中添加元素，主要分为两步走:

  1. 判断是否需要扩容，如果需要扩容执行扩容操作；
  2. 直接赋值。

对应源码如下:

?
1
2
3
4
5
6
public boolean add(E e) {
     //确保数组大小是否足够，不够执行扩容，size为当前数组元素个数，判断size+1是因为后面还要size++
  ensureCapacityInternal(size + 1 ); //1
  elementData[size++] = e; //2
  return true ;
}

我们先来看一下扩容部分的源码:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
private void ensureCapacityInternal( int minCapacity) {
     //先调用calculateCapacity计算容量
     ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
  //如果当前数组还是个空数组，也就是他用过无参构造去初始化的
  //那么直接返回DEFAULT_CAPACITY，即10
  if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
   return Math.max(DEFAULT_CAPACITY, minCapacity);
  }
  return minCapacity;
}
 
private void ensureExplicitCapacity( int minCapacity) {
  modCount++;
 
  // 如果当前容量已经大于当前数组的长度了，说明需要去扩容了
  if (minCapacity - elementData.length > 0 )
   //扩容
   grow(minCapacity);
}
 
private void grow( int minCapacity){
  int oldCapacity = elementData.length;
  //oldCapacity>>1是把oldCapacity除以2的意思
  int newCapacity=oldCapacity+(oldCapacity>> 1 );
  //如果扩容后的值<我们的期望值，扩容后的值就等于我们的期望值
  if (newCapacity-minCapacity< 0 )
  newCapacity = minCapacity;
  //如果扩容后的值>jvm所能分配的数组的最大值，那么就用Integer的最大值
  if (newCapacity-MAX_ARRAY_SIZE> 0 )
  elementData=Arrays.copyOf(elementData,newCapacity);
}

注释相对来说已经比较详细了，这里需要注意以下几点:

  1. 上面有个问题是为什么需要声明两个空数组。我们在看到上面源码的时候有一个方法为calculateCapacity，这个方法内部逻辑只有在通过无参构造初始化ArrayList的时候才会改变将要返回的minCapacity。而返回的这个值将会决定下面的数组是否需要扩容。如果我们通过指定大小的方式初始化ArrayList并指定大小为0，这说明我们需要的就是一个空的ArrayList，不需要去扩容，你细品；
  2. 新增时，没有对值进行校验，所以新增值可以为null，且没有做重复值判断，所以元素可以重复；
  3. ArrayList中的数组的最大值是Integer.MAX_VALUE，超过这个值，JVM就不会给数组分配内存空间了；
  4. 扩容是原来容量大小+容量大小的一半，简单说就是扩容后的大小是原来容量的1.5倍。

扩容完成之后，就是简单的赋值了，赋值时并没有加锁，所以是线程不安全的.

扩容的本质

在grow方法的最后，扩容是通过Arrays.copyOf(elementData,newCapacity);这行代码实现的。这个方法实际上调用的方法是我们经常使用的System.arraycopy:

?
1
2
3
4
5
6
7
8
9
/**
*@param src 被拷贝的数组
*@param srcPos 从数组那里开始
*@param dest 目标数组
*@param destPos从目标数组那个索引位置开始拷贝
*@param length 拷贝的长度
*此方法是没有返回值的，通过dest的引用进行传值
*/
public static native void arraycopy(Object src, int srcPos,Object dest, int destPos, int length);

这个方法是一个native方法，虽然不能看到方法内部的具体实现，但通过参数也可以管中窥豹。这个方法会移动元素。所以说数组如果要扩容，需要重新分配一块更大的空间，再把数据全部复制过去，时间复杂度 O(N)；而且你如果想在数组中间进行插入和删除，每次必须搬移后面的所有数据以保持连续，时间复杂度 O(N)。由于数组又是一块连续的内存空间，能够根据索引快速访问元素。 上面也就解释了一开始那个问题：ArrayList为什么插入慢，查询快.

删除

ArrayList有多种删除方法，这里以根据值删除的方式进行说明(其他原理类似):

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public boolean remove(Object o) {
  //如果要删除的值是null,删除第一个是null的值
  if (o== null ){
  for ( int index= 0 ;index<size;index++)
   if (elementData[index]== null ){
   fastRemove(index)
   return true ;
   }
  } else {
  //如果要删除的值不为null,找到第一个和要删除的值相等的删除
  for ( int index= 0 ;index<size;index++)
   //这里是根据 equals来判断值相等的，相等后再根据索引位置进行删除
   //所以根据对象删除时，一般来说，如果你确定要删除的是某一类的业务对象，则需要重写equals
   if (o.equals(elementData[index]){
   fastRemove(index)
   return true ;
   }
  }
  return false
}

核心其实是fastRemove方法:

?
1
2
3
4
5
6
7
8
9
10
11
12
private void fastRemove( int index){
  //记录数组的结构要发生变动了
  nodCount++;
  //numMoved表示删除index位置的元素后，需要从index后移动多少个元素到前面去
  //减1的原因，是因为size从1开始算起，index从0开始算起
  int numMoved=size-index- 1 ;
  if (numMoved> 0 )
  //从index+1位置开始被拷贝，拷贝的起始位置是index,长度是numMoved
  System.arraycopy(elementData, index+ 1 , elementData, index, numMoved);
  //数组最后一个位置赋值null,帮助GC(没有引用则自动回收了)
  elementData[--size] = null ;
}

从源码中，我们可以看出，某一个元素被删除后，为了维护数组结构，我们都会把数组后面的元素往前移动，同时释放最后一个引用，便于回收.

总结

本文主要从ArrayList的源码入手，分别从初始化、新增、扩容、删除四个方面展开学习。我们发现ArrayList内部其实就是围绕了一个数组，在数组容量不足时将数组扩容至更大，所以也就自然被称作基于动态数组。 微信搜索Java成神之路或扫描下方二维码，发现更多Java有趣知识，让我们一起成长！ 。

以上就是Java ArrayList使用总结的详细内容，更多关于Java ArrayList使用的资料请关注我其它相关文章！ 。

原文链接：https://www.cnblogs.com/printfn/p/14590940.html 。

最后此篇关于Java ArrayList使用总结的文章就讲到这里了,如果你想了解更多关于Java ArrayList使用总结的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。

25 4 0
文章推荐： 360随身wifi修改密码后，手机连不上怎么办
文章推荐： 为何人工智能(AI)首选Python？读完这篇文章你就知道了（推荐）
文章推荐： Linux下高并发socket最大连接数所受的各种限制(详解)
文章推荐： python基础梳理（一）（推荐）
qq735679552
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
全站热门文章
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com