【Java 集合】这次真的从0到1彻底吃透ArrayList底层实现源码!

文章较长,希望你能耐心阅读!相信你能够受益匪浅

0、ArrayList简介

ArrayList是 Java 集合 List 的一个实现类,List 是一个接口,其实现类除 ArrayList 之外,还有 LinkedList,并继承了 Collection,ArrayList集合很常用,同时也是程序员面试时经常会被问到的知识点,下面是结构图:

  1. 实现了 Serializable 接口,表明它支持序列化。

  2. 实现了 Cloneable 接口,表明它支持克隆,可以调用超类的 clone()方法进行浅拷贝。

  3. 实现了RandomAccess 接口:这是个标记接口,表明该类可随机访问。

  4. 继承了 AbstractList 抽象类,在他们的抽象父类中,都提供了equals() 方法和 hashCode() 方法。它们自身并不实现这两个方法。

  5. 实现了 List 接口,表明该容器类可以存放相同的元素,并且能够保证元素的有序。

ArrayList的主要特点可以总结如下:

  1. ArrayList是可以动态增长和缩减的索引序列,它是基于Object[] 数组实现的List类。

  2. 该类封装了一个动态再分配的Object[] 数组,每一个类对象都有一个capacity属性,表示它们所封装的Object[]数组的长度,当向ArrayList中添加元素时,该属性值会自动增加。如果想ArrayList中添加大量元素,可使用ensureCapacity方法一次性增加capacity,可以减少增加重分配的次数提高性能。

  3. ArrayList的用法和Vector相类似,但是Vector是一个较老的集合,具有很多缺点,不建议使用。另外,ArrayList和Vector的区别是:ArrayList是线程不安全的,当多条线程访问同一个ArrayList集合时,程序需要手动保证该集合的同步性,而Vector则是线程安全的。

  4. ArrayList不是线程安全的,只能用在单线程环境下,多线程环境下可以考虑用Collections.synchronizedList(List list)函数返回一个线程安全的ArrayList类,也可以使用concurrent并发包下的CopyOnWriteArrayList 类。

  5. ArrayList实现了Serializable接口,因此它支持序列化,能够通过序列化传输,实现了RandomAccess接口,支持快速随机访问,实际上就是通过下标序号进行快速访问,实现了Cloneable接口,能被克隆。

增删慢:每次删除元素,都需要更改数组的长度,拷贝以及移动元素的位置

查询快:由于数组在内存中是一块连续的空间,因此可以根据索引快速获取某个位置上的元素。

1、ArrayList底层数据结构

通过观察源代码可以看到ArrayList底层是基于一个Object[] 数组实现的。代码如下:

transient Object[] elementData; // non-private to simplify nested class access

 

一个对象只要实现了Serilizable接口,这个对象就可以被序列化,java的这种序列化模式为我们提供了很多便利,我们可以不必关心具体序列化的过程,只要这个类实现了Serilizable接口,这个类的所有属性和方法都会自动序列化。

但是我们常常会遇到这样的问题,这个类的有些属性需要序列化,而其他属性不需要被序列化,这时transient关键字为我们提供了便利,你只需要实现Serilizable接口,将不需要序列化的属性前添加关键字transient,序列化对象的时候,这个属性就不会序列化到指定的目的地中。

1)一旦变量被transient修饰,变量将不再是对象持久化的一部分,该变量内容在序列化后无法获得访问。

2)transient关键字只能修饰变量,而不能修饰方法和类。注意,本地变量是不能被transient关键字修饰的。变量如果是用户自定义类变量,则该类需要实现Serializable接口。

3)被transient关键字修饰的变量不再能被序列化,一个静态变量不管是否被transient修饰,均不能被序列化。

数据结构图

说明:底层的数据结构就是数组,数组元素类型为Object类型,即可以存放所有类型数据。我们对ArrayList类的实例的所有的操作底层都是基于数组的。

优点

由于底层实现是基于数组,支持随机访问,查找效率为O(1)

1、可以根据下标遍历元素效率较高。

2、可以根据下标访问元素效率较高。

3、在数组的基础上封装了对元素操作的方法。

