Java容器之ArrayList源码分析(java arraylist原理)

  本篇文章为你整理了Java容器之ArrayList源码分析(java arraylist原理)的详细内容,包含有java arrays.sort源码 java arraylist原理 java arraylist vector java arraylist iterator Java容器之ArrayList源码分析,希望能帮助你了解 Java容器之ArrayList源码分析。

  ArrayList 是一种变长的集合类,底层是基于数组来实现的,所以 ArrayList 查询效率高、增删效率低

  ArrayList 集合中的元素是有序、可重复的,且可以存储 null 空值

  当每次向 ArrayList 容器中添加元素时,会进行容量检查:当往 ArrayList 中添加的元素数量大于其底层数组容量时,会通过扩容机制重新生成一个更大容量的数组,然后把旧数组上面的数据复制进新数组

  ArrayList 是线程不安全的。在并发环境下,多个线程同时操作 ArrayList,会引发不可预知的错误。所以在多线程环境下可以使用 concurrent 并发包下的 CopyOnWriteArrayList 类来替代 ArrayList 类,或者使用 Collections.synchronizedList(List l) 返回一个线程安全的 ArrayList 类

  

// 容器中真正存放元素的地方,使用 transient 是为了不序列化这个字段。elementData 数组的长度指的是容器的容量

 

  transient Object[] elementData;

  // 容器中真正存储的元素个数

  private int size;

  // 定义默认空容量的数组:当使用 new ArrayList() 创建容器时,会将这个空数组直接赋值给 elementData

  private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

  // 默认的容量大小:使用 new ArrayList() 创建容器后,并往容器中添加第一个元素时才会使用这个默认容量进行初始化

  private static final int DEFAULT_CAPACITY = 10;

  // 定义空容量的数组:当使用 new ArrayList(0) 创建容器时,会使用这个空数组

  private static final Object[] EMPTY_ELEMENTDATA = {};

  

 

  ArrayList()

  

// 无参的构造方法

 

  public ArrayList() {

   // 当直接创建ArrayList时,elementData被赋予了默认空容量的数组,此时ArrayList容器的容量是0

   this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;

  

 

  ArrayList(int)

  

// 传容量的构造方法:根据传入的数值大小,创建指定长度的数组

 

  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);

  

 

  当 initialCapacity 0 时,会在堆上 new 一个大小为 initialCapacity 的数组,然后将其引用赋给 elementData,此时 ArrayList 的容量为 initialCapacity,元素个数 size 为默认值 0

  当 initialCapacity = 0 时,elementData 被赋予了默认空数组,因为其被 final 修饰了,所以此时 ArrayList 的容量为 0,元素个数 size 为默认值 0

  当 initialCapacity 0 时,会抛出异常

  ArrayList(Collection)

  

