转载

走进 JDK 之 ArrayList（一）

这篇本来是准备写 Java 集合框架概述 的，就是写起来效果不怎么样，可能是对整个 Java 集合框架还没有做到了然于心。所以还是先来源码分析，写完所有集合类的分析之后，再来总体概述。今天就从最最常用的 ArrayList 说起。

概述

ArrayList 是一种可以动态增长和缩减的线性表数据结构，允许重复元素，允许 null 值。基于动态数组实现，在内存中是连续的，这点和链表不同。另外，它不是线程安全的，与之相对应的同样基于动态数组实现的有序序列 Vector 则是线程安全的。

由于数组在内存中占用连续的内存空间，所以 ArrayList 具备随机访问能力，其根据下标随机访问的时间复杂度是 O(1) 。同样，为了保证内存的连续性，其 插入 和 删除 操作就相对低效的多。在指定位置插入数据，就要将该位置之后的数据都往后挪，才能腾出空间。在指定位置删除数据，就要将该位置之后的数据全部往前挪，才能保证空间连续性。它们的平均时间复杂度都是 O(n) 。

ArrayList 的使用还是比较简单的，下面还是带着两个问题看源码:

ArrayList 初始大小是多少？它是如何动态扩容的？

源码解析

类声明

走进 JDK 之 ArrayList（一） 
public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable {}
复制代码
  • Collection 是所有集合的根接口，定义了一些通用性的行为，抽象类 AbstractCollection 提供了部分集合类型无关的通用实现。 List 接口针对有序集合扩展了 Collection 接口，抽象类 AbstractList 提供了部分默认实现，当然 ArrayList 并没有照单全收，更多的是重写提供了自己的实现。
  • 实现了 RandomAccess 接口说明其支持快速随机访问，其实并没有实现任何方法，应该仅仅只是起一个标记的作用。
  • 实现 Cloneable 接口，提供浅拷贝。
  • 实现了 Serializable 接口，提供序列化能力，且重写了 readObject() 和 writeObject() 方法。

成员变量

private static final int DEFAULT_CAPACITY = 10; // 默认初始容量
private static final Object[] EMPTY_ELEMENTDATA = {}; // 共享空数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; // 默认共享空数组
transient Object[] elementData; // 真正保存数据的数组
private int size; // 当前元素个数
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; // 数组容量最大值
复制代码

elementData 是真正用来保存数据的数组。关于它的默认大小，让人很容易搞错。一看到 DEFAULT_CAPACITY 为 10，让人情不自禁的认为我一旦新建了一个 ArrayList ，它的默认大小就是 10。其实并不是这样的，后面看到构造函数的时候你就理解了。

数组的最大容量是 Integer.MAX_VALUE - 8 ，看到这个数字你应该很熟悉。 AbstractStringBuilder 类用来存储字符的 char[] ，最大容量也是这个数字。考虑到一些虚拟机实现会保留数组对象的头信息，大于此值可能会导致 OOM ，注意只是可能。但是如果大于 Integer.MAX_VALUE 的话，就会直接抛出 OOM 。

构造函数

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
复制代码

DEFAULTCAPACITY_EMPTY_ELEMENTDATA 是一个空数组，所以当你执行 List list = new ArrayList() 时，实际上创建了一个空数组，并不是容量为 10 的数组。 

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);
    }
}
复制代码

当我们可以预估到 ArrayList 需要容纳的元素数量时，我们可以直接指定数组大小 initialCapacity ，避免后续自动扩容带来的性能损耗和空间浪费。 initialCapacity 大小按如下规则： 

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;
    }
}
复制代码

我们也可以用一个集合来初始化 ArrayList 。调用集合的 toArray() 方法转换为数组并赋给 elementData 。如果传入的集合长度为 0，则将空数组 EMPTY_ELEMENTDATA 赋给 elementData 。

方法

ArrayList 提供了插入，删除，清空，查找，遍历等基本集合操作。下面从 add() 开始，通过源码更加深刻的理解 ArrayList 的实现。

add()

public void add(int index, E element) {
    rangeCheckForAdd(index); // 边界检测

    ensureCapacityInternal(size + 1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,
                         size - index); // 移动 index 之后的所有元素
    elementData[index] = element;
    size++;
}
复制代码

rangeCheckForAdd() 这个方法在后面也会用到很多次，主要做边界检测，当 index 大于 size 或者小于 0 时，都会抛出 IndexOutOfBoundsException 异常。

第二步 ensureCapacityInternal() 的作用是保证集合的空间足以继续添加元素，空间不足时会自动扩容。这个方法很重要，可以说是 ArrayList 的核心了。我们来看一下到底是如何扩容的。 

private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity); // 扩容
    }
复制代码

通过 calculateCapacity() 方法计算合适的最少空间： 

