Collection:Java集合框架-ArrayList

ArrayList （基于JDK1.8）

ArrayList

• 实现了 list 接口 是 list下 最常用的实现类之一
• 实现了 RandomAccess 接口 RandomAccess是一个声明式接口 拥有此接口 意味着 可以快速访问
• 实现了 Cloneable 接口 Cloneable 是一个声明式接口 拥有此接口 意味着 可以使用Object的clone方法复制副本
• 实现了 Serializable 接口 Serializable是一个声明式接口 拥有此接口 意味着 可以序列化以及反序列化

ArrayList 依赖关系：

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

类注释说明：

1. ArrayList 提供操作数组的方法 与 Vector 相似 但是ArrayList 线程不安全
2. add() 时间复杂度O(n)
3. 容量大于等于size
4. 线程不安全 如果想要用线程安全的 推荐使用Collections.synchronizedList 例子：List list = Collections.synchronizedList(new ArrayList(…))
5. since：1.2

ArrayList的一些默认属性值

// 初始容量大小 默认为10
private static final int DEFAULT_CAPACITY = 10;

// 基于空数组的实例
private static final Object[] EMPTY_ELEMENTDATA = {};

// 共享空数组实例，用于默认大小的空实例
// 将其与EMPTY_ELEMENTDATA区分开来，以了解添加第一个元素时需要膨胀多少。
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

// 默认的元素数据
// 如果初始化是没有设置 默认值元素数据为 DEFAULTCAPACITY_EMPTY_ELEMENTDATA
// 源码中 注释 不使用private 是为了能用于 简化 嵌套访问
// non-private to simplify nested class access
transient Object[] elementData;

// 数组大小 ArrayList中包含多少数据
private int size;

// ArrayList最大容量 Integer的最大值-8
// 源码中 说明 JVM虚拟机会占用部分资源
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

// 计数器(版本记录) ArrayList每被操作一次 将自增
protected transient int modCount = 0;

说明

1. 默认容量为10
2. size没有被volatile 线程不安全
3. size最大容量为Integer最大值-8
4. modCount 版本计数器

ArrayList的构造器

// 自定义容量大小的构造器
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);
     }
 }

// 默认空参构造器 初始为空 数组
// 默认 容量大小为 10
public ArrayList() {
     this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
 }
 
// 传入一个集合
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;
     }
 }

有关构造器的说明：

1. 通过空参构造器创建ArrayList对象的时候 默认容量是10 ，size的大小为0 ，第一次向数组中加值的时候size才会变成10
2. 通过传入集合构造器创建对象时 如果集合内的类型不是Object 会自动将类型转换成Object。通过此方式创建ArrayList可能会出现一个异常（// c.toArray might (incorrectly) not return Object[] (see 6260652)）一般情况下不会出此异常 只有在下列场景下才会触发：ArrayList 初始化之后（ArrayList 元素非 Object 类型），再次调用 toArray 方法，得到 Object 数组，并且往 Object 数组赋值时，才会触发此 bug，代码

List<String> list = Arrays.asList("test 6260652");
Object[] objects = list.toArray();
System.out.println("objects = " + objects.getClass().getSimpleName());
objects[0] = new Object();

objects = String[] // 执行发现 数据类型为String[]
Exception in thread “main” java.lang.ArrayStoreException: java.lang.Object
at com.demo.async.Test.main(Test.java:15)

• 官方文档中的说明：https://bugs.java.com/bugdatabase/view_bug.do?bug_id=6260652 此bug在 JAVA 9 被解决

ArrayList的方法

扩容机制

// 添加方法  
public boolean add(E e) {
    // 扩容方法 size是当前数组大小    
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 直接赋值 线程不安全
    elementData[size++] = e;
    return true;
}

private void ensureCapacityInternal(int minCapacity) {
    // 判断 原数数据 是否 等于 默认的实例大小
        if (elementData == DEFAULTCAPACITY_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);
    }
// 扩容
private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
    	// 扩容容量 = 初始容量(现有的 原数数据 长度) + 0.5初始容量
   		// 即 1.5倍扩
        int newCapacity = oldCapacity + (oldCapacity >> 1);
    	// 如果 扩容以后 还小于 期望容量 扩容容量直接等于期望容量
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
    	// 如果 扩容以后 大于数组的最大值 也就是Integer的最大值-8
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            // 扩容后的容量 直接等于 ArrayList的最大值
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
    	// 将 数组复制到 新的 数组中
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
    MAX_ARRAY_SIZE;
}

// 数组扩容的具体实现方法
// Arrays.copyOf()
// 参数一：旧容量 参数二：新的数组长度 参数三：新数组的类型
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
        @SuppressWarnings("unchecked")
    // 如果旧数组 和 新数组 类型一样都是Object  直接创建一个Object的数组 容量为 传入的新数组
        T[] copy = ((Object)newType == (Object)Object[].class)
            ? (T[]) new Object[newLength]
            // 否则 通过Array的 newInstance方法创建数组
            : (T[]) Array.newInstance(newType.getComponentType(), newLength);
        System.arraycopy(original, 0, copy, 0,
                         Math.min(original.length, newLength));
    // 最后返回数组
        return copy;
}

扩容机制说明

1. ArrayList 当容量不够时 1.5倍扩
2. 如果1.5倍扩不够 新容量为期望容量
3. 如果1.5倍扩大于ArrayList的最大容量 直接将最大容量赋值

ArrayList 动态数组的本质

利用Arrays的copy方法 将老数组 整个copy到新数组中

since：1.6

删除

// 通过下标 删除 为例子
public E remove(int index) {
    // 如果indnx 大于 size 会出下标越界异常
    rangeCheck(index);
	// 计数器自增
    modCount++;
    // 拿到删除的那个数据
    E oldValue = elementData(index);
	// size 3 index 1 numMoved 1
    int numMoved = size - index - 1;
    if (numMoved > 0)
        // 原数组 元素组起始位2 目标数组 目标数组起始下标1 要复制的元素个数1 
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

说明：

• 新的数组 = （原来数组 复制到 要删除的下标 -1） + （要删除下标 + 1 到 最后）

ArrayList 当 用于 共享资源时 是线程不安全的 因为里面的 add remove等方法 没有加synchronized 同步锁 并且 size elementData等属性 也不是不可见的（没有被volatile修饰）

赏

谢谢你请我吃糖果