Java之ArrayList解剖学

23号杂货铺

发布于 2019-09-27 16:31:23

3850

发布于 2019-09-27 16:31:23

文章被收录于专栏：23号杂货铺23号杂货铺

“ 一起来了解集合中ArrayList的源码实现。” —— 23号老板

引入

先送一张图。好好珍藏~ （来自网络）

回归基础，回归原理，你会有更深的领悟。今天来聊一聊在Java当中常用的一个集合类：ArrayList。

在大学学习数据结构的时候，我们知道常见的一种数据结构，就是集合。而在Java中的集合，是用于存储对象的工具类容器，它实现了常用的数据结构，提供了一系列公开的方法用于增加、删除、修改、查找和遍历数据，降低了日常开发的成本，提高了开发效率。

从上面的框架图中可以看出，Java的集合主要分为两类。

1、按照单个元素存储的Collection，在其继承树中，Set、List都实现了Collection接口；

2、按照Key - Value存储的Map，也是当下最流行的一种数据结构，业内出现了以此为基础的各式Nosql数据存储层产品。

了解ArrayList

List集合是线性数据结构的主要实现，集合元素通常存在一个明确的元素关系，Pre、Next。因此，List集合的遍历结果是稳定的。ArrayList就是List集合中的一个实现类，在开发中也是最常使用的一个集合类。这里以最常使用的JDK8为例，如果有版本上的不一致，请参看对比。

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable

也许你会在面试当中，常说到这样的话，和LinkedList作一次对比。ArrayList在使用上查询效率较高，新增元素的效率较低，balabala......然后就没什么可说的。再一问，这是为什么？不知道。

简单来说，ArrayList在内存上的存储，是利用了一个连续的存储空间，是一个顺序容器。即元素存放的数据与放进去的顺序相同，允许放入null元素，底层通过数组实现。

ArrayList的几个实现。

1、实现RandomAccess类

其原理的本质就在于indexedBinarySerach(list,key)或iteratorBinarySerach(list,key)方法。你会发现实现RandomAccess接口的List集合采用一般的for循环遍历，而未实现这接口则采用迭代器。通过大量的测试可以知道，使用迭代器遍历集合的速度会比for循环遍历差。

2、实现Cloneable类

Cloneable是一个标记接口，只有实现这个接口后，然后在类中重写Object中的clone方法，然后通过类调用clone方法才能克隆成功，如果不实现这个接口，则会抛出CloneNotSupportedException(克隆不被支持)异常。

3、实现Serializable类

实现Serializable接口的作用是就是可以把对象存到字节流，然后可以恢复（反序列化），能够进行关于对象的网络传输方式。

深入理解

/**
 * 默认初始容量
 */
private static final int DEFAULT_CAPACITY = 10;

private static final Object[] EMPTY_ELEMENTDATA = {};

/**
 * 空表的表示方法
 */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/**
 * 底层的数组为elementData
 */
transient Object[] elementData; // non-private to simplify nested class access

/**
 * ArrayList的大小
 */
private int size;

/**
 * 带有初始容量的构造器
 */
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {//大于0时创建一个initialCapacity大小的数组
        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;
}

/**
 * 当size大于0，采用Arrays.copyOf的复制方法赋值数组
 */
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;
    }
}

add、remove等

ArrayList的底层是基于动态数组实现的原因，动态数组的意思就是指底层的数组大小并不是固定的，而是根据添加的元素大小进行一个判断，不够的话就动态扩容，扩容的代码就在ensureCapacity里。

/**
 * 确保在扩容时的容量
 */
public void ensureCapacity(int minCapacity) {
    int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
        // any size if not default element table
        ? 0
        // larger than default for default empty table. It's already
        // supposed to be at default size.
        : DEFAULT_CAPACITY;

    if (minCapacity > minExpand) {
        ensureExplicitCapacity(minCapacity);
    }
}

/**
 * 数组的最大长度值，超过则OutOfMemoryError
 * OutOfMemoryError: Requested array size exceeds VM limit
 */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

/**
 * 扩容，原数组长度的2倍+1，采用的Arrays.copyOf复制方法
 */
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);
    elementData = Arrays.copyOf(elementData, newCapacity);
}


public int size() { return size;}

public boolean isEmpty() { return size == 0;}

public boolean contains(Object o) { return indexOf(o) >= 0;}

空间的问题解决后，插入过程就显得非常简单。

/**
 * 获取index位置的元素
 */
public E get(int index) {
    rangeCheck(index);

    return elementData(index);
}

/**
 * 替换index位置上的元素
 */
public E set(int index, E element) {
    rangeCheck(index);
    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

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

/**
 * 删除元素
 */
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; // clear to let GC do its work
    return oldValue;
}

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) {
    modCount++;
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work
}

删除是每次进行数组复制，然后让旧的elementData置为null进行垃圾回收。

以remove()方法为例。

可以看到这个 remove() 方法被重载了，一种是根据下标删除，一种是根据元素删除，这也都很好理解。

根据下标删除的 remove() 方法，大致的步骤如下：

1、检查有没有下标越界，就是检查一下当前的下标有没有大于等于数组的长度

2、列表被修改（add和remove操作）的次数加1

3、保存要删除的值

4、计算移动的元素数量

5、删除位置后面的元素向左移动，这里是用数组拷贝实现的

6、将最后一个位置引用设为 null，使垃圾回收器回收这块内存

7、返回删除元素的值

根据元素删除的 remove() 方法，大致的步骤如下：