private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity); // 如果当前是空数组，取 minCapacity 和 10 的较大值
    }
    return minCapacity;
}
复制代码

如果初始化时没有指定集合大小，则取 DEFAULT_CAPACITY （等于10）和 minCapacity 的较大值。所以，如果我们构建了一个空 ArrayList，当我们添加第一个元素的时候，就会默认扩容至 10 。

当 minCapacity 大于当前数组长度时，就需要扩容了， grow() 方法就是扩容的具体实现： 

private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length; // 原数组大小
    int newCapacity = oldCapacity + (oldCapacity >> 1); // 扩容至原来的 1.5 倍
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity); // 容量最大最大只能是 Integer.MAX_VALUE
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}
复制代码

每次扩容后为原来容量的 1.5 倍，所以当我们可以预估元素数量的时候，直接在构造函数中指定，就可以节约空间了。如果扩容后的新容量大于 MAX_ARRAY_SIZE ，即 Integer.MAX_VALUE - 8 ，调用 hugeCapacity() 方法再做一次判断。 

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError(); // 小于 0，即发生溢出，抛出 OOM
    return (minCapacity > MAX_ARRAY_SIZE) ? // 最大只可能为 Integer.MAX_VALUE
        Integer.MAX_VALUE : MAX_ARRAY_SIZE;
    }
复制代码

最后使用 Arrays.copyOf() 方法创建新数组： 

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
    @SuppressWarnings("unchecked")
    T[] copy = ((Object)newType == (Object)Object[].class)
        ? (T[]) new Object[newLength]
        : (T[]) Array.newInstance(newType.getComponentType(), newLength);
    System.arraycopy(original, 0, copy, 0,
                    Math.min(original.length, newLength));
    return copy;
}
复制代码

扩容完成之后，就可以愉快的添加元素了，直接给 elementData[size++] 赋值即可。

一个参数的 add(E element) 方法是在数组尾部添加元素，除此之外，ArrayList 还支持在指定位置添加元素， add(int index, E element) : 

public void add(int index, E element) {
    rangeCheckForAdd(index); // 边界检测

    ensureCapacityInternal(size + 1);  // Increments modCount!!
    System.arraycopy(elementData, index, elementData, index + 1,
                    size - index); // 移动 index 之后的所有元素
    elementData[index] = element;
    size++;
}
复制代码

在指定位置 index 处插入一个元素，就需要把 index 后面的元素都依次往后移动，给要添加的元素腾出来位置，所以 ArrayList 的插入操作并不是那么的高效。

remove()

remove() 方法也有两个，第一个是移除指定位置的元素： 

public E remove(int index) {
    rangeCheck(index); // 边界检测

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

    int numMoved = size - index - 1;
    if (numMoved > 0) // 移动 index 之后的所有元素
        System.arraycopy(elementData, index+1, elementData, index,
                        numMoved);
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}
复制代码

逻辑比较简单，将 index 之后的所有元素都依次往前移动，注意在完成移动之后，将集合尾部元素置空，以便 GC 回收。和插入一样， ArrayList 的删除也不是那么的高效，时间复杂度都是 O(n) 。

第二个是移除指定元素：

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;
}
复制代码

这里要注意一点，当集合中存在重复元素时，无论是 null 还是其他对象， remove() 方法只会移除其中的第一个。这里用的移除用的是 fastRemove() 方法，其实和普通的 remove() 方法没什么区别，只是取消了边界检测，且没有返回值，所以更 fast 一点。 

/*
* Private remove method that skips bounds checking and does not
* return the value removed.
* 取消边界检查，且不返回 remove 掉的值
*/
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; // clear to let GC do its work
}
复制代码

removeAll() && retainAll()

public boolean removeAll(Collection<?> c) {
    Objects.requireNonNull(c);
    return batchRemove(c, false);
}
复制代码

removeAll() 方法是移除所有包含在集合 c 中的元素，调用 batchRemove() 实现。 

public boolean retainAll(Collection<?> c) {
    Objects.requireNonNull(c);
    return batchRemove(c, true);
}
复制代码

retainAll() 方法正好与 removeAll() 相反，是保留所有包含在集合 c 中的元素，移除其他元素，也是调用 batchRemove() 实现。

batchRemove() 方法应该是 ArrayList 中比较复杂的一个方法了，但是绝对值得仔细一看。 

