本着共同学习的原则，来一波常用数据结构源码走读。包括ArrayList、LinkedList、HashMap。对这三种常用到的数据结构进行源码分析，本次列车解析主要包含各数据集合增、删、改、查。

ArrayList

- ArrayList是List接口的可变数组的实现。实现了所有可选列表操作，并允许包括 null 在内的所有元素。

数据结构：

线性表的顺序存储结构具有两个基本特点：

- 线性表中所有元素所占的存储空间是连续的；

- 线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。

源码

构造函数：

private static final Object[] EMPTY_ELEMENTDATA = {};

private static final int DEFAULT_CAPACITY = 10;

public ArrayList(int initialCapacity) {

super();

if (initialCapacity < 0)

throw new IllegalArgumentException("Illegal Capacity: "+

initialCapacity);

this.elementData = new Object[initialCapacity];

}

public ArrayList() {

super();

this.elementData = EMPTY_ELEMENTDATA;

}

ArrayList有两个构造函数，一种是给定初始容量，一种是默认构造。使用默认构造函数是不会分配多余的空间的，由源码`private static final Object[] EMPTY_ELEMENTDATA = {};`可以看出。而对于已分配的空间数量不够情况会怎么办呢？在元素增加（执行add方法）的时候会调用`ensureCapacityInternal()`方法进行容量检查并扩充容量。下面就来Look下add、remove、set、get方法源码：

public boolean add(E e) {

ensureCapacityInternal(size + 1); // Increments modCount!!

elementData[size++] = e;

return true;

}

public void add(int index, E element) {

if (index > size || index < 0)

throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

ensureCapacityInternal(size + 1); // Increments modCount!!

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

elementData[index] = element;

size++;

}

public E remove(int index) {

if (index >= size)

throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

modCount++;

E oldValue = (E) 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 E get(int index) {

if (index >= size)

throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

return (E) elementData[index];

}

public E set(int index, E element) {

if (index >= size)

throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

E oldValue = (E) elementData[index];

elementData[index] = element;

return oldValue;

}

ArrayList的数据操作都是简单的数组操作，这里主要介绍下两个方法：`ensureCapacityInternal`和`System.arraycopy`。System.arraycopy是数组操作的核心方法，理解了它你就理解了数组世界。

ensureCapacityInternal

public void ensureCapacity(int minCapacity) {

int minExpand = (elementData != EMPTY_ELEMENTDATA)

// any size if real element table

? 0

// larger than default for empty table. It's already supposed to be

// at default size.

: DEFAULT_CAPACITY;

if (minCapacity > minExpand) {

ensureExplicitCapacity(minCapacity);

}

}

private void ensureCapacityInternal(int minCapacity) {

if (elementData == EMPTY_ELEMENTDATA) {

minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);

}

ensureExplicitCapacity(minCapacity);

}

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

}

这里主要介绍下`Arrays.copyOf`方法，跟踪Arrays.copyOf代码可以看到核心还是System.arraycopy`方法。

System.arraycopy：

/*

* @param src 源数组

* @param srcPos 源数组复制的起始位置

* @param dest 目的数组

* @param destPos 目的数组放置的起始位置

* @param length 复制的长度

*/

public static native void arraycopy(Object src, int srcPos,

Object dest, int destPos,

int length);