龙空技术网

ArrayList源码解析

一缕82年的清风 489

前言:

此刻大家对“链表的实现之增删功能”大体比较关怀,小伙伴们都想要剖析一些“链表的实现之增删功能”的相关内容。那么小编同时在网络上网罗了一些对于“链表的实现之增删功能””的相关文章,希望大家能喜欢,朋友们快快来了解一下吧!

ArrayList是我们使用频率非常高的一个集合,也是集合中相对比较简单的集合。是List接口的主要实现类。一般面试的时候经常会问到ArrayList和LinkedList的区别。

ArrayList: 底层是数组实现的,查找快,增删慢。

LinkedList: 底层是链表实现的,增删快,查找慢。

一.类结构

ArrayList是集合的一种,集合的最顶端抽象接口为Collection, Collection下面又有两个子接口,一个是List,一个是Set, List和Set的区别也经常别被问到。

List: 数据是有序的,可以根据序号获取元素,List中的数据是可以重复的

Set: 数据是无序的,并且数据是不可重复的(是否重复是根据hashCode和equals方法结果决定)

List下的常用子类为: ArrayList, LinkedList, Vector.

Set下的常用子类: HashSet.

上面说的结构只是对List结构的一个简单描述。一个相对完成的类结构图如下:

这里可以更加清晰的看出ArrayList的结构,其中最主要的就是实现了List接口。那么我们简单的列一下List接口中 都有哪些方法。

    int size();        boolean isEmpty();     boolean contains(Object o);     Iterator<E> iterator();     Object[] toArray();     <T> T[] toArray(T[] a);     boolean add(E e);     boolean remove(Object o);     boolean containsAll(Collection<?> c);     boolean addAll(Collection<? extends E> c);     boolean addAll(int index, Collection<? extends E> c);     boolean removeAll(Collection<?> c);     void clear();     boolean equals(Object o);     int hashCode();     E get(int index);     E set(int index, E element);     void add(int index, E element);     E remove(int index);     int indexOf(Object o);     int lastIndexOf(Object o);     ListIterator<E> listIterator();     ListIterator<E> listIterator(int index);     List<E> subList(int fromIndex, int toIndex);

这你我把一些默认方法去掉了,因为看起来有点乱,其余的就是ArrayList中需要实现的方法了。这里边的大部分方法,我相信大家应该都使用过。而由于List是有序的,有序的意思就是我们可以通过编号来操作集合中的元素,所以上面有很多的方法都是可以传入 index参数的,就是直接根据编号来操作集合。

二. 构造方法

ArrayList中的构造方法总共有三个。其中两个应该是我们经常使用的。

public ArrayList(int initialCapacity); public ArrayList(); public ArrayList(Collection<? extends E> c);复制代码

这相当于我们可以通过三种方式来构建一个ArrayList集合

