从面试角度分析ArrayList源码

九路 等级 601 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的核心源码 首先
从面试角度分析ArrayList源码
注:本系列文章中用到的jdk版本均为java8 ArrayList类图如下: ArrayList的底层是由数组实现的,数组的特点是固定大小,而ArrayList实现了动
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\[\] 转换
C#泛型
现在的netcore 3.1和最新的.netframework8早已经没有当初那个被人诟病的ArrayList了,但很巧这玩意不得不说,因为它决定了C#团队痛改前非,抛弃过往重新上路,上一段ArrayList案例代码。 public class ArrayList { private object[]
Java 笔记
*  动态数组 ArrayList<String> List = new ArrayList<String>(); //定义动态数组 List.add(temp); //添加字符串 List<Integer> ret = new ArrayList<Integer>(); ret.add(i+1);
Java集合面试题
**Collection** Set和hashCode以及equals方法的联系 Set内存放的元素为什么不可以重复,内部是如何保证和实现的? List 和 Set 区别 List 和 Map 区别 Arraylist 与 LinkedList 区别 ArrayList 与 Vector 区别 Arraylist与LinkedList默认空间是
java.lang.UnsupportedOperationException
java.lang.UnsupportedOperationException 博客分类: java    在使用Arrays.asList()后调用add,remove这些method时出现 java.lang.UnsupportedOperationException异常。这是由于Arrays.asList() 返回java.util.Arrays$A
50道Java集合经典面试题(收藏版)
前言 -- 来了来了,50道Java集合面试题来了! ### 1\. Arraylist与LinkedList区别 可以从它们的底层数据结构、效率、开销进行阐述哈 * ArrayList是数组的数据结构,LinkedList是链表的数据结构。 * 随机访问的时候,ArrayList的效率比较高,因为LinkedList要移动指针,而
ArrayList源码分析
一、先看下ArrayList的构造方法源码 --------------------- public ArrayList(int initialCapacity) { super(); if (initialCapacity < 0) throw new IllegalArgumentExc
ArrayList源码分析(JDK1.8)
概述 -- ArrayList底层是基于 **数组** 实现的,并且支持 **动态扩容** 的动态数组(变长的集合类)。ArrayList允许空值和重复的元素,当向ArrayList中添加元素数量大于其底层数组容量时,会通过 **扩容机制** 重新生成一个容量更大的数组。另外,由于ArrayList底层数据结构是数组,所以保证了在O(1)复杂度下完成随机查
ArrayList源码解读(jdk1.8)
### **概要** 上一章,我们学习了Collection的架构。这一章开始,我们对Collection的具体实现类进行讲解;首先,讲解List,而List中ArrayList又最为常用。因此,本章我们讲解ArrayList。先对ArrayList有个整体认识,再学习它的源码,最后再通过例子来学习如何使用它。内容包括: 第1部分 ArrayList简
Copy ArrayList的四种方式
Copy ArrayList的四种方式 简介 == ArrayList是我们经常会用到的集合类,有时候我们需要拷贝一个ArrayList,今天向大家介绍拷贝ArrayList常用的四种方式。 使用构造函数 ====== ArrayList有个构造函数,可以传入一个集合: public ArrayList(Collection<? e
JSTL empty判断空值
<% String str1=null; String str2=""; String str3="aa"; ArrayList al1=null; ArrayList al2=new ArrayList(); ArrayList al3=new ArrayList();
List接口(动态数组)
List接口(动态数组) ============ List集合类中元素_**有序且可重复**_ ArrayList(重要) ------------- * 作为List接口的主要实现类 * 线程不安全的,效率高 * 底层使用Object\[\] elementData数组存储 ### ArrayList的源码分析 #### jdk7