Java-ArrayList源码分析

无标签
发布日期:   2018-06-02
文章字数:   3.2k
阅读时长:   12 分
阅读次数:  

版本说明：

JDK版本：1.8.0_171
IDE版本：IntelliJ IDEA 2017.1.5

0x01 ArrayList定义

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

Java自JDK1.5开始支持泛型，源码中ArrayList<E> 也是泛型支持的，它继承了AbstractList抽象类，实现了List、RandomAccess、Cloneable、java.io.Serializable接口。

标记接口，Marker interface，它们是一类没有定义任何接口方法的接口，表现为一个空接口
没有接口方法意味着实现该接口的类无需实现任何接口方法，仅仅作为一种标记，以供其他方法判断
作用就是当某个类实现这个接口后即拥有了这个接口的功能，Java 虚拟机在运行时会识别到它
标记接口是Java的语言特性

以下为ArrayList所实现的空接口（均为标记接口）：

  • RandomAccess 标记接口（Marker interface），用于标明实现该接口的list支持快速随机访问
  • Cloneable 标记接口（Marker interface），用于标明实现该接口的对象支持clone克隆
  • Serializable 标记接口（Marker interface）, 用于标明实现该接口的对象支持序列化

解释

  • 继承AbstractList类，实现List接口，提供了增删改查等操作，对象可以是null
  • 实现RandomAccess接口，提供了快速随机访问的能力（通过元素下标快速查找对象）
  • 实现Cloneable接口，覆盖了clone()方法，属于浅层拷贝，因为Java对象只有值传递
  • 实现Serializable接口，为对象提供了序列化传输功能
    ArrayList的内部结构是数组却不同于简单的数组，数组在创建之前需要确切的大小以容纳要存放的数据，创建之后大小已经固定，同一块内存地址上无法再进行添加操作。

优缺点

数组：高效但是其容量固定无法动态改变
ArrayList：容量可以动态增长，但牺牲的是效率，非线程安全
ArrayList是基于数组实现的可以自动扩容的数组也是其在集合框架中的特点，即动态数组。（扩容机制稍后源码分析）

0x02 ArrayList全局属性

//标明实现序列化类的版本号
private static final long serialVersionUID = 8683452581122892189L;

//默认初始的容量
private static final int DEFAULT_CAPACITY = 10;

//共享的空一个数组实例
private static final Object[] EMPTY_ELEMENTDATA = {};

//默认大小的空数组实例，将它与EMPTY_ELEMENTDATA区分开，以便确定当添加了第一个成员之后扩充多大。
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

//存储实际元素对象，ArrayList底层数据结构。注意，此参数不参与序列化，writeObject方法来进行
transient Object[] elementData; //非私有化以简化嵌套类的访问

//ArrayList包含的实际元素个数，elementData中已存放的元素的个数，默认为0
private int size;

解释

transient：用来标识一个属性不参加 要序列化的类的序列化操作。即序列化不会包含这个属性，这个字段的生命周期只存在于调用者的内存中而不会写入磁盘或通过网络传输到互联网上。
通俗的讲就是在采用Java默认的序列化机制的时候，被该关键字修饰的属性不会被序列化。
至于使用transient的原因：因为elementData是一个缓存数组，它通常会预留一些容量，等容量不足时再扩充容量。假如elementData的长度为10，而其中只有5个元素，那么在序列化的时
候只需要存储5个元素，而数组中后面5个元素会被序列化成null，这是不合逻辑的，所以不需要存储这些为null的元素，这样避免了Java的自动序列化之后，再通过手动添加序列化方法实现序列化。

0x03 ArrayList构造函数

ArrayList有三个构造函数

/**
 * 构造具有指定初始容量的空列表
 * 初始容量是对数组进行初始化大小的，此时ArrayList的size属性为0
 * 如果初始容量参数为负值时，则抛出异常
 */