4、可以自动扩容。

缺点

插入和删除操作需要移动所有受影响的元素,效率相对较低

1、插入和删除的效率比较低。

2、根据内容查找元素的效率较低。

适用场景

根据ArrayList的底层数据结构特点,ArrayList一般适用于查询多,增删操作少的场景下。

2、底层源码分析

0.成员变量

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    // 版本号 序列化相关,Java序列化的机制是通过判断类的serialVersionUID来验证的版本一致的
    private static final long serialVersionUID = 8683452581122892189L;
    // 缺省容量
    private static final int DEFAULT_CAPACITY = 10;
    // 空对象数组
    private static final Object[] EMPTY_ELEMENTDATA = {};
    // 缺省空对象数组
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    // 实际存储元素数组
    transient Object[] elementData;
    // 实际元素大小,默认为0
    private int size;
    // 最大数组容量
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
}

1.构造方法

无参构造

// 用法
ArrayList<String> list = new ArrayList<>();

// 源码
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

 

 

当我们使用一个无参的 ArrayList构造方法创建的时候,内部使用了一个空的数组赋值给了用于保存数据的数组。

指定初始容量

// 用法
ArrayList<String> list = new ArrayList<>(6);

// 源码
public ArrayList(int initialCapacity) {
  // 如果指定初始容量大于 0,则将按照指定容量初始化elementData数组
  if(initialCapacity > 0) {
    this.elementData = new Object[initialCapacity];
  }
  // 如果指定初始容量等于 0,则将按照默认容量初始化elementData数组
  else if(initialCapacity == 0) {
    this.elementData = EMPTY_ELEMENTDATA;
  }
  // 如果指定初始容量小于 0 抛出IllegalArgumentException异常
  else {
    throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
  }
}

 

 

该构造函数可以传入一个 int 值,如果该值大于 0,则创建一个长度为该值的数组; 如果该值等于 0,则使用一个空数组;如果该值小于 0,则抛出IllegalArgumentException异常。

指定一个集合

// 用法
ArrayList<String> arrayList = new ArrayList<>();
arrayList.add("YJS");
ArrayList<String> list = new ArrayList<>(arrayList);

// 源码
public ArrayList(Collection <? extends E > c) {
  // 将参数集合转换成数组并且赋值给elementData数组
  elementData = c.toArray();
  // 将elementData的长度赋值给成员变量size,如果参数集合元素不为空
  if((size = elementData.length) != 0) {
    // 数组的创建和拷贝
    if(elementData.getClass() != Object[].class) 
      elementData = Arrays.copyOf(elementData, size, Object[].class);
  }
  // 如果传入的集合为空,则将使用默认空数组
  else {
    this.elementData = EMPTY_ELEMENTDATA;
  }
}

 

 

该构造函数可以传入一个 Collection,将传入的集合转换为数组,然后将该数组赋值给成员变量elementData,将elementData的长度赋值给成员变量 size,判断是否不等于 0 ,如果传入的集合中有元素该判断是成立的,然后再判断elementData.getClass() != Object[].class,成立则将会进行数组的创建和拷贝。如果等于零则将EMPTY_ELEMENTDATA赋值给 elementData。

2.添加元素原理分析

示例源码

我这里使用的是无参构造器创建的ArrayList集合,也就是说初始容量为空。

public static void main(String[] args) {
    ArrayList arrayList = new ArrayList();
    arrayList.add(0);
    arrayList.add("java");
    arrayList.add("yjs");
    System.out.println("arrayList= " + arrayList);
}

 

 

初始化ArrayList

ArrayList arrayList = new ArrayList();执行后,会自动调用ArrayList的无参构造方法。

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

调用add(E e) 方法

在每次添加数据时,如果数据是基本数据类型,会先将基本数据类型进行装箱操作,把基本数据类型转换成对应的包装类型(引用数据类型),最终add(E e) 会向数组末尾添加一个元素。

/**
 * 将基本数据类转换为引用数据类型
 * @param  i 	传入的参数为一个基本型数据类型
 * @return 		返回的参数是一个基本数据类型的包装类(引用数据类型)
 */
