ArrayList源码分析

java源码分析之ArrayList源码分析，ArrayList是常用的集合框架类之一。现在来先简单分析它的源码，占坑先。

构造函数

 /**
  * Constructs an empty list with an initial capacity of ten.
  */
  表示构建一个数组，长度为10
public ArrayList() {
    //DEFAULTCAPACITY_EMPTY_ELEMENTDATA是一个Object类型数组的引用
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

常用的方法

1，添加元素

public boolean add(E e) {
        //modCount加1
        modCount++;
        //
        add(e, elementData, size);
        return true;
}
``

private void add(E e, Object[] elementData, int s) {
//
if (s == elementData.length)
elementData = grow();
elementData[s] = e;
size = s + 1;
}

grow()

private Object[] grow() {
return grow(size + 1);
}

1	grow(int minCapacity )

private Object[] grow(int minCapacity) {
return elementData = Arrays.copyOf(elementData,
newCapacity(minCapacity));
}

1	关键代码：newCapacity()

private int newCapacity(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity <= 0) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
return Math.max(DEFAULT_CAPACITY, minCapacity);
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return minCapacity;
}
return (newCapacity - MAX_ARRAY_SIZE <= 0)
? newCapacity
: hugeCapacity(minCapacity);
}

copyOf

public static T[] copyOf(T[] original, int newLength) {
return (T[]) copyOf(original, newLength, original.getClass());
}

1	copyOf(U[] original, int newLength, Class<? extends T[]> newType)

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
@SuppressWarnings(“unchecked”)
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
return copy;
}

1
2
3

分析：
以上就是add()方法走的流程，这是基于JDK 11.0.2的。
简而言之就是调用无参的构造函数会创建一个大小为0的Object型数组，

this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;

1	而DEFAULTCAPACITY_EMPTY_ELEMENTDATA就是一个大小为0的Object数组

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

在新增了一个元素的时候，逐步调用会调用到grow()函数，grow()又继续调用grow(int minCapacity)函数，grow(int minCapacity)返回一个Object类型的数组，这个数组又是怎么生成以及大小是什么呢？这时候到copyOf(T[] original, int newLength)方法：Arrays.copyOf(elementData，newCapacity(minCapacity));第一个参数先不看，第二个参数是newCapacity(minCapacity)，返回一个int型的值，这个值是多少呢？这就到了newCapacity(int minCapacity)方法，minCapacity是grow(int minCapacity)中minCapacity传入的，而grow(int minCapacity)是被grow()调用的，传入的参数是size + 1，size正是数组中元素的个数，添加第一个元素的时候size还是为0，所以这里grow(size + 1)的size为0，size + 1为1，也就是minCapacity的值为1，newCapacity(minCapacity)中的minCapacity为1，而初始化数组就是在调用newCapacity(int minCapacity)函数的时候，看代码：

private int newCapacity(int minCapacity) {
// overflow-conscious code
//oldCapacity = 0
int oldCapacity = elementData.length;
//newCapacity = 0
int newCapacity = oldCapacity + (oldCapacity >> 1);
//满足这个条件
if (newCapacity - minCapacity <= 0) {
//满足这个条件
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
//minCapacity值为1，所以这里显然返回DEFAULT_CAPACITY的值
return Math.max(DEFAULT_CAPACITY, minCapacity);
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return minCapacity;
}
return (newCapacity - MAX_ARRAY_SIZE <= 0)
? newCapacity
: hugeCapacity(minCapacity);
}

return Math.max(DEFAULT_CAPACITY, minCapacity);DEFAULT_CAPACITY的值是10，是一个常量。所以这样就生成了一个初始容量大小为10的数组。紧接着把第一个元素赋值给数组的第一个位置。

elementData[s] = e;

这样就完成初始化了，jdk这样改进后能或多或少节约一点资源，这和HashMap初始化一样，在添加了元素才会在内存开辟空间生成默认大小的数组，一开始是生成了一个引用。比如HashMap的默认构造函数：

public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

1	并没有数组实例，只是确认了加载因子。调用了put方法添加元素进去的时候再初始化创建数组。put方法代码：

public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}

```
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        //(tab = table) == null 为true，所以执行1处的代码
        if ((tab = table) == null || (n = tab.length) == 0)
            // resize()，
            n = (tab = resize()).length;//1
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
}

执行resize()方法，生成一个大小为16，加载因子为0.75的Node数组。

2，删除元素

public E remove(int index) {
    Objects.checkIndex(index, size);
    final Object[] es = elementData;

    @SuppressWarnings("unchecked") E oldValue = (E) es[index];
    fastRemove(es, index);

    return oldValue;
}

3，修改元素

public E set(int index, E element) {
    //检查是否越界
    Objects.checkIndex(index, size);
    //找到要覆盖的元素
    E oldValue = elementData(index);
    //覆盖这个值
    elementData[index] = element;
    //返回旧值
    return oldValue;
}

查询

不同修改modCount，相对于增删效率要高一些

public E get(int index) {
    //检查是否越界
    Objects.checkIndex(index, size);
    //
    return elementData(index);
}

清空元素

public void clear() {
    modCount++;
    final Object[] es = elementData;
    for (int to = size, i = size = 0; i < to; i++)
        es[i] = null;
}

包含某个元素

//返回一个boolean值，可知indexOf(o)的值大于等于0方法返回的值就为true，就说明包含该元素
public boolean contains(Object o) {
        return indexOf(o) >= 0;
}

indexOf方法

public int indexOf(Object o) {
    //
    return indexOfRange(o, 0, size);
}

indexOfRange方法

//返回一个int值，从start到end范围内，对应到上面的代码就是从0到list列表的大小(size)。
 int indexOfRange(Object o, int start, int end) {
        Object[] es = elementData;
        //如果o为null，
        if (o == null) {
            for (int i = start; i < end; i++) {
                //注意，ArrayList是可以添加null元素的，且可以添加多个，如果列表中有null
                //元素，找到一个就返回，返回该元素的下标，它当然大于等于0，所以此时
                //indexOfRange(o, 0, size)返回值大于等于0，走到最后indexOf(o)也是大于等
                //于0，所以返回true。
                if (es[i] == null) {
                    return i;
                }
            }
        }
        //否则，也就是o不为null，
         else {
            for (int i = start; i < end; i++) {
                //如果o和数组中某个元素相等，返回该元素下标，最终contains也是返回true
                if (o.equals(es[i])) {
                    return i;
                }
            }
        }
        //都不满足以上条件，返回-1，小于0，所以contains方法返回false
        return -1;
}

判空

这里很简单，就是看size是否为0，是就返回true，否则返回false

1
2
3

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

迭代器 Iterator

1
2
3

public Iterator<E> iterator() {
    return new Itr();
}