Java集合源码剖析之ArrayList

1 ArrayList概括
- 1.1 特性
- 1.2 数据结构
2 ArrayList源码剖析
- 2.1 继承关系
- 2.2 成员属性
- 2.3 构造方法
- 2.4 核心方法
- - 2.4.1 添加元素
  - 2.4.2 查询元素
  - 2.4.3 修改元素
  - 2.4.4 删除元素
  - 2.4.5 数组扩容
  - 2.4.6 其它方法

1 ArrayList概括

1.1 特性

ArrayList是基于数组实现的有序集合，它的容量可以动态的增长和缩减，默认容量为10，最大容量为Integer.MAX_VALUE。

ArrayList实现了RandomAccess接口，查找元素时可以通过数组下标快速的随机查找，但插入或删除元素时通常需要移动元素，因此，ArrayList更适合需要频繁的查找或修改的应用场景，而不太适合需要频繁的插入或删除的应用场景。如果想在ArrayList中添加大量元素，可通过ensureCapacity()方法指定合适的容量，从而减少扩容的次数以达到提高性能的目的。

ArrayList是非线程安全的，只能在单线程环境下使用，多线程环境下可以使用concurrent并发包下的CopyOnWriteArrayList类。

ArrayList中的元素可以重复，且可以为null值。

特性总结：有序、动态扩容、随机访问、非线程安全、元素可重复。

1.2 数据结构

ArrayList是使用Object数组实现的，其数据结构图如下图所示：

Java集合源码剖析之ArrayList1 ArrayList概括2 ArrayList源码剖析

2 ArrayList源码剖析

2.1 继承关系

ArrayList的层次结构如处图所示：

Java集合源码剖析之ArrayList1 ArrayList概括2 ArrayList源码剖析

ArrayList的继承关系下所示：

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

2.2 成员属性

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable {
    private static final long serialVersionUID = 8683452581122892189L;

    /**
     * 数组的默认容量
     */
    private static final int DEFAULT_CAPACITY = 10;
    
    /**
     * 数组的默认最大容量
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    /**
     * 空数组
     */
    private static final Object[] EMPTY_ELEMENTDATA = {};

    /**
     * 默认空数组
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     * ArrayList用于存储数据元素的数组
     */
    transient Object[] elementData;

    /**
     * ArrayList中实际数据元素的个数
     */
    private int size;
}

2.3 构造方法

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

    /**
     * 无参构造方法：不指定容量时，为默认空数组，默认容量为10
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    
    /**
     * 有参构造方法：指定容量时，为指定容量的数组
     */
    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);
        }
    }

    /**
     * 有参构造方法：赋值
     */
    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }
}

2.4 核心方法

2.4.1 添加元素

/**
 * 在ArrayList中添加一个元素
 */
public boolean add(E e) {
	// 容量检查，必要时进行扩容
    ensureCapacityInternal(size + 1);
    // 添加元素，修改实际元素的个数
    elementData[size++] = e;
    return true;
}

/**
 * 在ArrayList中指定位置添加一个元素
 */
public void add(int index, E element) {
	// 下标合法性检查
    rangeCheckForAdd(index);
    // 容量检查，必要时进行扩容
    ensureCapacityInternal(size + 1);
    // 移动index位置后面的元素
    System.arraycopy(elementData, index, elementData, index + 1, size - index);
    // 添加元素
    elementData[index] = element;
    // 修改实际元素的个数
    size++;
}

/**
 * 在ArrayList中批量添加元素
 */
public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray();
    int numNew = a.length;
    // 容量检查，必要时进行扩容
    ensureCapacityInternal(size + numNew);
    // 批量添加元素
    System.arraycopy(a, 0, elementData, size, numNew);
    // 修改实际元素的个数
    size += numNew;
    return numNew != 0;
}

/**
 * 在ArrayList中指定位置批量添加元素
 */
public boolean addAll(int index, Collection<? extends E> c) {
    // 下标合法性检查
    rangeCheckForAdd(index);
    Object[] a = c.toArray();
    int numNew = a.length;
    // 容量检查，必要时进行扩容
    ensureCapacityInternal(size + numNew);
    // 计算需要移动元素的个数
    int numMoved = size - index;
    if (numMoved > 0) {
    	// 移动元素
        System.arraycopy(elementData, index, elementData, index + numNew, numMoved);
	}
	// 批量添加元素
    System.arraycopy(a, 0, elementData, index, numNew);
    // 修改实际元素的个数
    size += numNew;
    return numNew != 0;
}

当调用add方法后，实际上会调用一系列方法，调用流程如下图所示：

Java集合源码剖析之ArrayList1 ArrayList概括2 ArrayList源码剖析

上图所示的调用流程实际上是与扩容有关，这一部分在2.4.5节中专门讲解。

2.4.2 查询元素

/**
 * 查询指定位置的元素
 */
public E get(int index) {
	// 下标合法性检查
    rangeCheck(index);
    // 获取并返回元素
    return elementData(index);
}

/**
 * 获取指定位置的元素
 */
E elementData(int index) {
    return (E) elementData[index];
}

2.4.3 修改元素

/**
 * 修改指定位置的元素
 */
public E set(int index, E element) {
	// 下标合法性检查
    rangeCheck(index);
    // 获取旧元素
    E oldValue = elementData(index);
    // 设置新元素
    elementData[index] = element;
    return oldValue;
}

2.4.4 删除元素

/**
 * 删除指定位置的元素
 */
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;
    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;
}

/*
 * 批量删除元素
 */
public boolean removeAll(Collection<?> c) {
	// 合法性检查
    Objects.requireNonNull(c);
    return batchRemove(c, false);
}

/**
 * 清空所有元素
 */