public static Integer valueOf(int i) {
    if (i >= IntegerCache.low && i <= IntegerCache.high)
        return IntegerCache.cache[i + (-IntegerCache.low)];
    return new Integer(i);
}

 

 

如果是引用数据类型的话会直接去调用ArrayList的add(E e)方法,源码如下:

public boolean add(E e) {
    // 确保数组已使用长度(size)加1之后足够存下 下一个数据
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 数组的下一个位置存放传入元素,同时将size后移
    elementData[size++] = e;
    // 始终返回true
    return true;
}

 

 

调用ensureCapacityInternal(size + 1);方法,该方法的作用是确保数组的长度加1后内存是充足的,就是说保证能够数组还能存放一个元素。

ensureCapacityInternal()

ensureCapacityInternal(int minCapacity)方法保证存在剩余空间存放要添加的元素。

/**
	1、如果调用的是空参数构造函数:比较初始容量和所需最小容量的大小,并返回较大的
	2、如果调用的带参数构造函数:直接返回最小容量(size+1)
**/
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    /**
    	如果ArrayList创建对象时调用的是空参数构造函数:
    	第一次调用add()方法添加元素时:会在这儿将数组的容量初始化为10
    	随后调用add()方法添加元素时:会比较添加该元素所需的最小容量minCapacity和10的大小,返回大的	 
    */
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
	/**
		如果ArrayList创建对象时调用的为带参构造函数:直接返回最小容量minCapacity = size+1
	*/
    return minCapacity;
}

private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // 如果 minCapacity(即size+1当前需要的最小容量) > elementData.length(数组的容量),需要扩容
    // 使得存在剩余的数内存存放要添加的元素
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

 

 

调用calculateCapacity(elementData, minCapacity)计算添加一个元素所需的最小容量minCapacity;根据ArrayList创建对象时使用的构造方法分为两种情况:

  • 如果使用空参数构造函数创建ArrayList对象,会在第一次调用add()方法添加元素时,将数组的容量初始化为10,随后每次调用add()方法添加元素时都会比较初始容量10与minCapacity的大小,并返回大的容量。

  • 如果使用带参构造函数创建ArrayList对象,会直接但是minCapacity。

调用ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));该方法就是ensureCapacityInternal(size + 1)方法的底层,其作用是确保数组的长度加1后内存是充足的,就是说保证能够数组还能存放一个元素。

若添加一个元素所需的最小容量minCapacity大于数组的长度if (minCapacity - elementData.length > 0)那么就需要扩容,此时就会调用扩容方法:grow(int minCapacity)

grow()

这个方法完成了ArrayList()集合进行扩容的真正实现,源码如下:

private void grow(int minCapacity) {
    // 获取数组原有的容量
    int oldCapacity = elementData.length;
    
    // 扩容1.5倍(将数组的容量扩容1.5倍)
    // 进行右移一位,也就是除 2的 1 次方
    // 假如 oldCapacity 现在为 12 
    // newCapacity = 12 + (12/2) = 18
    // 也可以理解新容量为 为旧的容量的1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    
    // 如果扩展为1.5倍后还不满足需求,则直接扩展为需求值
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    
    // 检查扩容后的容量是否大于最大容量
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    
    // 申请一块更大内存容量的数组,将原来数组中的元素挪到这个新数组中,同时将elementData指向这个新数组
    // 原来的旧的数组由于没有引用变量指向他,就会被垃圾回收机制回收掉
    elementData = Arrays.copyOf(elementData, newCapacity);
}

 

 

调用 grow(int minCapacity)方法,该方法会对数组容量进行扩容。

在扩容时会申请一块更大内存容量的数组,将原来数组中的元素拷贝到这个新的数组中,同时让elementData指向该数组,而原来的数组由于没有新的指针指向它,就会被垃圾回收机制回收。

在扩容时,首先考虑扩容1.5倍(如果扩容的太大,可能会浪费更多的内存,如果扩容的太小,又会导致频繁扩容,申请数组拷贝元素等对添加元素的性能消耗较大,因此1.5倍刚好)。如果扩容1.5倍还是内存不足,就会直接扩容到添加元素所需的最小的容量。同时不能超过数组的最大容量Integer.MAX_VALUE - 8