// 传入Collection元素列表的构造方法

 

  public ArrayList(Collection ? extends E c) {

   Object[] a = c.toArray();

   if ((size = a.length) != 0) {

   if (c.getClass() == ArrayList.class) {

   elementData = a;

   } else {

   elementData = Arrays.copyOf(a, size, Object[].class);

   } else {

   // replace with empty array.

   elementData = EMPTY_ELEMENTDATA;

  

 

  将参数集合转化为一个 Object 类型的数组:

  如果参数集合转换为数组后的数组长度为 0,会初始化 elementData 为空数组,此时 ArrayList 的容量是 0,元素个数 size 为 0

  如果参数集合转换为数组后的数组长度不等于 0

  如果参数集合的类型是 ArrayList,则直接将参数赋值给 elementData

  否则,将参数数组的数组类型转换为 Object 对象数组的数组类型,并赋值给 elementData

  
public boolean add(E e) {

   // 添加元素之前,首先需要确定集合的容量(检测集合是否需要扩容)

   ensureCapacityInternal(size + 1);

   // 将指定元素插入容器尾部

   elementData[size++] = e;

   return true;

  // 确保容器内部的容量:即容器扩容的入口方法

  private void ensureCapacityInternal(int minCapacity) { // minCapacity是集合当前大小+1

   ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));

  // 计算并得到容器的最小容量

  private static int calculateCapacity(Object[] elementData, int minCapacity) {

   // 如果elementData是空数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA,则从size+1的值和默认值10中取最大值

   if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {

   return Math.max(DEFAULT_CAPACITY, minCapacity);

   // 如果elementData不为空数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA,则返回size+1

   return minCapacity;

  // 确保elementData数组的容量足够存放新加入的元素,若不够,要扩容

  private void ensureExplicitCapacity(int minCapacity) {

   // moCount是记录ArrayList被修改次数的,该变量主要是用来实现fail-fast机制

   modCount++;

   // 如果添加元素后的集合最小容量大于当前ArrayList内部数组的长度,就需要对内部数组elementData扩容

   if (minCapacity - elementData.length 0)

   grow(minCapacity);

  // 扩容的实际方法:该方法是用来确保ArrayList至少能存储minCapacity个元素

  private void grow(int minCapacity) {

   // 扩容前的elementData容量

   int oldCapacity = elementData.length;

   // 获取旧容量的1.5倍赋值给一个新容量变量(oldCapacity右移一位,等于除以二)

   int newCapacity = oldCapacity + (oldCapacity 1);

   if (newCapacity - minCapacity 0) // 如果扩容后的新容量比实际需要的容量还小,则以实际需要的容量为准

   newCapacity = minCapacity;

   if (newCapacity - MAX_ARRAY_SIZE 0) // 如果新容量超过容器支持的最大容量了,则使用最大容量

   newCapacity = hugeCapacity(minCapacity);

   // 使用 Arrays.copyOf() 方法将原数组的值拷贝到一个大小为newCapacity的新数组

   elementData = Arrays.copyOf(elementData, newCapacity);

  // 计算最大的容量

  private static int hugeCapacity(int minCapacity) {

   if (minCapacity 0) // 大小溢出

   throw new OutOfMemoryError();

   // 如果所需最小容量minCapacity大于数组最大的长度,则取Integer的最大值,否则取数组最大长度

   return (minCapacity MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;

  // 允许分配的最大数组大小

  private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

  

 

 

  add(int, E)

  

// 在集合指定索引 index 位置处插入指定元素 element

 

  public void add(int index, E element) {

   // 检查是否越界

   rangeCheckForAdd(index);

   // 检测是否需要扩容

   ensureCapacityInternal(size + 1);

   // 将 index 及其之后的所有元素都向后移一位

   System.arraycopy(elementData, index, elementData, index + 1, size - index);

   // 将新元素插入至index的位置

   elementData[index] = element;

   size++;

  private void rangeCheckForAdd(int index) {

   if (index size index 0)

   throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

  

 

  ArrayList 的扩容机制

  扩容可分为两种情况:

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

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

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

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

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

  不同于插入操作,ArrayList 没有无参删除方法。所以其只能删除指定位置的元素或删除指定元素,这样就无法避免移动元素(除非从元素序列的尾部删除)

  remove(int)

  

// 删除指定位置的元素

 

  public E remove(int index) {

   // 检查是否数组越界

   rangeCheck(index);

   // moCount是记录ArrayList被修改次数的,该变量主要是用来实现fail-fast机制

   modCount++;

   // 获取index索引处的元素

   E oldValue = elementData(index);

   int numMoved = size - index - 1;

   if (numMoved 0)

   // 如果 index 不是最后一位,则将 index + 1 及之后的元素向前移动一位,覆盖被删除值

   System.arraycopy(elementData, index + 1, elementData, index, numMoved);

   // 将最后一个元素置空,并将 size 值减 1

   elementData[--size] = null;

   // 返回旧值

   return oldValue;

  private void rangeCheck(int index) {

   if (index = size)

   throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

  E elementData(int index) {

   return (E) elementData[index];

  

 

  remove(Object)

  

// 删除指定元素:若元素重复,则只删除下标最小的元素

 

  public boolean remove(Object o) {

   if (o == null) {

   for (int index = 0; index size; index++)

   if (elementData[index] == null) {

   fastRemove(index);

   return true;

   } else {

   // 遍历数组,查找要删除元素的位置

   for (int index = 0; index size; index++)

   if (o.equals(elementData[index])) {

   fastRemove(index);

   return true;

   return false;

  private void fastRemove(int index) {

   // moCount是记录ArrayList被修改次数的,该变量主要是用来实现fail-fast机制

   modCount++;

   int numMoved = size - index - 1;

   if (numMoved 0)

   // 如果 index 不是最后一位,则将 index + 1 及之后的元素向前移动一位,覆盖被删除值

   System.arraycopy(elementData, index + 1, elementData, index, numMoved);

   // 将最后一个元素置空,并将 size 值减 1

   elementData[--size] = null;

  

 

  更新元素:set(int, E)

  

public E set(int index, E element) {

 

   rangeCheck(index); // 检查是否数组越界

   E oldValue = elementData(index); // 获取index索引处的旧值

   elementData[index] = element; // 将指定索引处的元素替换为 element

   return oldValue; // 返回旧值

  

 

  查询元素:get()

  

// 获取指定索引处的元素

 

  public E get(int index) {

   rangeCheck(index); // 检查是否越界

   return elementData(index); // 获取并返回index索引处的元素

  private void rangeCheck(int index) {

   if (index = size)

   throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

  E elementData(int index) {

   return (E) elementData[index];

  

 

  以上就是Java容器之ArrayList源码分析(java arraylist原理)的详细内容,想要了解更多 Java容器之ArrayList源码分析的内容,请持续关注盛行IT软件开发工作室。

郑重声明:本文由网友发布,不代表盛行IT的观点,版权归原作者所有,仅为传播更多信息之目的,如有侵权请联系,我们将第一时间修改或删除,多谢。

留言与评论(共有 条评论)
   
验证码: