ArrayList源码解读—Java8版本(上)

简介: ArrayList源码解读—Java8版本(上)

一、ArrayList简介


ArrayList顶部有一段很长的注释,大概的介绍了ArrayList。


1.1 原文

/**
 * Resizable-array implementation of the <tt>List</tt> interface.  Implements
 * all optional list operations, and permits all elements, including
 * <tt>null</tt>.  In addition to implementing the <tt>List</tt> interface,
 * this class provides methods to manipulate the size of the array that is
 * used internally to store the list.  (This class is roughly equivalent to
 * <tt>Vector</tt>, except that it is unsynchronized.)
 *
 * <p>The <tt>size</tt>, <tt>isEmpty</tt>, <tt>get</tt>, <tt>set</tt>,
 * <tt>iterator</tt>, and <tt>listIterator</tt> operations run in constant
 * time.  The <tt>add</tt> operation runs in <i>amortized constant time</i>,
 * that is, adding n elements requires O(n) time.  All of the other operations
 * run in linear time (roughly speaking).  The constant factor is low compared
 * to that for the <tt>LinkedList</tt> implementation.
 *
 * <p>Each <tt>ArrayList</tt> instance has a <i>capacity</i>.  The capacity is
 * the size of the array used to store the elements in the list.  It is always
 * at least as large as the list size.  As elements are added to an ArrayList,
 * its capacity grows automatically.  The details of the growth policy are not
 * specified beyond the fact that adding an element has constant amortized
 * time cost.
 *
 * <p>An application can increase the capacity of an <tt>ArrayList</tt> instance
 * before adding a large number of elements using the <tt>ensureCapacity</tt>
 * operation.  This may reduce the amount of incremental reallocation.
 *
 * <p><strong>Note that this implementation is not synchronized.</strong>
 * If multiple threads access an <tt>ArrayList</tt> instance concurrently,
 * and at least one of the threads modifies the list structurally, it
 * <i>must</i> be synchronized externally.  (A structural modification is
 * any operation that adds or deletes one or more elements, or explicitly
 * resizes the backing array; merely setting the value of an element is not
 * a structural modification.)  This is typically accomplished by
 * synchronizing on some object that naturally encapsulates the list.
 *
 * If no such object exists, the list should be "wrapped" using the
 * {@link Collections#synchronizedList Collections.synchronizedList}
 * method.  This is best done at creation time, to prevent accidental
 * unsynchronized access to the list:<pre>
 *   List list = Collections.synchronizedList(new ArrayList(...));</pre>
 *
 * <p><a name="fail-fast">
 * The iterators returned by this class's {@link #iterator() iterator} and
 * {@link #listIterator(int) listIterator} methods are <em>fail-fast</em>:</a>
 * if the list is structurally modified at any time after the iterator is
 * created, in any way except through the iterator's own
 * {@link ListIterator#remove() remove} or
 * {@link ListIterator#add(Object) add} methods, the iterator will throw a
 * {@link ConcurrentModificationException}.  Thus, in the face of
 * concurrent modification, the iterator fails quickly and cleanly, rather
 * than risking arbitrary, non-deterministic behavior at an undetermined
 * time in the future.
 *
 * <p>Note that the fail-fast behavior of an iterator cannot be guaranteed
 * as it is, generally speaking, impossible to make any hard guarantees in the
 * presence of unsynchronized concurrent modification.  Fail-fast iterators
 * throw {@code ConcurrentModificationException} on a best-effort basis.
 * Therefore, it would be wrong to write a program that depended on this
 * exception for its correctness:  <i>the fail-fast behavior of iterators
 * should be used only to detect bugs.</i>
 *
 * <p>This class is a member of the
 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
 * Java Collections Framework</a>.
 *
 * @author  Josh Bloch
 * @author  Neal Gafter
 * @see     Collection
 * @see     List
 * @see     LinkedList
 * @see     Vector
 * @since   1.2
 */
public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
...
}


1.2 翻译

List接口的大小可变数组的实现。实现了所有可选列表操作,并允许包括null在内的所有元素。除了实现List接口外,此类还提供一些方法来操作内部用来存储列表的数组的大小。(此类大致上等同于Vector类,除了此类是不同步的。)


