《Java源码解析》集合框架List之ArrayList

Myth丶恋晨 2022-07-13 01:56 264阅读 0赞

Java的集合框架的底层实现在面试中用的比较多，接下来我就用一些时间来分析一下Java的集合框架中的List(ArrayList,LinkedList),Set(Set的各种实现类),Map(Hashtable、HashMap、ConcurrentHashMap)

对于集合框架我们的关注点一般在一下几点：  
1. 集合底层实现的数据结构是什么？  
2. 集合中元素是否允许为空？  
3. 是否允许重复的数据？  
4. 是否有序(这里的有序是指读取数据和存放数据的顺序是否一致)  
5. 是否线程安全。

下面先从List的实现类开始解读源码

# ArrayList #

## 1.首先看看 **ArrayList** 的继承体系的结构 ##

![ArrayList的类继承结构][ArrayList]

ArrayList主要是继承自AbstractList抽象类并实现了List接口、实现了Cloneable和Serializable接口使得ArrayList具有克隆和序列化的功能、实现了RandomAccess接口以实现随机访问的功能。

## 2.重要属性 ##

ArrayList中两个最重要的属性如下：

/**存放List中元素的数组*/
    private transient Object[] elementData;
    /**ArrayList中元素的数量*/
    private int size;

elementData数组用来存放List中的元素，可知ArrayList的底层是数组实现的，此外这里elementData是用transient修饰的，表示该变量不可序列化；size表示List中已存放的元素的容量。

此外还有三个重要的属性，其各自功能见源码注释：

//ArrayList默认的初始容量
    private static final int DEFAULT_CAPACITY = 10;
    //这是一个共享的空的数组实例
    private static final Object[] EMPTY_ELEMENTDATA = {};
    //元素数组的最大容量
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

## 3. 五个关注点在ArrayList上面的答案 ##

**ArrayList**

<table> 
 <thead> 
  <tr> 
   <th>关注点</th> 
   <th align="center">结论</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>集合底层实现的数据结构</td> 
   <td align="center">数组</td> 
  </tr> 
  <tr> 
   <td>集合中元素是否允许为空</td> 
   <td align="center">允许</td> 
  </tr> 
  <tr> 
   <td>是否允许重复的数据</td> 
   <td align="center">允许</td> 
  </tr> 
  <tr> 
   <td>是否有序</td> 
   <td align="center">有序</td> 
  </tr> 
  <tr> 
   <td>是否线程安全。</td> 
   <td align="center">非线程安全</td> 
  </tr> 
 </tbody> 
</table>

## 4. ArrayList的构造函数 ##

ArrayList有三个构造函数：

#### 1. 无参构造函数 ####

public ArrayList() {
        super();
        this.elementData = EMPTY_ELEMENTDATA;
    }

这个无参构造函数直接把EMPTY\_ELEMENTDATA传递给elementData属性。根据注释说明：构造一个初始容量为10的空列表。至于EMPTY\_ELEMENTDATA是什么时候初始化的，且看后面的分析。

#### 2. 指定初始容量的构造函数 ####

public ArrayList(int initialCapacity) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        //new一个指定容量的数组传递给elementData
        this.elementData = new Object[initialCapacity];
    }

#### 3. 使用传递的集合初始化List的构造函数 ####

public ArrayList(Collection<? extends E> c) {
        //将集合c转换成数组元素，然后传递给elementData
        elementData = c.toArray();
        //获取数组的大小，然后赋值给size
        size = elementData.length;
        //这里会进行判断elementData是否正确的被赋值
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    }

这里有一点值得注意的是最后一句：通过调用Arrays.copyOf()函数复制指定的数组，截取或用 null 填充（如有必要），以使副本具有指定的长度。我们进入这个函数发现这个函数主要是调用了System.arraycopy(),继续跟踪下去，发现这个函数是一个native方法。

## 5.ArrayList关键函数之add(E e) ##

源代码如下：

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

JDK对这个函数的解释是：在List的后面添加一个元素。  
在源码里面，首先调用如下函数  
`ensureCapacityInternal(size + 1);`  
这个函数主要是确保size+1不会导致数组越界，下面我们先看看这个函数里面的实现：

