1、ArrayList源码解析

1 概述

  1. ArrayList实现了List接口,是 顺序容器,允许放入null元素
  2. 有一个容量(capacity),表示底层数组的实际大小。如果容量不足,容器会 自动增大底层数组的大小
  3. 支持泛型,泛型擦除后,容器的元素都是 Object类型
  4. ArrayList没有实现同步(synchronized),因此它是 线程不安全的。(vector线程安全)
  5. 关于数组:一旦数组初始化完成,则长度不可改变 因此ArrayList扩容时会涉及数组的拷贝

2 底层数据结构

两个重要成员变量

  1. Object[] elementData

存储列表元素的数组;该数组的长度就是列表的容量
列表的容量是指它所能存储元素的最大个数

  1. size

列表的大小。指当前列表包含的元素个数,跟容量不是一个概念

size 跟 elementData数组长度是不一样的。elementData 允许长度大于元素的个数

    transient Object[] elementData; //存储列表元素的数组     private int size;//元素的数量     protected transient int modCount = 0; //list的修改次数 

3 构造函数

有三个构造函数:

  • 指定初始容量大小时,创建一个容量为参数的Object数组,并赋值给数据数组
  • 不指定初始容量大小时,数据数组赋值为一个无限容量的空数组
  • 构造参数为集合类型,将参数转换成Object类型数组,并赋值给数据数组
  • 注意,只有当第一次add元素时,才会指定数组的长度

参照源码:

    //指定初始容量大小时,创建一个容量为参数的Object数组,并赋值给数据数组     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() {         this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;     } // 构造参数为集合类型,将参数转换成Object类型数组,并赋值给数据数组     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;         }     }  

4 自动扩容

  1. 添加元素时,会判断添加后是否超出当前数组长度,超出则会执行数组扩容;
  2. 数组扩容时,会将老数组中的元素重新 拷贝一份到新的数组中。(因为数组长度不可变,因此需要创建新数组)
  3. 数组执行扩容,扩容后的容量为扩容前的 1.5倍
  4. 尽可能评估所需要容量的大小,避免扩容。(因为扩容占用更多的内存)

参考源码:

重点!!!!!:添加前,都判断是否需要扩容:(如果size+1后,超过elementData的长度,则执行扩容,扩容为原来的1.5倍

 public boolean add(E e) {     ensureCapacityInternal(size + 1);  // size 初始化时是0,     elementData[size++] = e;     return true; }  private void ensureCapacityInternal(int minCapacity) {     ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); }  //计算所需容量:第一次添加时,容量为10;反则,容量为当前长度+1 private static int calculateCapacity(Object[] elementData, int minCapacity) {     if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {         return Math.max(DEFAULT_CAPACITY, minCapacity);//DEFAULT_CAPACITY = 10,即第一次添加时,数组长度变为10     }     return minCapacity;//如果数组不为空时,最小长度是当前长度+1 }  //再次计算数组所需容量 private void ensureExplicitCapacity(int minCapacity) {     modCount++;//列表修改次数递增     //所需容量大于数组的长度,则执行扩容     if (minCapacity - elementData.length > 0)         grow(minCapacity); } //扩容,数组的内存状态已经发生变化了 private void grow(int minCapacity) {     int oldCapacity = elementData.length;     int newCapacity = oldCapacity + (oldCapacity >> 1);//  新的长度为旧长度的1.5倍  【右移1位(除以2)】     if (newCapacity - minCapacity < 0)  // 如果扩容后的长度小于所需要的最小长度,则使用最小长度(基本不会发生)         newCapacity = minCapacity;     if (newCapacity - MAX_ARRAY_SIZE > 0)  //这里是极限的情况,即逼近数组分配的最大内存空间         newCapacity = hugeCapacity(minCapacity);     elementData = Arrays.copyOf(elementData, newCapacity);  // 执行数组拷贝 } 

5 set() get() remove()

  • set()方法也就变得非常简单,直接对数组的指定位置赋值即可。
public E set(int index, E element) {     rangeCheck(index);//下标越界检查     E oldValue = elementData(index);     elementData[index] = element;//赋值到指定位置,复制的仅仅是引用     return oldValue;//返回原先位置上的元素 } 
  • get()方法同样很简单,唯一要注意的是由于底层数组是Object[],得到元素后需要进行类型转换。
public E get(int index) {     rangeCheck(index);     return (E) elementData[index];//注意类型转换 } 
  • remove()方法也有两个版本,一个是remove(int index)删除指定位置的元素,另一个是remove(Object o)删除第一个满足o.equals(elementData[index])的元素。删除操作是add()操作的逆过程,需要将删除点之后的元素向前移动一个位置。需要注意的是为了让GC起作用,必须显式的为最后一个位置赋null值
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);     elementData[--size] = null; //清除该位置的引用,让GC起作用     return oldValue; }  

6 Fail-Fast机制

ArrayList也采用了快速失败的机制,通过记录 modCount 参数来实现。在面对并发的修改时,迭代器很快就会完全失败,而不是冒着在将来某个不确定时间发生任意不确定行为的风险。

发表评论

相关文章