public void clear() {
    modCount++;
    for (int i = 0; i < size; i++) {
        elementData[i] = null;
	}
    size = 0;
}

/*
 * 批量删除元素
 * @param complement 指明c中的元素是要保留的元素还是要删除的元素，true则为要保留的元素，false则为要删除的元素
 */
private boolean batchRemove(Collection<?> c, boolean complement) {
  
    final Object[] elementData = this.elementData;
    // w是批量删除后的实际元素个数
    int r = 0, w = 0;
    boolean modified = false;
    try {
        for (; r < size; r++) {
        	// 遍历每个元素，并保留希望保留的元素
            if (c.contains(elementData[r]) == complement) {
                elementData[w++] = elementData[r];
            }
        }
    } finally {
    	// 如果还有元素没有遍历，则把后面的元素全部向前移动
        if (r != size) {
            System.arraycopy(elementData, r, elementData, w, size - r);
            w += size - r;
        }
        // 如果有元素被删除了
        if (w != size) {
        	// 清空后面的元素
            for (int i = w; i < size; i++) {
                elementData[i] = null;
            }
            modCount += size - w;
            // 修改批量删除之后的实际元素的个数
            size = w;
            modified = true;
        }
    }
    return modified;
}



/*
 * 快速移动元素
 */
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;
}

2.4.5 数组扩容

/**
 * 容量检查，必要时进行扩容
 * @param minCapacity 此次操作后的实际元素个数
 */
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

/**
 * 计算完成此次操作之后的容量
 * @param minCapacity 此次操作后的实际元素个数
 */
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    // 如果存储数据元素的数组为空数组，则此次操作后的容量应该为max(DEFAULT_CAPACITY, minCapacity)
    // 如果存储数据元素的数组不为空数组，则此次操作后的容量应该为minCapacity
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

/**
 * 查检是否要进行扩容
 * @param minCapacity 此次操作后的实际容量
 */
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // 如果此次操作之后的实际容量比当前容量要大，则进行扩容，否则不扩容
    if (minCapacity - elementData.length > 0) {
        grow(minCapacity);
    }
}

/**
 * 扩容
 * @param minCapacity 此次操作后的实际容量
 */
private void grow(int minCapacity) {
    // 保存现有的数据
    int oldCapacity = elementData.length;
    // 计算的新容量 = 当前容量的1.5倍
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 计算的新容量 = max(计算的新容量 , 此次操作后的实际容量)
    if (newCapacity - minCapacity < 0) {
        newCapacity = minCapacity;
    }
    // 如果计算的新容量比默认的最大容量还要大，则计算的新容量 = 允许的最大容量
    if (newCapacity - MAX_ARRAY_SIZE > 0) {
        newCapacity = hugeCapacity(minCapacity);
    }
    // 按照计算的新容量进行扩容
    elementData = Arrays.copyOf(elementData, newCapacity);
}

/**
 * 计算允许的最大容量
 * @param minCapacity 此次操作后的实际容量
 */
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) {
        throw new OutOfMemoryError();
    }
    // 如果此次操作后的实际容量比默认最大容量要大，则允许的最大容量为Integer.MAX_VALUE，否则为MAX_ARRAY_SIZE
    return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}

扩容总结：正常情况下扩容为原来的1.5倍，否则扩容为最大值（Integer.MAX_VALUE 或 MAX_ARRAY_SIZE）

2.4.6 其它方法

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

public void ensureCapacity(int minCapacity) {
    int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) ? 0 : DEFAULT_CAPACITY;
    if (minCapacity > minExpand) {
        ensureExplicitCapacity(minCapacity);
    }
}

public List<E> subList(int fromIndex, int toIndex) {
    subListRangeCheck(fromIndex, toIndex, size);
    return new SubList(this, 0, fromIndex, toIndex);
}

public Object[] toArray() {
    return Arrays.copyOf(elementData, size);
}

public <T> T[] toArray(T[] a) {
    if (a.length < size) {
        return (T[]) Arrays.copyOf(elementData, size, a.getClass());
    }
    System.arraycopy(elementData, 0, a, 0, size);
    if (a.length > size) {
        a[size] = null;
    }
    return a;
}

如果觉得本文对您有帮助，请关注博主的微信公众号，会经常分享一些Java和大数据方面的技术案例！

Java集合源码剖析之ArrayList1 ArrayList概括2 ArrayList源码剖析

Java集合源码剖析之ArrayList1 ArrayList概括2 ArrayList源码剖析

Java集合源码剖析之ArrayList

1 ArrayList概括

1.1 特性

1.2 数据结构

2 ArrayList源码剖析

2.1 继承关系

2.2 成员属性

2.3 构造方法

2.4 核心方法

2.4.1 添加元素

2.4.2 查询元素

2.4.3 修改元素

2.4.4 删除元素

2.4.5 数组扩容

2.4.6 其它方法

继续阅读

关于Gradle配置的小结

Java小案例——随机数猜测随机数猜测

nginx location中斜线的位置的重要性

27 Best Free Eclipse Plug-ins for Java Developer to be ProductiveCode Quality PluginsText Editor PluginsDependency ManagementVersion Control Integration PluginsFramework Development Continuous Integration Related PluginsOther Utility Plugins

Java String.format方法的简单使用

neo4j之cypher使用文档

GitHub连夜封杀！这份阿里 10W 字内部 Java 字面试手册到底有多强？

spark/scala关于【资源文件】加载方法概述外部文件加载方案测试资源文件打包入jar包中小结

mybatis_入门程序Mybatis入门

AOP编程_Android优雅权限框架(1)概念基础，2021金三银四前言正文大纲正文

Effective Java 8:通用程序设计

OOM三种类型

工厂模式-三种类型

【递归】高效率求2的n次幂

win10本地scala和spark安装安装scala安装spark

scala (3) Function 和 Method