private void ensureCapacityInternal(int minCapacity) {
        if (elementData == EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        ensureExplicitCapacity(minCapacity);
    }

这是一个内部调用的private函数，这个函数里面又主要调用如下函数  
`ensureExplicitCapacity(minCapacity);`  
这个函数传入的参数是list的最小容量。而且这个函数也是private的，看看这个函数的源码：

private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        //这里判断当前List所需的容量大于elementData本身的容量，那么就调用grow()函数对数组扩容。
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

这里有个变量modCount是定义父类AbstractList中的  
`protected transient int modCount = 0;`  
这个变量的主要作用是修饰结构化的修改此List的次数。这里有个重要的函数`private void grow(int minCapacity)`需要分析,源代码如下：

private void grow(int minCapacity) {
        //获取elementData也就是List中本来的容量
        int oldCapacity = elementData.length;
        //oldCapacity的大约1.5倍赋值给新的newCapacity
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        //根据新的数组容量，调用接口扩容elementData
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

根据上述的源码注释，我们可以知道这个函数主要是将原来的list的大小扩大到现在的大约1.5倍。  
至此，add()函数中的第一行`ensureCapacityInternal(size + 1);`已经分析完毕，主要也就是在add元素的时候确保当前的list的容量可用。在add()函数中剩下的也就是在数组末尾增加一个元素了,注意这里size自加了一次，也就是size表示的是list中元素的个数。

elementData[size++] = e;
    return true;

自此,add()函数的源码也就分析完毕。

## 6.ArrayList关键函数之add(int index, E element) ##

这个函数与add(E e)的区别就是add(int index, E element)是在index位置插入一个元素。这个地方由于加了index，所以很可能涉及到数组内大量的元素移动。

public void add(int index, E element) {
        rangeCheckForAdd(index);
        //和add(E e)函数一样，确保add操作对于list容量可用
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //通过调用System的系统调用数组copy操作
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        //数组的添加
        elementData[index] = element;
        size++;
    }

上面首先通过`rangeCheckForAdd(index);` 检查index是否对于数组合法。下面是rangeCheckForAdd()函数的源码：

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

## 7.ArrayList关键函数之addAll(Collection ##

public boolean addAll(Collection<? extends E> c) {
        //将集合中元素转换成数组
        Object[] a = c.toArray();
        int numNew = a.length;
        //确保添加集合到list中后，list容量仍可用，如果不可用就扩容
        ensureCapacityInternal(size + numNew);  // Increments modCount
        System.arraycopy(a, 0, elementData, size, numNew);
        size += numNew;//集合中元素添加到list中之后，size相应的添加。
        return numNew != 0;
    }

## 8. get(int index)和set(int index, E element) 操作 ##

首先贴出这两个函数的源码：

public E get(int index) {
        //确保index在List中可用
        rangeCheck(index);
        //返回数组中index下标的元素
        return elementData(index);
    }
    
    public E set(int index, E element) {
        //确保index在List中可用
        rangeCheck(index);
        //将新的element设置在index位置，并返回旧的element
        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }

## 9. clear()函数 ##

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

看上面的源码可知，就是直接把elementData数组全部赋值为null了，然后将size清零。

## 10. remove(Object o) 删除list中的某个对象 ##

public boolean remove(Object o) {
        //如果o为null,就删除list中的所有的null
        if (o == null) {
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true;
                }
        } else {
       //删除list中的所有o
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }

## 11. subList(int fromIndex, int toIndex)获取子List ##

这个函数是根据索引fromIndex和toIndex来获取父List的一个视图，注意，这里并不是创建了一个新的List，而只是原来List的部分数据的一个视图，subList的任何操作都会影响到原来的父List。  
源码如下：

public List<E> subList(int fromIndex, int toIndex) {
        subListRangeCheck(fromIndex, toIndex, size);
        return new SubList(this, 0, fromIndex, toIndex);
    }
    
    static void subListRangeCheck(int fromIndex, int toIndex, int size) {
        if (fromIndex < 0)
            throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
        if (toIndex > size)
            throw new IndexOutOfBoundsException("toIndex = " + toIndex);
        if (fromIndex > toIndex)
            throw new IllegalArgumentException("fromIndex(" + fromIndex +
                                               ") > toIndex(" + toIndex + ")");
    }

SubList是一个ArrayList内部的private类，构造函数如下：

SubList(AbstractList<E> parent,
           int offset, int fromIndex, int toIndex) {
            this.parent = parent;
            this.parentOffset = fromIndex;
            this.offset = offset + fromIndex;
            this.size = toIndex - fromIndex;
            this.modCount = ArrayList.this.modCount;
    }

这个SubList的任何操作都是基于ArrayList这个类的elementData这个数组来实现的，所以只是父类的一个子视图。所以需要额外注意这一点

## 12. elementData为啥使用transient修饰？ ##

我们知道elementData使用transient修饰，那么这个List不是不能被序列化了吗？但是我们的ArrayList又实现了Serializable接口，这意味着ArrayList是可以被序列化的，用transient修饰elementData意味着我不希望elementData数组被序列化。这是为什么？因为序列化ArrayList的时候，ArrayList里面的elementData未必是满的，比方说elementData有10的大小，但是我只用了其中的3个，那么是否有必要序列化整个elementData呢？显然没有这个必要，因此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();
        }
    }

每次序列化的时候调用这个方法，先调用defaultWriteObject()方法序列化ArrayList中的非transient元素，elementData不去序列化它，然后遍历elementData，只序列化那些有的元素，这样：  
1、加快了序列化的速度  
2、减小了序列化之后的文件大小  
不失为一种聪明的做法，如果以后开发过程中有遇到这种情况，也是值得学习、借鉴的一种思路。

自此，ArrayList的源码分析完毕。

[ArrayList]: /images/20220713/08adf5641f4a4b4a9d4ee1b95ec1be6e.png