从面试角度分析ArrayList源码

九路 等级 414 0 0

注:本系列文章中用到的jdk版本均为java8

ArrayList类图如下:

从面试角度分析ArrayList源码

ArrayList的底层是由数组实现的,数组的特点是固定大小,而ArrayList实现了动态扩容

ArrayList部分变量如下,在下面的分析中会用到这些变量。

/**
 * 默认容量
 */
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; 

一、初始化ArrayList

初始化ArrayList一般会使用以下两个构造器

1.1 无参构造器

初始化ArrayList的时候如果不指定大小,则会创建一个空数组。

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

1.2 指定数组大小的构造器

创建一个预估大小的数组,指定大小后只是指定了数组初始值的大小,不影响后面扩容,指定的好处就是可以节省内存及时间上的开销。

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.add(E e)源码:

public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
} 

add()elementData[size++] = e很好理解,就是将元素插入第size个位置,然后将size++,我们重点来看看ensureCapacityInternal(size + 1)方法;

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

ensureCapacityInternal()方法中判断缓存变量elementData是否为空,也就是判断是否是第一次添加元素,如果是第一次添加元素,则设置初始化大小为默认容量10,否则为传入的参数。这个方法的目的就是获取初始化数组容量。获取到初始化容量后调用ensureExplicitCapacity(minCapacity)方法;

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

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

ensureExplicitCapacity(minCapacity)方法用来判断是否需要扩容,假如第一次添加元素,minCapacity10elementData容量为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);
} 

grow(minCapacity)方法对数组进行扩容,扩容大小为原数组的1.5倍,如果计算出的扩容容量比需要的容量小,则扩容大小为需要的容量,如果扩容容量比数组最大容量大,则调用hugeCapacity(minCapacity)方法,将数组扩容为整数的最大长度,然后将elemetData数组指向新扩容的内存空间并将元素复制到新空间。

当需要的集合容量特别大时,扩容1.5倍就会非常消耗空间,因此建议初始化时预估一个容量大小。

三、删除元素

ArrayList提供两种删除元素的方法,可以通过索引元素进行删除。两种删除大同小异,删除元素后,将后面的元素一次向前移动。

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

删除元素时,首先会判断索引是否大于ArrayList的大小,如果索引范围正确,则将索引位置的下一个元素赋值到索引位置,将ArrayList的大小-1,最后返回移除的元素。操作图如下,假如我要移除索引为1的元素:

四、总结

ArrayList底层是数组实现的,可以进行动态扩容,扩容大小为原来的1.5倍,虽然可以通过动态扩容,但是数组非常大时会特别浪费空间,因此建议初始化时预估数组大小。ArrayList允许插入重复值和空值。ArrayList实现了RandomAccess接口,支持快速随机访问,就是可以通过索引快速查到某个元素,因此遍历时使用for循环的方式效率更高。ArrayList是线程不安全的,可以通过Collections.synchronizedList将其转变为线程安全的集合,不过一般不会使用,VectorCopyOnWriteArrayList是线程安全的,Vector性能一般,逐渐被CopyOnWriteArrayList取代了。

点关注、不迷路

如果觉得文章不错,欢迎关注点赞收藏,你们的支持是我创作的动力,感谢大家。

如果文章写的有问题,请不要吝惜文笔,欢迎留言指出,我会及时核查修改。

收藏
评论区

相关推荐

