关于java:面试官你说你精通源码那你知道ArrayList-源码的设计思路吗

Arraylist 源码剖析

ArrayList 咱们简直每天都会应用到，然而通常状况下咱们只是晓得如何去应用，至于其外部是怎么实现的咱们不关怀，然而有些时候面试官就喜爱问与 ArrayList 的源码相干的问题，明天咱们就来看看和 ArrayList 源码相干的问题。

一：整体架构

1.1、ArrayList 构造

ArrayList 整体架构比较简单，就是一个数组构造，比较简单，如下图：

图中展现是长度为 n 的数组，index 示意数组的下标，从 0 开始计数，elementData 示意数组自身，源码中除了这两个概念，还有以下三个基本概念：

1. DEFAULT_CAPACITY，示意数组的初始大小，默认是 10；
2. size，以后数组的大小，没有应用 volatile 润饰，非线程平安的；
3. modCount，统计以后数组被批改的版本次数；

1.2、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、复杂度剖析

2.5、线程平安

咱们须要强调的是，只有当 ArrayList 作为共享变量时，才会有线程平安问题，当 ArrayList 是办法内的局部变量时，是没有线程平安的问题的。

ArrayList 有线程平安问题的实质，是因为 ArrayList 本身的 elementData、size、modConut 在进行各种操作时，都没有加锁，而且这些变量的类型并非是可见（volatile）的，所以如果多个线程对这些变量进行操作时，可能会有值被笼罩的状况。

类正文中举荐咱们应用 Collections#synchronizedList 来保障线程平安，SynchronizedList 是通过在每个办法下面加上锁来实现，尽管实现了线程平安，然而性能大大降低。

三：总结

从下面 ArrayList 的局部源码的剖析中，咱们能够发现 ArrayList 底层其实就是围绕数组构造，各个 API 都是对数组的操作进行封装，让使用者无需感知底层实现，只需关注如何应用即可。

最初

感激你看到这里，看完有什么的不懂的能够在评论区问我，感觉文章对你有帮忙的话记得给我点个赞，每天都会分享 java 相干技术文章或行业资讯，欢送大家关注和转发文章！