JDK容器学习之ArrayList:底层存储和动态扩容

ArrayList 底层存储和动态扩容逻辑

ArrayList 作为最常用的容器之一,通常用来存储一系列的数据对象,O(1)级别的数据读写

I. 底层数据模型

查看源码,其内部定义的成员变量

// 默认数组容量
private static final int DEFAULT_CAPACITY = 10;

// 静态成员,创建一个空的ArrayList时,内部数组实际使用这个
// 避免每次创建一个ArrayList对象,都要新创建一个对象数组
private static final Object[] EMPTY_ELEMENTDATA = {};

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

// 实际保存数据的数组
transient Object[] elementData; // non-private to simplify nested class access

private int size;

因此ArrayList的底层数据模型比较清晰,就是一个数组,默认初始容量为10

II. 新增,删除,读取逻辑

因为底层的数据结构为数组,所以根据index查询元素是常量级别开销,等同于获取数组中所索引为index处的元素 因此需要关注的就是新增一个元素,若数组容量不够,如何进行扩容 删除一个元素,数组的连续性又是如何保障

1. 获取接口

获取List中某索引处的值,实现逻辑比较简单,如下

public E get(int index) {
    // 判断是否数组越界
    rangeCheck(index);
    // 获取数组中的元素
    return elementData(index);
}

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

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

另一个比较常见的读取接口就是containindexOf两个接口,用于判断列表中是否包含某个元素or某个元素在数组中的索引

若让我们自己来设计上面两个接口,多半是遍历数组,依次判断每个元素,是否满足要求

JDK实际实现代码如下

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

从具体实现,可以注意一下几点

  • size表示列表中元素的实际个数
  • 列表中允许保存NULL
  • 列表中允许多次加入统一个对象,但indexOf返回的是第一个匹配的位置
  • 方法indexOf返回-1表示不存在

2. 删除元素

在添加元素之前,先看删除元素的接口实现,因为不涉及到动态扩容问题, 在分析中考虑下面几点

  1. 删除中间的元素,是否会造成后续的数组迁移
  2. 删除最后一个元素,是否会造成重排(还是直接size-1即可)

首先看删除指定索引处的值

public E remove(int index) {
    // 数组越界判断
    rangeCheck(index);

    modCount++;
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    if (numMoved > 0) { // 如果移动不是最后一个则需要数组拷贝
        // native 方法实现数组拷贝
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    }
    // 消灭最后一个元素
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

从源码解决上面两个问题

  1. 删除中间元素,会导致数组拷贝
  2. 删除最后一个元素,不用数组拷贝,直接将最后一个元素设置为null
  3. 删除不会导致数组容量缩水,也就是List只有扩容的逻辑,没有缩小容量的逻辑

3. 新增元素

结合删除的逻辑,新增元素逻辑应该比较清晰,将添加索引处及之后的元素,整体后移一位,然后赋值新的值; 需要注意扩容的机制

添加一个元素的实现

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}
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++;
}

扩容的逻辑如下

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

    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    if (minCapacity - elementData.length > 0) {
    // 当前的数组容量,已经超过数组长度
        grow(minCapacity);
    }
}

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

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

针对上面的逻辑进行小结:

  • 先扩容,后数组迁移,最后进行赋值
  • 扩容逻辑:
    • 优先扩容原来容量的1.5倍
    • 若依旧不够,则扩容到恰好能容纳所有元素
  • 在列表的最后添加元素,不要使用add(index,object)方法,会造成没必要的数组迁移调用

插入删除示意图

III. 遍历逻辑

容器基本上都是实现了 Iterable 接口,所以遍历则主要是依据迭代器的next()方法来实现

List的遍历,说白了就是数组的遍历,实现逻辑比较简单,唯一有意思的就是并发修改抛异常的问题

先看下迭代器类

private class Itr implements Iterator<E> {
    int cursor;       // index of next element to return
    int lastRet = -1; // index of last element returned; -1 if no such
    int expectedModCount = modCount;

    public boolean hasNext() {
        return cursor != size;
    }

    @SuppressWarnings("unchecked")
    public E next() {
        // 下面方法确保在遍历过程中,若有其他线程修改了列表的内容,则抛异常
        checkForComodification();
        int i = cursor;
        if (i >= size)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        
        // 遍历的实际逻辑,就是索引的递增
        cursor = i + 1;
        return (E) elementData[lastRet = i];
    }

    public void remove() {
       // ...
    }

    @Override
    @SuppressWarnings("unchecked")
    public void forEachRemaining(Consumer<? super E> consumer) {
        //
    }

    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

IV. 小结

  1. ArrayList的底层存储为数组
  2. ArrayList中可保存null,一个对象可以塞入多次
  3. 初始容量为10, 新增元素,若实际个数超过数组容量,则触发扩容逻辑
    • 优先扩容原来容量的1.5倍
    • 若依旧不够,则扩容到恰好能容纳所有元素
  4. 只有添加元素会导致数组容量变化,删除不会
  5. 线程非安全,遍历过程中不允许修改列表

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏皮皮之路

【JDK1.8】JDK1.8集合源码阅读——ArrayList

9140
来自专栏格子的个人博客

Java源码阅读之ArrayList - JDK1.8

当你对某件事情很感兴趣的时候,时间的流逝在感知中都模糊了(是不是很文艺,绕口得都快听不懂了),通俗来说,就是时间过得很快。

20550
来自专栏Android知识点总结

Java容器源码攻坚战--第二战:ArrayList

18820
来自专栏coolblog.xyz技术专栏

ArrayList 源码详细分析

ArrayList 是一种变长的集合类,基于定长数组实现。ArrayList 允许空值和重复元素,当往 ArrayList 中添加的元素数量大于其底层数组容量时...

44080
来自专栏我就是马云飞

ArrayList到底是什么?

ArrayList是日常开发中使用最频繁的集合类。首先这边简单介绍一下ArrayList:

18920
来自专栏皮皮之路

【JDK1.8】JDK1.8集合源码阅读——ArrayList

287120
来自专栏用户画像

4.5.1 二叉排序树

二叉排序树的查找时从根结点开始,沿着某一分支逐层向下进行比较比较的过程。若二叉排序树非空,将给定值与根结点的关键字比较,若相等,则查找成功;若不等,则当根结点的...

11430
来自专栏猿人谷

线性表简介

学习数据结构 -> 线性表 -> 线性表的介绍     线性表是一种典型的数据结构, 线性结构的基本特点是线性表中的数据元素是有序且有限的, 在线性结构中...

21680
来自专栏desperate633

LintCode 数组剔除元素后的乘积题目代码

定义B[i] = A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1], 计算B的时候请不要使用除法。

10510
来自专栏一枝花算不算浪漫

Java中常见数据结构List之ArrayList

390120

扫码关注云+社区

领取腾讯云代金券