欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  科技

ArrayList 源码解析和设计思路

程序员文章站 2022-07-08 10:16:33
Arraylist源码分析ArrayList 我们几乎每天都会使用到,但是通常情况下我们只是知道如何去使用,至于其内部是怎么实现的我们不关心,但是有些时候面试官就喜欢问与ArrayList 的源码相关的问题,今天我们就来看看和ArrayList 源码相关的问题。一:整体架构1.1、ArrayList 结构ArrayList 整体架构比较简单,就是一个数组结构,比较简单,如下图:图中展示是长度为 n 的数组,index 表示数组的下标,从 0 开始计数,elementData 表示数组本身,源码中...

Arraylist源码分析

ArrayList 我们几乎每天都会使用到,但是通常情况下我们只是知道如何去使用,至于其内部是怎么实现的我们不关心,但是有些时候面试官就喜欢问与ArrayList 的源码相关的问题,今天我们就来看看和ArrayList 源码相关的问题。

一:整体架构

1.1、ArrayList 结构

ArrayList 整体架构比较简单,就是一个数组结构,比较简单,如下图:
ArrayList 源码解析和设计思路
图中展示是长度为 n 的数组,index 表示数组的下标,从 0 开始计数,elementData 表示数组本身,源码中除了这两个概念,还有以下三个基本概念:

  1. DEFAULT_CAPACITY ,表示数组的初始大小,默认是 10;
  2. size ,当前数组的大小,没有使用 volatile 修饰,非线程安全的;
  3. modCount ,统计当前数组被修改的版本次数;

1.2、ArrayList 类注释

看源码,首先要看类注释,我们看看类注释上面都说了什么,部分截图如下图所示:
ArrayList 源码解析和设计思路
类注释主要讲了以下四点

  1. 允许put null 值,会自动扩容
  2. size、isEmpty、get、set、add 等方法时间复杂度都是 O (1)
  3. 是非线程安全的,多线程情况下,推荐使用线程安全类:Collections#synchronizedList
  4. 增强 for 循环,或者使用迭代器迭代过程中,如果数组大小被改变,会快速失败,抛出异常

二:源码解析

2.1、初始化

ArrayList 有三种初始化办法:无参数直接初始化、指定大小初始化、指定初始数据初始化,源码如下:

// 无参数直接初始化,数组大小为空
public ArrayList() {
	this.elementData = DEFAULTCAPACITY_EMPTY_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);
   }
}

// 指定初始数据初始化
public ArrayList(Collection<? extends E> c) {
	elementData = c.toArray();
    if ((size = elementData.length) != 0) {
    	// c.toArray might (incorrectly) not return Object[] (see 6260652)
    if (elementData.getClass() != Object[].class) {
        elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
      // replace with empty array.
      this.elementData = EMPTY_ELEMENTDATA;
   }
}

注意: ArrayList 无参构造器初始化时,默认大小是空数组,并不是大家常说的 10,10 是在第一次 add 的时候扩容的数组值。

2.2、新增和扩容实现

新增方法主要分成两步:首先判断数组是否需要扩容,如果需要,执行扩容操作,否则,直接赋值。新增方法源码如下,其中ensureCapacityInternal()方法就是扩容操作。

public boolean add(E e) {
  //确保数组大小是否足够,不够执行扩容,size 为当前数组的大小
  ensureCapacityInternal(size + 1);  // Increments modCount!!
  //直接赋值,线程不安全的
  elementData[size++] = e;
  return true;
}

扩容(ensureCapacityInternal)的源码:

private void ensureCapacityInternal(int minCapacity) {
  // 如果初始化数组大小时,有给定初始值,以给定的大小为准,不走 if 逻辑
  if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
    minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
  }
  // 确保容积足够
  ensureExplicitCapacity(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)
    newCapacity = hugeCapacity(minCapacity);
 
  // 通过复制进行扩容
  elementData = Arrays.copyOf(elementData, newCapacity);
}

从扩容的源码我们可以看出:

  1. 扩容的规则并不是翻倍,而是原来容量的 1.5 倍 ;
  2. ArrayList 中的数组容量的最大值是 Integer.MAX_VALUE,超过这个值,JVM 就不会给数组分配内存空间了 ;

2.3、删除

ArrayList 删除元素有很多种方式,比如根据数组索引删除、根据值删除或批量删除等等,原理和思路都差不多,我们选取根据值删除方式来进行源码说明:

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 来判断值相等的,相等后再根据索引位置进行删除
      if (o.equals(elementData[index])) {
        fastRemove(index);
        return true;
      }
  }
  return false;
}

从上面的源码中我们可以看出:

  1. 由于新增的时候没有对 null 值做出判断,所以是可以删除 null 值的 ;
  2. 找到值在数组中的索引位置,是通过 equals 来判断的,如果数组元素不是基本类型,我们需要关注 equals 的具体实现;

删除的具体逻辑是在fastRemove()中实现的,源码如下所示

private void fastRemove(int index) {
  // 记录数组的结构要发生变动了
  modCount++;
  // 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;
}

2.4、复杂度分析

操作 时间复杂度
get() 根据下标直接查询 O(1)
add(E e) 直接尾部添加 O(1)
add(int index, E e) 插入后元素需要往后移动一个单位 O(n)
remove(E e) 删除后元素需要往前移动一个单位 O(n)

2.5、线程安全

我们需要强调的是,只有当 ArrayList 作为共享变量时,才会有线程安全问题,当 ArrayList 是方法内的局部变量时,是没有线程安全的问题的。

ArrayList 有线程安全问题的本质,是因为 ArrayList 自身的 elementData、size、modConut 在进行各种操作时,都没有加锁,而且这些变量的类型并非是可见(volatile)的,所以如果多个线程对这些变量进行操作时,可能会有值被覆盖的情况。

类注释中推荐我们使用 Collections#synchronizedList 来保证线程安全,SynchronizedList 是通过在每个方法上面加上锁来实现,虽然实现了线程安全,但是性能大大降低。

三:总结

从上面 ArrayList 的部分源码的分析中,我们可以发现 ArrayList 底层其实就是围绕数组结构,各个 API 都是对数组的操作进行封装,让使用者无需感知底层实现,只需关注如何使用即可。

本文地址:https://blog.csdn.net/weixin_38478780/article/details/107688462

相关标签: Java源码 java