投稿
  1. 极客之音首页
  2. 其他分类
  3. 微信精选

JDK8源码阅读-ArrayList

小半 • • 微信精选 • 阅读 255

小伙伴们，大家好。前几周好像是得了甲流，一直发烧、感冒，学习劲头也不是很足。今天终于有心情读读源码写写文章了。我们先找个软柿子捏捏。

类结构

JDK8源码阅读-ArrayList
image.png
  • Serializable接口：序列化接口
  • Cloneable接口：可克隆接口
  • RandomAccess接口：支持随机访问（通过下标的形式访问元素）
  • List接口
  • AbstractList<E>抽象类
  • AbstractCollection<E>抽象类
  • Collection<E>接口
  • Iterable<T>接口

属性

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 Object[] EMPTY_ELEMENTDATA = {};

    /**
     * 空数组实例 和 EMPTY_ELEMENTDATA 有区分
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    /**
     * 元素数组
     */
    transient Object[] elementData; // non-private to simplify nested class access

    /**
     * 元素数量
     */
    private int size;

}
  • Object[] elementData：用于存放元素的数组（数组的长度并一定等于元素个数）
  • int size：用于记录元素的个数
  • int DEFAULT_CAPACITY：默认的数组长度大小为10
  • Object[] EMPTY_ELEMENTDATA：长度为0的数组实例（手动设置初始容量为0时使用）
  • Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA：长度为0的数组实例（无参构造方法时使用）

构造方法

ArrayList()

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

无参构造方法，元素数组elementData默认赋值DEFAULTCAPACITY_EMPTY_ELEMENTDATA空数组实例

ArrayList(int initialCapacity)

    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);
        }
    }
  • initialCapacity的取值范围：[0,Integer.MAX_VALUE]
  • 当指定initialCapacity=0时，元素数组elementData默认赋值EMPTY_ELEMENTDATA空数组实例

ArrayList(Collection<? extends E> c)

    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;
        }
    }
  • 当c.toArray()的元素个数为0时，元素数组elementData被赋值EMPTY_ELEMENTDATA空数组实例
  • 当c.toArray()的元素个数不为0时
    • 若数组是Object[]类型，则无须任何操作，方法结束
    • 若数组不是Object[]类型，则转换成Object[]类型

get(int index)方法

    public E get(int index) {
        rangeCheck(index);

        return elementData(index);
    }
  • rangeCheck(int index)：检查index的值是否越界
  • elementData(int index)：获取元素

rangeCheck(int index)

    private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

方法判断index不能够大于等于size，否则抛出异常。 如果大家传负值，这里不会报错

elementData(int index)

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

代码也相当的简单，直接通过下标访问数组，并强转一次。

add(E e)

public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {
    public boolean add(E e) {
        add(size(), e);
        return true;
    }
}
public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> {
 public void add(int index, E element) {
        throw new UnsupportedOperationException();
    }
}

add(E e)方法在抽象类中，并提供一个add(int index, E element)让其子类重写，这里插入位置index为size，下面进入其子类ArrayList#add(int index, E element)的具体实现

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
 public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
    }
}

ArrayList的实现逻辑如下

  • rangeCheckForAdd(int index)：判断插入位置index是否在数组下标范围内[0,size]
  • ensureCapacityInternal：确保数组长度大于当前size+1
  • 通过复制的方式移动数组，将index位置空出来
  • 将index位置设置为被插入元素
  • size++

rangeCheckForAdd(int index)

    private void rangeCheckForAdd(int index) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

方法十分简单易懂，判断index要在[0,size]范围，否则抛出异常

ensureCapacityInternal(int minCapacity)

    private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }

该方法为了确保元素数组elementData的长度足够

  • 如果元素数组elementData为DEFAULTCAPACITY_EMPTY_ELEMENTDATA，则会取minCapacity和DEFAULT_CAPACITY中较大的一个作为minCapacity
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

进入ensureExplicitCapacity方法，modCount会自增。如果当前的数组元素elementData长度不够（小于minCapacity），则进行扩容。扩容方法咱们后面细说

元素移动

    public void add(int index, E element) {
     //..................
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        //..................
    }

从index位置开始，移动size-index个元素到index+1开始的位置

JDK8源码阅读-ArrayList
image.png

add(int index, E element)

指定位置插入，是直接跳到了ArrayList中的add(int index, E element)就是上面分析的内容，这里就不重复分析了。

remove(int index)

    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; // clear to let GC do its work

        return oldValue;
    }
  1. index检查是否越界
  2. modCount++记录一次修改
  3. 获取index位置的元素值
  4. 计算出移动的元素个数size-index-1
  5. 将删除位置后的元素向前移动
  6. size-1的位置设置为空，size=size-1
  7. 返回老数据
JDK8源码阅读-ArrayList
image.png

扩容grow(int minCapacity)

好的，我们这里专门看一下ArrayList的扩容机制

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
 private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        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);
    }

    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

  • 新的数组大小等于oldCapacity + (oldCapacity >> 1)

oldCapacity >> 1等价于oldCapacity/2。 所以新数组大小为老数组的1.5倍

  • 若老数组扩容1.5倍后还是小于minCapacity则新数组的长度就是minCapacity
  • 若新数组大小比MAX_ARRAY_SIZE还要大，则通过minCapacity重新计算新的数组长度
  • 通过Arrays.copyOf进行数组复制扩容

总结

以上就是XiXi关于ArrayList的创建、新增元素（扩容）、删除元素、查询元素相关代码的阅读，总结下来就几点

  • ArrayList底层就是一个Object[]数组，默认初始化大小为10，且在首次add元素时才初始化数组长度为10
  • ArrayList插入和删除元素会移动元素位置，使用复制的方式完成
  • ArrayList每次扩容原数组长度的1.5倍
  • ArrayList的新增和删除操作均会导致modCount的自增


原文始发于微信公众号（溪溪技术笔记）：JDK8源码阅读-ArrayList

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。

文章由极客之家整理，本文链接：https://www.bmabk.com/index.php/post/207092.html

赞 (0)
小半的头像小半
0 0

相关推荐

发表回复

登录后才能评论
极客之家——专业性很强的中文编程技术网站，欢迎收藏到浏览器，订阅我们！