hugeCapacity()

// 用来赋最大值。
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    // 如果minCapacity都大于MAX_ARRAY_SIZE,那么就Integer.MAX_VALUE返回,反之将MAX_ARRAY_SIZE返回。因为maxCapacity是三倍的minCapacity,可能扩充的太大了,就用minCapacity来判断了。
    // Integer.MAX_VALUE:2147483647   MAX_ARRAY_SIZE:2147483639  也就是说最大也就能给到第一个数值。还是超过了这个限制,就要溢出了。相当于arraylist给了两层防护。
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
    MAX_ARRAY_SIZE;
}

 

 

总结

3、其他方法源码分析

1.add(int index, E element)

向数组的指定位置添加元素。

public void add(int index, E element) {
    // 首先判断索引是否越界
    rangeCheckForAdd(index);

    // 确保数组size+1之后能够存下 下一个数据
    ensureCapacityInternal(size + 1); 

    /**
    	源数组 elementData 从传入形参index处开始复制,复制size-index个元素
    	目标数组 elementData 从index+1处开始粘贴,粘贴从源数组赋值的元素
    **/
    System.arraycopy(elementData, index, elementData, index + 1,size - index);

    // 把index处的元素替换成新的元素。
    elementData[index] = element;

    // 将size后移
    size++;
}

// 判断索引是否越界
private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

// 这是一个本地方法,由C语言实现。
public static native void arraycopy(Object src,  // 源数组
                                    int  srcPos, // 源数组要复制的起始位置
                                    Object dest, // 目标数组(将原数组复制到目标数组)
                                    int destPos, // 目标数组起始位置
                                    int length   // 复制源数组的长度
                                   );

 

 

2.set(int index, E element)

设置index位置处的元素。

public E set(int index, E element) {
    // 检查下标是否越界
    rangeCheck(index);
	
    //记录index位置处的旧值
    E oldValue = elementData(index);
    //将数组index索引处的元素设置为新值element
    elementData[index] = element;
    //返回旧值
    return oldValue;
}

//判断索引越界
private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

 

 

3.get(int index)

获取指定索引位置处的元素。

public E get(int index) {
    //判断索引越界
    rangeCheck(index);
    //返回指定索引位置处的元素
    return elementData(index);
}

 

 

4.remove(int index)

删除指定索引位置的数组元素。

//删除该列表中指定位置的元素,将所有后续元素转移到前边(将其中一个元素从它们中减去指数)
public E remove(int index) {
    //判断索引越界
    rangeCheck(index);

    modCount++;
    //获取index位置处的旧值
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    if (numMoved > 0)
        /**
            源数组 elementData 从传入形参index+1处开始复制,复制size-index-1个元素
            目标数组 elementData 从index处开始粘贴,粘贴从源数组赋值的元素
        */
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    //将size减1指向最后一个元素位置,再将最后一个位置清空
    elementData[--size] = null; 

    return oldValue;
}

// 这是一个本地方法,由C语言实现。
public static native void arraycopy(Object src,  // 源数组
									int  srcPos, // 源数组要复制的起始位置
                                    Object dest, // 目标数组(将原数组复制到目标数组)
                                    int destPos, // 目标数组起始位置
                                    int length   // 复制源数组的长度
                                    );

 

 

4、常见面试题

1.说一说 ArrayList。

ArrayList是List接口的常用实现类,并且是容量可变的线程不安全列表,底层使用Object[]数组实现,支持对元素的快速随机访问,但插入与删除速度很慢。集合扩容时会创建更大的数组,把原有数组复制到新数组。ArrayList 实现了 RandomAccess 标记接口,如果一个类实现了该接口,那么表示使用索引遍历比迭代器更快。

通过查看源码可以发现实际上 RandomAccess 接口中什么都没有定义。所以, RandomAccess 接口不过是一个标识罢了。 标识实现这个接口的类具有随机访问功能,也就是表示使用索引遍历比迭代器更快。