1 手写ArrayList核心源码
手写ArrayList核心源码 ArrayList是Java中常用的数据结构,不光有ArrayList,还有LinkedList,HashMap,LinkedHashMap,HashSet,Queue,PriorityQueue等等,我们将手写这些常用的数据结构的核心源码,用尽量少的代码来揭示核心原理。 下面我们来手写ArrayList的核心源码 首先
2 手写Java LinkedList核心源码
上一章我们手写了ArrayList的核心源码,ArrayList底层是用了一个数组来保存数据,数组保存数据的优点就是查找效率高,但是删除效率特别低,最坏的情况下需要移动所有的元素。在查找需求比较重要的情况下可以用ArrayList,如果是删除操作比较多的情况下,用ArrayList就不太合适了。Java为我们提供了LinkedList,是用链接来实现的,我们
从面试角度分析ArrayList源码
注:本系列文章中用到的jdk版本均为java8 ArrayList类图如下: ArrayList的底层是由数组实现的,数组的特点是固定大小,而ArrayList实现了动
List集合
Java的List集合 一、ArrayList 1.插入 java / 在元素序列尾部插入 / public boolean add(E e) { // 1. 检测是否需要扩容 ensureCapacityInternal(size 1); // Increments modCount // 2. 将新元素插入序列尾
Python中的基本list操作
List是python中的基本数据结构之一,和Java中的ArrayList有些类似,支持动态的元素的增加。list还支持不同类型的元素在一个列表中,List is an Object。 最基本的创建一个列表的方法 myList \'a','b','c'\ 在python中list也是对象,所以他也有方法和属性,在ptython解释器中 使用h
说说ArrayList的扩容机制
ArrayList是List接口的实现类,它是支持根据需要而动态增长的数组。java中标准数组是定长的,在数组被创建之后,它们不能被加长或缩短。这就意味着在创建数组时需要知道数组的所需长度,但有时我们需要动态程序中获取数组长度。ArrayList就是为此而生的,但是它不是线程安全的,外ArrayList按照插入的顺序来存放数据 ①ArrayList扩容发生
MySQL 8 复制(二)——半同步复制
目录 一、简介 直到目前的最新版本为止,MySQL缺省依然使用异步复制策略。简单说所谓异步复制,指的是主库写二进制日志、从库的I/O线程读主库的二进制日志写本地中继日志、从库的SQL线程重放中继日志,这三步操作都是异步进行的。如此选择的主要理由是出于性能考虑,与同步复制相比,异步复制显然更快,同时能承载更高的吞吐量。但异
ArrayList底层
一、ArrayList集合底层数据结构1.ArrayList集合介绍List集合的可调整大小数组实现。2.数组结构介绍 增删快:每次增加删除元素,都需要更改数组长度、拷贝以及移除元素位置。 查询快:由于数组在内存中是一块连续空间,因此可以根据地址索引的方式快速获
[C#]ArrayList、string、string[]之间的转换
1、ArrarList 转换为 string\[\] :  ArrayList list new ArrayList();  list.Add("aaa");  list.Add("bbb");  string\[\] arrString (string\[\])list.ToArray(typeof( string)) ;2、string\[\] 转换
Java集合之综合论述
1.Java集合 1.1 集合应用场景1. 无法预测存储数据的数量的情况下,2. 同时存储一对一关系的数据3. 需要进行数据的增删4. 数据重复问题 1.2 集合框架的体系结构 集合框架分为两类,一是Collection,用于存储类的对象。二是Map,以键值对的形式存储信息。 Collection主要有三个子接口,List(序列),Queue(队列
Java TreeMultiSet-为什么要开发这个数据结构???
TreeMultiSet基于TreeMap实现的支持可重复元素的TreeSet搞过java的人应该都知道TreeSet,但是TreeSet是不支持重复元素的。有人会说,那用ArrayList或LinkedList不就可以了吗?确实,ArrayList或LinkedList天然不去重,可以满足支持重复元素的需求。但是,我不仅需要支持可重复元素,而且需要数据实时
我丢,去面试初级Java开发岗位,被问到泛型?
1、泛型的基础概念 1.1 为什么需要泛型 c List list new ArrayList();//默认类型是Object list.add("A123"); list.add("B234"); list.add("C345"); System.out.println(list);
「JDK——ArrayList源码」超强解析,图文详解
ArrayList源码解析 简介ArrayList是Java集合框架中非常常用的一种数据结构。继承自AbstractList,实现了List接口。底层基于数组来实现动态容量大小的控制,允许null值的存在。同时还实现了RandomAccess、Cloneable、Serializable接口,支持快速访问、复制、序列化操作。 了解数组数组简单来说就是将所有的
简简单单复习一哈ArrayList和Arrays.asList()
1、面向对象补充(详见面试补充) 基于JDK11静态代码块 非静态代码块 无参/有参构造在同一次编译运行时,静态代码块只会被调用一次ListArrayList (数组,初始容量为10)注: 除了通过 Iterator 自己的remove或add方法,迭代器将抛出ConcurrentModificationException 。 因此,面对并
世道变了,面试初级Java开发会问到Arrays!!!你不会还不知道吧!
](https://shimo.im/docs/9GTP6XrJg9J88cJD/) 一、基本定义Arrays类,全路径java.util.Arrays,主要功能为操作数组,Arrays类的所有方法均为静态方法,所以调用方式全部为Arrays.方法名 二、常用方法c1. <T List<T asList(T... a)可以将数组转化为相应的list集合,但