public class Test{    public static void main(String[] args){    // 无参构造    List<String> list1 = new ArrayList<>();        // 传入初始化容量    List<String> list2 = new ArrayList<>(3);        // 传入一个集合    List<String> list3 = new ArrayList<>(list1);      }}

这里边第一种方式应该是我们最长使用的,当然也是最不负责任的。第二种方式是编码规范的要求我们这么写的,传入一个初始化的容量。这么做的目的主要是防止向集合中添加数据时,由于集合扩容导致的性能下降问题。所以建议我们在创建集合的时候,最好就根据我们的需求,合理分配出集合的容量大小。第三种是直接传入一个Collection ,要注意,是一个Collection ,也就是List也行,Set也行,这种方法会把Collection直接转为数组,存储到创建的集合中。

三. ArrayList原理

介绍完了这几个构造方法,我们先来讲讲ArrayList的原理。

Q1:ArrayList为什么可以存储元素?

其实他的本质就是一个Object[] , 我们每次向List中添加一个元素,他都会把元素存储到他的一个Object[] 中。那么问题是,我创建一个多大的数组合适呢? 这就涉及到了一个概念叫做 容量 (Capacity) ,所以刚刚的第二种构造方法,传入一个初始化的数组容量,就是代表我的Object[] 的初始化大小是多少。比如我传入了一个10, 那就代表创建了一个10个长度的Object[].

Q2: 如果存储的数据超出了Object[]的长度范围改怎么办?

假设我们通过List list = new ArrayList(10); 指定了集合的初始化长度,那我们向里边添加的元素个数可以超过10个么。答案是肯定的,也就是我们添加超过10个元素的时候,集合也不会报错,原因是什么的,就是ArrayList的自动扩容原理。当我们向集合中添加元素的时候,集合首先会判断当前的数组容量能否容纳得下所需添加的元素,如果容纳不下,就会触发自动扩容机制。而自动扩容机制的核心原理就是创建一个更大的Object[] ,然后将原来的数组中的元素拷贝到这个更大的数组中来,而往往这个过程是比较影响性能的,尤其是集合中的数据量很大的时候,所以我们前面提到了,尽量直接指定数据的容量(在我们可以判断所需大小的时候),目的就是为了减少他的自动扩容,提升效率。

Q3: capacity和size的区别?

这个概念很重要,大家一定要搞清楚这两个概念的区别,才能够更好地理解集合。

先说capcity, 我们上面提到了,他指的就是我用来存储数据的数组的大小。而size只的是集合中存入的元素个数。

什么意思呢,比如我capacity是10,就代表我的集合中数组的长度是10个,然后我向集合中add一个元素,那么size就是1。 size代表的是集合中存储的元素的真正个数。 当集合中的size即将超过capacity的时候,就会出发集合的扩容操作,capacity会继续增大。

Q4: ArrayList的扩容机制*

这个也是面试中会经常别问到的话题,集合的默认容量是多少,什么时候触发扩容,扩成了多大等等,接下来我们就来详细的分析一下。

1. 首先介绍一下ArrayList类中的五个核心成员变量。

public class ArrayList<E> extends AbstractList<E>        implements List<E>, RandomAccess, Cloneable, java.io.Serializable{    private static final long serialVersionUID = 8683452581122892189L;     // 默认容量    private static final int DEFAULT_CAPACITY = 10;    // 空数组,当capacity = 0是使用的    private static final Object[] EMPTY_ELEMENTDATA = {};     // 空数组,无参构造方法使用    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};    // 核心数组,用于存储数据    transient Object[] elementData; // non-private to simplify nested class access    // 集合中实际元素个数      private int size;}

这几个成员变量都是非常重要的。首先我们先来介绍一下这里有两个空的Object数组。一个是EMPTY_ELEMENTDATA,还有一个DEFAULTCAPACITY_EMPTY_ELEMENTDATA。

2. EMPTY_ELEMENTDATA 和 DEFAULTCAPACITY_EMPTY_ELEMENTDATA区别

这两个都是空数组,为什么要定义两个呢,有什么区别的?其实在注解中已经给出了解释。

这里在解释一下。其实主要区别就是这样的两个集合。

List list1 = new ArrayList(0); List list2 = new ArrayList();复制代码

这两种集合,第一种情况,集合中的数组使用的就是EMPTY_ELEMENTDATA, 第二种情况使用的是DEFAULTCAPACITY_EMPTY_ELEMENTDATA。 我们也可以通过代码清晰的看出来。

主要就是对应有参构造方法中的0,和无参构造方法。

那么为什么非要用两个集合呢。主要原因在于,使用无参构造的集合(上述示例中的list2)是要扩容为默认长度(10)的数组,而指定长度的数组是不需要默认长度的。所以要用两个集合。详见计算容量的方法:

这里要注意一下,我是用的JDK8的代码和JDK7略有区别。就是数组在什么时候开辟空间。从jdk8开始,集合不是你new完了就把空间创建出来的,从代码也可以看出来,我们new完的集合(0参和无参),实际上就给了一个空数组,只有当我们向集合中添加元素的时候,才会根据长度初始化数组的长度。这样做的目的实际就是一个懒加载的思想,避免内存的浪费。

3. 扩容到底扩多大

那么接下来我们就来研究下,扩容到底扩成多大。先总结下我们创建数组的构造方法:

// 初始化了一个空数组 DEFAULTCAPACITY_EMPTY_ELEMENTDATAList list1 = new ArrayList(); // 初始化了一个空数组: EMPTY_ELEMENTDATAList list2 = new ArrayList(0); // 初始化了一个10个长度的数组List list3 = new ArrayList(10);复制代码

而当我们向list1中添加元素的时候,就会将其初始化成默认的长度,也就是10.

// 默认容量private static final int DEFAULT_CAPACITY = 10;复制代码

那么什么时候扩容呢: 看源码:

public boolean add(E e) {  ensureCapacityInternal(size + 1);  // Increments modCount!!  elementData[size++] = e;  return true;}复制代码

添加元素的时候,会使用size+1的值去计算是否需要扩容:

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

此时的minCapacity 的值就是 size + 1; 调用calculateCapacity 得出所需容量

private static int calculateCapacity(Object[] elementData, int minCapacity) {    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {      return Math.max(DEFAULT_CAPACITY, minCapacity);    }    return minCapacity;}

这个时候就比较重要了, 当我们的集合是通过无参构造初始化的时候,他的容量是当前size+1 和默认长度的最大值。也就是当我们向集合中添加元素的时候,如果元素个数小于10,那么这个结果就是10, 如果元素个数大于10了,就取当前的最大值。

private void ensureExplicitCapacity(int minCapacity) {        modCount++;         // overflow-conscious code        if (minCapacity - elementData.length > 0)            grow(minCapacity);}

如果通过上面得到的值已经大于数组的长度了,就代表数组已经装不下了,这时候就会调用grow方法进行扩容。

// 扩容核心方法private void grow(int minCapacity) {    // overflow-conscious code    int oldCapacity = elementData.length;    int newCapacity = oldCapacity + (oldCapacity >> 1);    if (newCapacity - minCapacity < 0)      newCapacity = minCapacity;    if (newCapacity - MAX_ARRAY_SIZE > 0)      newCapacity = hugeCapacity(minCapacity);    // minCapacity is usually close to size, so this is a win:    elementData = Arrays.copyOf(elementData, newCapacity);}

怎么扩的呢,新的容量为 :oldCapacity + (oldCapacity >> 1); 其实就是原长度的1.5倍,如果你原来是默认的10个长度,扩容后会变为15个。但是也不是最终结果。如果扩完的长度还不够,那么就要多长给多长了。如果扩完的长度大于 MAX_ARRAY_SIZE(这个值是int的最大值-8),就将数组扩容为int的最大值,如果minCapacity为负就代表内存溢出了。这里可能有人想不通,就是扩容后的长度怎么可能不够呢,要注意我们的集合操作不一定都是一个一个添加的,可以通过addAll方法添加一堆元素,那么此时就可能导致你扩容后还是装不下,那就直接初始化为所需长度。

private static int hugeCapacity(int minCapacity) {        if (minCapacity < 0) // overflow            throw new OutOfMemoryError();        return (minCapacity > MAX_ARRAY_SIZE) ?            Integer.MAX_VALUE :            MAX_ARRAY_SIZE;}

最后再把原来的数组中数据拷贝到新的数组里即可。扩容操作完毕。有点复杂,没懂的多读几遍。

这里基本上就已经是ArrayList中最核心的方法了。剩下的就是一下常用的api都比较好理解了。

四. 常见Api解读

掌握了核心原理,我们就再来读读其他的方法。就比较好理解了。

1. size() 方法,获取集合中元素个数,这里一定注意和capacity的区别。

// 就是一个get方法 public int size() {   return size; }

2. get方法和set方法

public E get(int index) {  rangeCheck(index);   return elementData(index);} public E set(int index, E element) {  rangeCheck(index);   E oldValue = elementData(index);  elementData[index] = element;  return oldValue;}

这里注意一下: 凡是跟index相关的方法,都会先校验一下index是否合法,否则会出现一个我们非常眼熟的异常:

private void rangeCheck(int index) {  if (index >= size)    throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}     private void rangeCheckForAdd(int index) {  if (index > size || index < 0)    throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}

3. addAll方法: 这个方法也涉及到扩容问题。跟上面的差不多:

public boolean addAll(Collection<? extends E> c) {        Object[] a = c.toArray();        int numNew = a.length;        ensureCapacityInternal(size + numNew);  // Increments modCount        System.arraycopy(a, 0, elementData, size, numNew);        size += numNew;        return numNew != 0;}

这里注意下,判断是否扩容的长度就是size + numNew; 单个的时候用的是 size + 1去判断是否扩容。

4. modCount解释:

我们在代码中会随处发现一个变量modCount,比如扩容的时候,remove的时候,set,clear等方法被调用的时候,都有一个modCount++;

这个变量是干什么用的呢,其实就是用来记录集合被操作的次数。记录这个东西有啥用的,主要就是在做序列化的时候,也就是往出写的时候。在ArrayList中有一个writeObject方法:

private void writeObject(java.io.ObjectOutputStream s)        throws java.io.IOException{        // Write out element count, and any hidden stuff        int expectedModCount = modCount;        s.defaultWriteObject();         // Write out size as capacity for behavioural compatibility with clone()        s.writeInt(size);         // Write out all elements in the proper order.        for (int i=0; i<size; i++) {            s.writeObject(elementData[i]);        }         if (modCount != expectedModCount) {            throw new ConcurrentModificationException();        }}

写的时候会判断前后的modCount是否一致,如果不一致代表对象被操作过,就会报ConcurrentModificationException。

5.indexOf方法: 返回对象在数组中的位置,这里是使用equals方法比较的:

public int indexOf(Object o) {  if (o == null) {    for (int i = 0; i < size; i++)      if (elementData[i]==null)        return i;  } else {    for (int i = 0; i < size; i++)      if (o.equals(elementData[i]))        return i;  }  return -1;}

这个应该比较好理解,就是遍历数组,查找对象,返回索引值。

6. clear方法:

public void clear() {        modCount++;         // clear to let GC do its work        for (int i = 0; i < size; i++)            elementData[i] = null;         size = 0;    }

将数组中所有元素置为null, size改为0

剩下的方法就不一一过了。 全篇代码中没有出现 synchronized关键字,也间接证明该类线程不安全

标签: #链表的实现之增删功能