size、isEmpty、get、set、iterator和listIterator操作都以固定时间运行。add操作以分摊的固定时间运行,也就是说,添加n个元素需要O(n)时间。其他所有操作都以线性时间运行(大体上讲)。与用于LinkedList实现的常数因子相比,此实现的常数因子较低。


每个ArrayList实例都有一个容量。该容量是指用来存储列表元素的数组的大小。它总是至少等于列表的大小。随着向ArrayList中不断添加元素,其容量也自动增长。并未指定增长策略的细节,因为这不只是添加元素会带来分摊固定时间开销那样简单。


在添加大量元素前,应用程序可以使用ensureCapacity操作来增加ArrayList实例的容量。这可以减少递增式再分配的数量。


注意,此实现不是同步的。如果多个线程同时访问一个ArrayList实例,而其中至少一个线程从结构上修改了列表,那么它必须保持外部同步。(结构上的修改是指任何添加或删除一个或多个元素的操作,或者显式调整底层数组的大小;仅仅设置元素的值不是结构上的修改。)这一般通过对自然封装该列表的对象进行同步操作来完成。如果不存在这样的对象,则应该使用Collections.synchronizedList方法将该列表“包装”起来。这最好在创建时完成,以防止意外对列表进行不同步的访问:

List list = Collections.synchronizedList(new ArrayList(…));


此类的iterator和listIterator方法返回的迭代器是快速失败的:在创建迭代器之后,除非通过迭代器自身的remove或add方法从结构上对列表进行修改,否则在任何时间以任何方式对列表进行修改,迭代器都会抛出ConcurrentModificationException。因此,面对并发的修改,迭代器很快就会完全失败,而不是冒着在将来某个不确定时间发生任意不确定行为的风险。


注意,迭代器的快速失败行为无法得到保证,因为一般来说,不可能对是否出现不同步并发修改做出任何硬性保证。快速失败迭代器会尽最大努力抛出ConcurrentModificationException。因此,为提高这类迭代器的正确性而编写一个依赖于此异常的程序是错误的做法:迭代器的快速失败行为应该仅用于检测bug。


此类是Java Collections Framework的成员。


1.3 一语中的

底层:ArrayList是List接口的大小可变数组的实现。

是否允许null:ArrayList允许null元素。

时间复杂度:size、isEmpty、get、set、iterator和listIterator方法都以固定时间运行,时间复杂度为O(1)。add和remove方法需要O(n)时间。与用于LinkedList实现的常数因子相比,此实现的常数因子较低。

容量:ArrayList的容量可以自动增长。

是否同步:ArrayList不是同步的。

迭代器:ArrayList的iterator和listIterator方法返回的迭代器是 fail-fast 的。

如果小伙伴们不了解"fail-fast"机制,可以参考如下文章:

深入浅出fail-fast机制


1.4 线程安全性

对ArrayList进行添加元素的操作的时候是分两个步骤进行的,即第一步先在object[size]的位置上存放需要添加的元素;第二步将size的值增加1。由于这个过程在多线程的环境下是不能保证具有原子性的,因此ArrayList在多线程的环境下是线程不安全的。


具体举例说明:在单线程运行的情况下,如果Size = 0,添加一个元素后,此元素在位置 0,而且Size=1;而如果是在多线程情况下,比如有两个线程,线程 A 先将元素存放在位置0。但是此时 CPU 调度线程A暂停,线程 B 得到运行的机会。线程B也向此ArrayList 添加元素,因为此时 Size 仍然等于 0 (注意哦,我们假设的是添加一个元素是要两个步骤哦,而线程A仅仅完成了步骤1),所以线程B也将元素存放在位置0。然后线程A和线程B都继续运行,都增 加 Size 的值。 那好,现在我们来看看 ArrayList 的情况,元素实际上只有一个,存放在位置 0,而Size却等于 2。这就是“线程不安全”了。


如果非要在多线程的环境下使用ArrayList,就需要保证它的线程安全性,通常有两种解决办法:


第一,使用synchronized关键字;

第二,可以用Collections类中的静态方法synchronizedList();对ArrayList进行调用即可。

第三,也可以使用concurrent并发包下的CopyOnWriteArrayList类。


1.5 优劣分析