具体应用比如在 binarySearch() 方法中,它要判断传入的 list 是否 RamdomAccess 的实例,如果是,调用indexedBinarySearch()方法,如果不是,那么调用iteratorBinarySearch()方法。

elementData是 ArrayList 的数据域,被 transient 修饰,序列化时会调用 writeObject 写入流,反序列化时调用 readObject 重新赋值到新对象的 elementData。原因是 elementData 容量通常大于实际存储元素的数量,所以只需发送真正有实际值的数组元素。

size 是当前实际大小,elementData 大小大于等于 size。

modCount记录了 ArrayList 结构性变化的次数,继承自 AbstractList。所有涉及结构变化的方法都会增加该值。expectedModCount 是迭代器初始化时记录的 modCount 值,每次访问新元素时都会检查 modCount 和 expectedModCount 是否相等,不相等就会抛出异常。这种机制叫做 fail-fast,所有集合类都有这种机制。

2.ArrayList 和 LinkedList 的区别

  1. 底层数据结构

    ArrayList 底层使用的是 Object[] 数组,存储空间是连续的;LinkedList 底层使用的是双向链表数据结构(JDK1.6 之前为循环链表,JDK1.7 取消了循环。) 存储空间是不连续的。

  2. 插入和删除是否受元素位置的影响

    • ArrayList 底层采用数组存储,所以插入和删除元素的时间复杂度受元素位置的影响。 比如:执行add(E e)方法的时候, ArrayList 会默认在将指定的元素追加到此列表的末尾,这种情况时间复杂度就是 O(1)。但是如果要在指定位置 i 插入和删除元素的话(add(int index, E element))时间复杂度就为 O(n-i)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作。

    • LinkedList 底层采用链表存储,所以,如果是在头尾插入或者删除元素不受元素位置的影响(add(E e)、addFirst(E e)、addLast(E e)removeFirst()removeLast()),近似 O(1),如果是要在指定位置 i 插入和删除元素的话(add(int index, E element)) 时间复杂度近似为 O(n) ,因为需要先移动到指定位置再插入。

      • 对于随机访问get 和 set ,ArrayList 优于 LinkedList,因为 LinkedList 要移动指针。

      • 对于新增和删除操作 add 和 remove ,LinedList 比较占优势,因为 ArrayList 要移动数据。

  3. 是否支持快速随机访问

    LinkedList 不支持高效的随机元素访问,而 ArrayList 支持。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index)方法)。

  4. 是否保证线程安全

    ArrayList 和 LinkedList 都是不同步的,也就是不保证线程安全;

  5. 内存空间占用

    ArrayList 的空间浪费主要体现在在List列表的结尾会预留一定的容量空间,而 LinkedList 的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间(因为要存放直接后继和直接前驱以及数据)。

    同样的数据量 LinkedList 所占用空间可能会更小,因为 ArrayList 需要预留空间便于后续数据增加,而 LinkedList 增加数据只需要增加一个节点。

 

3.Arraylist 和 Vector 的区别

  • ArrayList 是 List 的主要实现类,底层使用 Object[]存储,适用于频繁的查找工作,线程不安全 ;

  • Vector 是 List 的古老实现类,底层使用Object[] 存储,线程安全的。

4.简单说一下ArrayList的扩容

扩容可分为两种情况:

  • 第一种情况,当ArrayList的容量为0时,此时添加元素的话,需要扩容,三种构造方法创建的ArrayList在扩容时略有不同:

    1.无参构造,创建ArrayList后容量为0,添加第一个元素后,容量变为10,此后若需要扩容,则正常扩容。

    2.传容量构造,当参数为0时,创建ArrayList后容量为0,添加第一个元素后,容量为1,此时ArrayList是满的,下次添加元素时需正常扩容。

    3.传列表构造,当列表为空时,创建ArrayList后容量为0,添加第一个元素后,容量为1,此时ArrayList是满的,下次添加元素时需正常扩容。

  • 第二种情况,当ArrayList的容量大于0,并且ArrayList是满的时,此时添加元素的话,进行正常扩容,每次扩容到原来的1.5倍。

 

 

微信关注

编程那点事儿

编程那点事儿

阅读剩余
THE END