public ArrayList(int initialCapacity) {
    if (initialCapacity > 0) {
        //创建一个初始化大小的Object数组给elementData
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        //将空数组赋给elementData
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}
//将elementData指向默认的空数组，当第一次插入元素时，会对其扩容到10个
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
 * 构造一个包含指定Collection元素的list
 * 元素的排列顺序与使用Collection的iterator返回的顺序一致。
 * 指定的Collection的所有元素都会被放在构造的list中9k
 * 当指定的Collection为null时抛出异常
 */
public ArrayList(Collection<? extends E> c) {
    //集合转换为数组，将数组地址赋值给elementData
    elementData = c.toArray();
    //更新size的值，同时判断size的大小，如果是size不等于0，
    if ((size = elementData.length) != 0) {
        //c.toArray 可能(错误地)不返回 Object[]类型的数组（此处是JDK的bug，有bug_id）
        //bug参见：https://bugs.java.com/bugdatabase/view_bug.do?bug_id=6260652
        if (elementData.getClass() != Object[].class)
            //转换为Object数组
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        //将空数组赋给elementData
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

解释

c.toArray 可能不返回Object[]类型的数组

通过ArrayList的toArray()方法传过来的数组一定是Object[]类型的。
但是ArrayList的这个构造函数接受的参数是Collection<? extends E> c，
同事由于Arrays中的asList()是将数组转换成list集合的一种方法，其满足形参的要求，但是Arrays中的toArray()
方法却不同于ArrayList中的toArray()方法，它没有保证传递出的数组一定是Object[]类型。

以下代码整理自Arrays的内部类ArrayList(此类与java.util.ArrayList无关系)

//Arrays$ArrayList，Arrays内部类ArrayList
private static class ArrayList<E> extends AbstractList<E>
    implements RandomAccess, java.io.Serializable
{
    private final E[] a;
    
    //单纯的克隆，没有保证数组的类型
    @Override
    public Object[] toArray() {
        return a.clone();
    }
}

所有如果传递给ArrayList构造函数的集合是Arrays$ArrayList这个内部类，那么它返回的数组类型不一定是Object[]
需要在**if (elementData.getClass() != Object[].class)**进行判断。

0x04 ArrayList扩容机制

在说明扩容机制之前，首先了解一下如何给ArrayList添加一个元素

//将指定元素追加到列表的末尾
public boolean add(E e) {
    //检测底层数组的容量，不足则进行扩容
    ensureCapacityInternal(size + 1);  // 同时需要增加modCount
    //底层数组添加这个元素，再size自增
    elementData[size++] = e;
    return true;
}

add()方法首先去检测数组的容量是否还能装得下需要添加的新元素，因为size初始化为0，所以扩容判断要加1，不够则进行数组的扩容，同时源码作者还不忘记提醒需要修改modCount这个记录修改次数的属性。扩容完成后进行元素的添加，同时size++ 来保证添加的元素数量增1来表明ArrayList的个数。

// 私有方法，扩容检查入口
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
//空数组判断
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    // 判断是否为空数组
    // 如果是无参构造函数构造的集合，第一次添加元素时会满足此条件，返回较大的值：10
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}
//进行精确扩容检查
private void ensureExplicitCapacity(int minCapacity) {
    // 记录结构被修改的次数，用于迭代器在遍历时做线程安全检查的
    modCount++;

    // 当底层数组的长度比添加元素后的长度小时，进行扩容操作（同时考虑溢出）
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
/**
 * 数组所能分配到的最大值
 * 因为有的虚拟机在数组中保留了一些header words
 * 请求更大数组可能会导致OutOfMemoryError，大小超过了VM的限制
 */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
// 扩容操作
// 增加容量以确保它至少能容纳 由最小容量参数指定的 元素数量。
private void grow(int minCapacity) {
    // 得到目前的容量
    int oldCapacity = elementData.length;
    // oldCapacity >> 1表示位运算，扩容的关键性语句
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 判断newCapacity是否溢出
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 判断newCapacity是否超过了MAX_ARRAY_SIZE，超过了，则计算最大容量
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // 数组拷贝并扩容，传递原数组与新数组长度，由Arrays内部创建数组返回给elementData
    elementData = Arrays.copyOf(elementData, newCapacity);
}
// 求最大容量值
private static int hugeCapacity(int minCapacity) {
    // 首先判断minCapacity是否已经溢出了，溢出了就直接抛出OOM
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    //判断minCapacity 是否大于 MAX_ARRAY_SIZE，大于返回 Integer.MAX_VALUE ，不大于 返回MAX_ARRAY_SIZE
    return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}

解释

代码比较多，主要是围绕扩容，保证数据安全性的操作。
首先，在往几何对象中添加元素时，在调用add方法时，先会去检查层数组的容量，不足就去进行扩容操作。

  • ensureCapacityInternal 扩容判断入口
  • calculateCapacity计算底层数组的需要的最少容量，底层数组为空，则返回10，底层数组扩容到10
  • ensureExplicitCapacity扩容判断，最小容量与底层数组，判断底层数组容量，是否需要扩容
  • grow底层数组扩容，拷贝到新数组，规避溢出问题等
  • hugeCapacity最大容量保证，溢出则抛OOM
    扩容大小，原大小+原大小进行右位移运算1位得出的结果。

0x05 ArrayList普通方法

普通方法只在代码中注释，个别重点方法会拉出来进行解释

//将底层数组的容量调整为当前实际元素的大小，应用程序可以使用此操作最小化ArrayList实例的存储。
public void trimToSize() {
    modCount++;
    if (size < elementData.length) {
        elementData = (size == 0)
          ? EMPTY_ELEMENTDATA
          : Arrays.copyOf(elementData, size);
    }
}
 //返回此list的元素个数。size是真正的保存的元素的数量
public int size() {
    return size;
}
//判断此list是否为空，true为空
public boolean isEmpty() {
    return size == 0;
}
//判断容器是否包含某个元素,包含则返回true
public boolean contains(Object o) {
    return indexOf(o) >= 0;
}
/**
 * 判断元素是否在集合中，注意list允许null值，注意只获取第一个所在的位置
 * 集合中的元素为空时则返回-1
 */
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;
}
//同indexOf，不过是从尾部遍历。for循环从后往前
public int lastIndexOf(Object o) {
    if (o == null) {
        for (int i = size-1; i >= 0; i--)
            if (elementData[i]==null)
                return i;
    } else {
        for (int i = size-1; i >= 0; i--)
            if (o.equals(elementData[i]))
                return i;
    }
    return -1;
}
// 重写Object的clone方法，返回这个ArrayList实例的浅拷贝。
public Object clone() {
    try {
        ArrayList<?> v = (ArrayList<?>) super.clone();
        // 将原对象elementData数组的内容复制到新返回对象elementData数组的内容中
        v.elementData = Arrays.copyOf(elementData, size);
        // 新对象的modCount设置为0
        v.modCount = 0;
        return v;
    } catch (CloneNotSupportedException e) {
        // 这不可能发生，因为我们是可克隆的
        throw new InternalError(e);
    }
}
/**
 * 返回一个包含这个集合所有元素正确顺序排列的数组(从第一个到最后一个元素)
 * 返回的数组是“安全的”，在这个集合中没有引用过它(换句话说，这个方法必须分配一个
 * 新数组)。因此，调用方可以自由修改返回的数组
 * 此方法充当基于数组和基于集合API的桥梁
 */
public Object[] toArray() {
    return Arrays.copyOf(elementData, size);
}
/**
 * 返回数组的运行时类型 为 指定的类型
 * 如果list符合指定的数组，则将其返回其中
 * 否则，将使用指定数组的运行时类型和该list的大小分配一个新数组。
 *
 * 如果list符合指定的数组，且有多余的空间(比如：数组比list有更多的元素)
 * 在集合结束后，数组中的元素被设置为null。(只有当调用者知道列表中不包含
 * 任何空元素时，这才有助于确定列表的长度。)
 *
 * 参数： a 要存储list元素的数组，应该足够大，以装得下list的所有元素;
 *          否则，将为此目的分配一个相同的运行时类型的新数组。
 */
@SuppressWarnings("unchecked")
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;
}

0x06 ArrayList位置访问操作

E elementData(int index) {
    return (E) elementData[index];
}

/**
 * Returns the element at the specified position in this list.
 *
 * @param  index index of the element to return
 * @return the element at the specified position in this list
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public E get(int index) {
    rangeCheck(index);

    return elementData(index);
}
文章作者: 王吉凯
文章链接: https://wangjikai.top/2018/06/02/Java-ArrayList%E6%BA%90%E7%A0%81%E5%88%86%E6%9E%90/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 王吉凯 !
无标签
赏
 上一篇
Java-TimeUnit源码分析 Java-TimeUnit源码分析
2023-03-30 王吉凯
下一篇 
Java-Serializable源码分析 Java-Serializable源码分析
Java序列化是指把Java对象转换为字节序列的过程；通过序列化可以把对象转换成字节流，可以进行网络传输，保持到本地文件，数据库等，增加对象的生命周期。serializeable是一个标记接口，没有待实现方法，此接口的意义在于告诉java
2018-06-02 王吉凯
  目录