优点


ArrayList底层以数组实现,是一种随机访问模式,再加上它实现了RandomAccess接口,因此查找也就是get的时候非常快。

ArrayList在顺序添加一个元素的时候非常方便,只是往数组里面添加了一个元素而已。

根据下标遍历元素,效率高。

根据下标访问元素,效率高。

可以自动扩容,默认为每次扩容为原来的1.5倍。

缺点


插入和删除元素的效率不高。

根据元素下标查找元素需要遍历整个元素数组,效率不高。

线程不安全。


二、定义


我们先来看看ArrayList的定义:

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


从中我们可以了解到:


ArrayList:说明ArrayList支持泛型。

extends AbstractList :继承了AbstractList。AbstractList提供List接口的骨干实现,以最大限度地减少“随机访问”数据存储(如ArrayList)实现Llist所需的工作。

implements List:实现了List。实现了所有可选列表操作。

implements RandomAccess:表明ArrayList支持快速(通常是固定时间)随机访问。此接口的主要目的是允许一般的算法更改其行为,从而在将其应用到随机或连续访问列表时能提供良好的性能。

implements Cloneable:表明其可以调用clone()方法来返回实例的field-for-field拷贝。

implements java.io.Serializable:表明该类具有序列化功能。

为什么要先继承AbstractList,而让AbstractList先实现List?而不是让ArrayList直接实现List?


这里是有一个思想,接口中全都是抽象的方法,而抽象类中可以有抽象方法,还可以有具体的实现方法,正是利用了这一点,让AbstractList是实现接口中一些通用的方法,而具体的类, 如ArrayList就继承这个AbstractList类,拿到一些通用的方法,然后自己在实现一些自己特有的方法,这样一来,让代码更简洁,就继承结构最底层的类中通用的方法都抽取出来,先一起实现了,减少重复代码。所以一般看到一个类上面还有一个抽象类,应该就是这个作用。


ArrayList的父类AbstractList也实现了List接口,那为什么子类ArrayList还是去实现一遍呢?


collection 的作者Josh说他写这代码的时候觉得这个会有用处,但是其实并没什么用,但因为没什么影响,就一直留到了现在。


ArrayList的类结构图:


image.png

如何查看类的完整结构图可以参考如下文章:

IDEA如何查看类的完整结构图


三、数据结构


image.png

如图所示,ArrayList底层通过数组实现。


一般的时候,我们只需要知道ArrayList的实际大小,但是作为一个优秀的程序员,知道ArrayList数组的容量大小非常重要,如果你想知道如何获取ArrayList的容量大小,可以参考如下文章:

Java如何获取ArrayList的容量(elemenData)大小?



四、域的解读


/**
 * 初始化默认容量。
 */
private static final int DEFAULT_CAPACITY = 10;
/**
 * 指定该ArrayList容量为0时,返回该空数组。
 */
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
 * 当调用无参构造方法,返回的是该数组。刚创建一个ArrayList 时,其内数据量为0。
 * 它与EMPTY_ELEMENTDATA的区别就是:该数组是默认返回的,而后者是在用户指定容量为0时返回。
 */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
 * 保存添加到ArrayList中的元素。
 * ArrayList的容量就是该数组的长度。
 * 该值为DEFAULTCAPACITY_EMPTY_ELEMENTDATA 时,当第一次添加元素进入ArrayList中时,数组将扩容值DEFAULT_CAPACITY。
 * 被标记为transient,在对象被序列化的时候不会被序列化。
 */
transient Object[] elementData; // non-private to simplify nested class access
/**
 * ArrayList的实际大小(数组包含的元素个数)。
 * @serial
 */
private int size;


思考:elementData被标记为transient,那么它的序列化和反序列化是如何实现的呢?

被标记为transient的属性在对象被序列化的时候不会被保存。

ArrayList自定义了它的序列化和反序列化方式。详情请查看writeObject(java.io.ObjectOutputStream s)和readObject(java.io.ObjectOutputStream s)方法。


相关文章
|
5月前
|
人工智能 安全 JavaScript
Java ArrayList:动态数组
本文探讨Java中的数组,对比C/C++、JS/PHP/Python等语言的数组特性。文章分析了Java数组的定义、创建方式及其规范,指出其优缺点。Java数组作为引用类型,在堆上分配内存,支持动态大小,避免了C/C++中裸数组的常见问题(如越界访问)。然而,Java数组也存在性能瓶颈和设计缺陷,例如运行时的安全检查影响速度,无法创建超大数组或泛型数组,且多线程场景下缺乏同步机制。作者建议在实际开发中用集合替代数组以规避这些问题。
123 1
|
28天前
|
安全 架构师 Java
Java LTS版本进化秀:从8到21的欢乐升级之旅
困惑于Java版本选择?轻松幽默地穿越Java LTS版本时光隧道,掌握从Java 8到21的关键特性。通过一家初创公司的系统升级故事,直观了解每个版本如何解决代码冗余、性能瓶颈等开发痛点,助你在技术选型中做出明智决策。
|
1月前
|
存储 小程序 Java
热门小程序源码合集:微信抖音小程序源码支持PHP/Java/uni-app完整项目实践指南
小程序已成为企业获客与开发者创业的重要载体。本文详解PHP、Java、uni-app三大技术栈在电商、工具、服务类小程序中的源码应用,提供从开发到部署的全流程指南,并分享选型避坑与商业化落地策略,助力开发者高效构建稳定可扩展项目。
|
3月前
|
Java 索引
Java ArrayList中的常见删除操作及方法详解。
通过这些方法,Java `ArrayList` 提供了灵活而强大的操作来处理元素的移除,这些方法能够满足不同场景下的需求。
421 30
|
2月前
|
Cloud Native Java API
Java Spring框架技术栈选和最新版本及发展史详解(截至2025年8月)-优雅草卓伊凡
Java Spring框架技术栈选和最新版本及发展史详解(截至2025年8月)-优雅草卓伊凡
383 0
|
3月前
|
安全 Java API
Java 17 及以上版本核心特性在现代开发实践中的深度应用与高效实践方法 Java 开发实践
本项目以“学生成绩管理系统”为例,深入实践Java 17+核心特性与现代开发技术。采用Spring Boot 3.1、WebFlux、R2DBC等构建响应式应用,结合Record类、模式匹配、Stream优化等新特性提升代码质量。涵盖容器化部署(Docker)、自动化测试、性能优化及安全加固,全面展示Java最新技术在实际项目中的应用,助力开发者掌握现代化Java开发方法。
144 1
|
5月前
|
JavaScript Java 关系型数据库
家政系统源码,java版本
这是一款基于SpringBoot后端框架、MySQL数据库及Uniapp移动端开发的家政预约上门服务系统。
170 6
家政系统源码,java版本
|
5月前
|
供应链 JavaScript 前端开发
Java基于SaaS模式多租户ERP系统源码
ERP,全称 Enterprise Resource Planning 即企业资源计划。是一种集成化的管理软件系统,它通过信息技术手段,将企业的各个业务流程和资源管理进行整合,以提高企业的运营效率和管理水平,它是一种先进的企业管理理念和信息化管理系统。 适用于小微企业的 SaaS模式多租户ERP管理系统, 采用最新的技术栈开发, 让企业简单上云。专注于小微企业的应用需求,如企业基本的进销存、询价,报价, 采购、销售、MRP生产制造、品质管理、仓库库存管理、财务应收付款, OA办公单据、CRM等。
319 23
|
4月前
|
存储 安全 Java
Java 集合面试题从数据结构到 HashMap 源码剖析详解及长尾考点梳理
本文深入解析Java集合框架,涵盖基础概念、常见集合类型及HashMap的底层数据结构与源码实现。从Collection、Map到Iterator接口,逐一剖析其特性与应用场景。重点解读HashMap在JDK1.7与1.8中的数据结构演变,包括数组+链表+红黑树优化,以及put方法和扩容机制的实现细节。结合订单管理与用户权限管理等实际案例,展示集合框架的应用价值,助你全面掌握相关知识,轻松应对面试与开发需求。
213 3
|
存储 Java 索引
【Java集合类面试二十四】、ArrayList和LinkedList有什么区别?
ArrayList基于动态数组实现,支持快速随机访问;LinkedList基于双向链表实现,插入和删除操作更高效,但占用更多内存。