JDK8中ArrayList源码分析

ArrayList是一个动态数组,可灵活的增删元素,更改数组

1.前言

前面几章学习了数据结构和算法的基础知识,对简单数据结构的使用和算法都有了初步的了解,今天我们接着学习数据结构相关知识,ArrayList源码简单分析

2.目录

目录

3.ArrayList分析

3.1 类和属性

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

3.1.1.实现的接口

• RandomAccess:使for循环效率更高,否则使用iterator
• Cloneable:方便集合数据的复制
• Serializable:可序列化传输集合数据

3.1.2.属性

// 序列化id
private static final long serialVersionUID = 8683452581122892189L;
// 默认的初始容量 默认构造器初始化 第一次add 扩容为10
private static final int DEFAULT_CAPACITY = 10;
// 空的对象数组 容量为0 第一次add 扩容为1
private static final Object[] EMPTY_ELEMENTDATA = {};
// 空的对象数组 默认构造器的初始化值
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 当前数据对象存放的数组,不参与序列化,之序列化实际的数据,不是整个数组,节约时间和空间
transient Object[] elementData;
//当前数组的长度
private int size;
// 有些虚拟机在阵列中保留一些头信息，防止内存溢出 一个字节8bytes
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

3.2 初始化

默认构造方法,数据存放数组赋值为空数组

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

• 传入参数如果是大于0，则使用用户的参数初始化，
• 等于0则初始化为空数组
• 传入的参数小于0，则抛出异常

public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
    }
}

• 将collection对象转换成数组，然后将数组的地址的赋给elementData。
• 更新size的值，同时判断size的大小，如果是size等于0，直接将空对象EMPTY_ELEMENTDATA的地址赋给elementData
• 如果size的值大于0，则执行Arrays.copy方法，把collection对象的内容（可以理解为深拷贝）copy到elementData中。

public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        //在bug文档6260652中 防止c.toArray()类型返回错误
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

3.3.常用方法

add(E e)方法:增添元素,成功返回true,扩容为原有容量的1.5倍

public boolean add(E e) {
    //容量的规格调整
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    //容量加1,存放添加元素
    elementData[size++] = e;
    //成功返回true
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    //数组对象为默认的初始化的值时
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        //将默认值10和最小容量作比较
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    //设置容量
    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    //修改数加一 部分情况会判断是否与预期值一致,否则报ConcurrentModificationException
    modCount++;
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        //扩容
        grow(minCapacity);
}

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    //扩大为原来的1.5倍
    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);
}

//底层数组的复制,数组的位置调动
//将src数组从srcPos处开始, length个元素,拷贝到dest数组,从destPos开始
@FastNative
public static native void arraycopy(Object src,  int  srcPos,
                                    Object dest, int destPos,
                                    int length);

add(int index, E element)方法:在指定索引出插入元素

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;
    //数组长度加1
    size++;
}

get(int index)方法:获取指定索引的值

public E get(int index) {
    //判断数组下标是否越界
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    //-1会报ArrayIndexOutOfBoundsException
    return (E) elementData[index];
}

set(int index, E element)方法:设置指定索引的值,返回旧值

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

contains(Object o)方法:遍历数组作对比,找到返回true,没有找到则返回false

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

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

remove(int index)/remove(Object o)方法:根据索引或者值删除元素

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 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)
        //将elementData数组从index+1处开始, numMoved个元素,拷贝到elementData数组,从index开始
        System.arraycopy(elementData, index+1, elementData, index,
                numMoved);
    //数组末尾元素置空 大小减一
    elementData[--size] = null; // clear to let GC do its work
}

clear()方法:清空数组元素,不会调整数组的最大容量

public void clear() {
    modCount++; 
    // clear to let GC do its work
    for (int i = 0; i < size; I++)
        //将数组内的元素都置空,等待垃圾收集器收集,但不会减小数组最大容量
        elementData[i] = null;
    //数组大小置为0
    size = 0;
}

trimToSize()方法:数组最大容量平衡调整

public void trimToSize() {
    modCount++;
    if (size < elementData.length) {
        elementData = (size == 0)
                ? EMPTY_ELEMENTDATA
                //数组最大容量调整,底层用的是System.arraycopy(), elementData要复制的数组, size要返回的副本长度
                : Arrays.copyOf(elementData, size);
    }
}

ListIterator接口:ArrayList的遍历迭代器,通过内部类ListItr实现

private class ListItr extends Itr implements ListIterator<E> {
    ListItr(int index) {
        super();
        //开始的遍历的索引
        cursor = index;
    }
    //前面是否有数据
    public boolean hasPrevious() {
        return cursor != 0;
    }
    //下一个索引
    public int nextIndex() {
        return cursor;
    }
    //前一个索引
    public int previousIndex() {
        return cursor - 1;
    }
    @SuppressWarnings("unchecked")
    public E previous() {
        //已修改数与预期修改数不一致报ConcurrentModificationException
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        int i = cursor - 1;
        //索引越界 没有结点
        if (i < 0)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        //并发操作导致i值异常
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        cursor = I;
        //返回前一个的结点值
        return (E) elementData[lastRet = I];
    }
    ...
}

4.总结

本章主要讲解了java常用集合ArrayList的源码实现,包括ArrayList的初始化,元素的添加,扩容,元素的删除,容量的平衡调整等. ArrayList底层是对数组进行操作,封装了数组常用的一些方法,对数组扩容,数组复制进行了优化