/**
*
* @param c 集合
* @param complement 为 true 时，保留指定集合中的值，为 false 时，删除指定集合中的值
* @return 数组中重复的元素都会被删除，只要发生删除就会返回 true
*/
private boolean batchRemove(Collection<?> c, boolean complement) {
    final Object[] elementData = this.elementData;
    int r = 0, w = 0;
    boolean modified = false;
    try {
        // 遍历数组，并检查这个集合是否包含对应的值，移动要保留的值到数组前面，w 最终值为要保留的元素的数量
        // 也就是说，如果是 retainAll()，就将相同元素移动到数组前面。
        // 如果是 removeAll()，就将不同元素移动到数组前面
        for (; r < size; r++)
            if (c.contains(elementData[r]) == complement)
                elementData[w++] = elementData[r];
    } finally {
        // Preserve behavioral compatibility with AbstractCollection,
        // even if c.contains() throws.
        if (r != size) { // r != size，说明发生异常，循环未执行完成
            System.arraycopy(elementData, r,
                            elementData, w,
                            size - r); // 将 r 之后的元素移动过去
            w += size - r;
        }
        // w == size 说明保留全部元素，modified 返回 false
        if (w != size) {
            // clear to let GC do its work
            for (int i = w; i < size; i++)
                elementData[i] = null;
            modCount += size - w; // 更新 modCount
            size = w; // w 就是要保存的元素个数
            modified = true;
        }
    }
    return modified;
}
复制代码

总之，不管你是 removeAll() 还是 retainAll() ，我 batchRemove() 一律把要保留的元素移到前面，要删掉的元素扔后面，并记录下面要保留元素的个数。

其他

后面的方法都很简单直白，大致浏览一下就可以了。

// 获取集合大小
public int size() {
    return size;
}

// 判断集合是否为空
public boolean isEmpty() {
    return size == 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 E set(int index, E element) {
    rangeCheck(index);

    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}

// 获取指定位置的元素
public E get(int index) {
    rangeCheck(index);

    return elementData(index);
}

// 清空集合
public void clear() {
    modCount++;

    // clear to let GC do its work
    for (int i = 0; i < size; i++)
        elementData[i] = null;

    size = 0;
}
复制代码

总结

简单总结一下 ArrayList：

O(1)
O(n)

既然标题是 走进 JDK 之 ArrayList（一） ，那么肯定还有二嘛。如果你有认真看 ArrayList 源码，你会发现一个经常出现的字段 modCount ，字面意思就是修改次数。基本但凡涉及到修改集合的方法，大多都会执行 modCount++ 操作，以 clear() 方法为例： 

public void clear() {
    modCount++;
    // clear to let GC do its work
    for (int i = 0; i < size; i++)
        elementData[i] = null;
    size = 0;
}
复制代码

那么，这个 modCount 究竟有什么作用，这便是 走进 JDK 之 ArrayList（二） 所要详细说明的。

文章首发微信公众号： 秉心说 ， 专注 Java 、 Android 原创知识分享，LeetCode 题解。

更多 JDK 源码解析，扫码关注我吧！

走进 JDK 之 ArrayList（一）
原文  https://juejin.im/post/5cc070a2f265da037a3cee37
正文到此结束
所属分类： Java 编程技术

热门推荐

相关文章

阿里云首购8折
说给你听

本文目录
随机标签
书籍教程
Java入门教程 bootstrap3 CSS Apache基础教程 springboot-demo php ionic 教程 Python mysql教程 eclipse Ubuntu VPS系统配置 AngularJS 教程 Struts2教程 MongoDB教程 Redis教程 Spring教程 Git教程 Jenkins进阶系列 openfire参考指南 Java设计模式 HBase教程 Maven教程 hibernate教程 Docker 教程 memcached教程 Quartz指南 SpringCloud ANTLR教程 Hive教程 java实例教程 Ant教程 Hazelcast教程 Elastic-Job-Lite XStream教程 深入浅出MyBatis SVN教程 ibaties教程 rabittmq教程 WebService CXF学习 Hadoop教程 solr教程 JPA教程 ActiveMQ中文指南 Java内存模型 dubbo教程 Linux入门视频教程
近期评论
  1. 1 能用365块大洋去解决的事，千万不要用时间
  2. 2 Spring Boot集成atomikos快速入门Demo
  3. 3 Spring Boot集成fastdfs快速入门Demo
  4. 4 Spring Boot集成Https快速入门Demo
  5. 5 Spring Boot集成easypoi快速入门Demo
  6. 6 Spring Boot集成webflux快速入门Demo
  7. 7 Spring Boot集成Graphql快速入门Demo
  8. 8 Spring Boot API 多版本快速入门Demo
  9. 9 Spring Boot内容协商快速入门Demo
  10. 10 Spring Boot集成Debezium实现postgres增量同步
网站信息
  • 文章总数：155,458 篇
  • 文件总数：468,738 个
  • 标签总数：2,264 个
  • 分类总数：90 个
  • 留言数量：2,538 条
  • 在线人数：654 人
  • 运行天数：4,191天
  • 最后更新：2024年04月18日22点
Loading...

其他链接

关于本站

本站定位：个人技术类博客

本站作用：写博客、记日志、闲聊扯淡鼓捣技术。

问题交流

[HBLOG]公众号 HBLOG HBLOG