Java中的ArrayList容量及扩容方式

目录
  • 查看JDK1.8 ArrayList的源代码
    • 1、默认初始容量为10
    • 2、最大容量为 Integer.MAX_VALUE - 8
    • 3、扩容方式:
  • Java ArrayList() 扩容原理
    • 先看下 ArrayList 的属性以及构造方法,这个比较重要
    • 上看说的是初始化场景,下面看一下其他场景,也是相当简单
    • 结论

查看JDK1.8 ArrayList的源代码

1、默认初始容量为10

   /**
     * Default initial capacity.
     */
    private static final int DEFAULT_CAPACITY = 10;

2、最大容量为 Integer.MAX_VALUE - 8

    /**
     * The maximum size of array to allocate.
     * Some VMs reserve some header words in an array.
     * Attempts to allocate larger arrays may result in
     * OutOfMemoryError: Requested array size exceeds VM limit
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

原因:之前参考别人的,有待求证:

数组对象有一个额外的元数据,用于表示数组的大小;

数组长度size为int类型,共32位,有一位符号位,所以最大长度为Integer.MAX_VALUE=2^31= 2,147,483,648;

8bytes用来存储size;

3、扩容方式:

(1)首先传递进来一个希望的最小容量minCapacity;

(2)新容量newCapacity = oldCapacity + (oldCapacity >> 1),即新容量等于原容量的1.5倍;

(3)如果minCapacity > newCapacity ,newCapacity = minCapacity ;

(4)如果 newCapacity > 最大容量 MAX_ARRAY_SIZE ,newCapacity = hugeCapacity(minCapacity);

(5)以新容量拷贝原数据

   /**
     * Increases the capacity to ensure that it can hold at least the
     * number of elements specified by the minimum capacity argument.
     *
     * @param minCapacity the desired minimum capacity
     */
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        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);
    }

    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }

Java ArrayList() 扩容原理

平常都是直接使用 ArrayList(),今天特地看一下 ArrayList() 的扩容原理。

先看下 ArrayList 的属性以及构造方法,这个比较重要

先看下属性

// ArrayList 默认容量大小
private static final int DEFAULT_CAPACITY = 10;
// 一个共享的空数组, 在空实例时使用
private static final Object[] EMPTY_ELEMENTDATA = {};
// 一个共享的空数组, 在使用默认 size 的空实例时使用
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/*
存储 ArrayList 元素的数组缓冲区
重点1: ArrayList 的容量是数组缓冲区的长度
重点2: 从这个元素也可以看的出来 ArrayList() 的底层就是一个 Object[]
add 第一个元素时, 任何带有 elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的空 ArrayList 都将被扩展为 DEFAULT_CAPACITY
*/
transient Object[] elementData;
// ArrayList 的大小, 我们平常使用的 list.size() 底层就是记录的这个 size
private int size;
// ArrayList 最大
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

再看构造器,带参构造器

/*
带参构造器, 参数为容量大小, 例如: 初始化一个容器为 20 类型为 Integer 的 ArrayList
ArrayList<Integer> list = new ArrayList<>(20);
*/
public ArrayList(int initialCapacity) {
 /*
 初始化容量 > 0, elementData 初始化为初始化容量大小的数组
 初始化容量 = 0, elementData = EMPTY_ELEMENTDATA (空数组)
 初始化容量 < 0, 直接抛出异常
 */
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                           initialCapacity);
    }
}

参数为 Collection 的构造器

/*
将一个参数为 Collection 的集合转换为 ArrayList
*/
public ArrayList(Collection<? extends E> c) {
    // Collection 转换为数组 Object[] 类型
    elementData = c.toArray();
    // 判断当前对象大小是否和 Collection 长度相等并且不等于 0, false 的话 elementData 等于空数组了
    if ((size = elementData.length) != 0) {
     // c.toArray() 可能不会正确地返回一个 Object[] 数组,所以使用 Arrays.copyOf()
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

不带参构造器

/*
不带参构造器就像我们平时使用一样, 直接 new 一个 ArrayList 不需要传递任何参数
构造方法中直接将 elementData 初始化为 DEFAULTCAPACITY_EMPTY_ELEMENTDATA (空数组)
*/
public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

看到这里就发现,带参的构造器我们可以直接传递参数,而默认的构造器怎么怎么样初始化容量大小的呢?

add() 方法可以直接得到答案。

public boolean add(E e) {
 // 这一行是关键, 看下面
    ensureCapacityInternal(size + 1);
    // 将元素追加到集合的末尾 假如当前 size = 10 size++ 追加到第 11 位
    elementData[size++] = e;
    return true;
}

ensureCapacityInternal() 方法调用

private void ensureCapacityInternal(int minCapacity) {
 /*
 calculateCapacity() 方法, 刚初始化时会返回 10, 其他情况返回当前 size + 1
 ensureExplicitCapacity() 方法, 调用扩容
 */
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
 /*
 使用无参构造器创建创建 ArrayList 的集合, 此时一定是相等的
 */
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
     /*
     两数相比返回最大值, 此时 Math.max(10, 1);
     默认容量, 由此而来
     */
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    // 不相等的话只有返回当前的 size + 1
    return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
    // 增量, 记录修改/更新次数
    modCount++;  

     // 初始化: 10 - 0 > 0
     // 其他: size + 1 > 0
    if (minCapacity - elementData.length > 0)
     // 扩容操作
        grow(minCapacity);
}
private void grow(int minCapacity) {
    // 老的长度, 初始化时为 0,
    int oldCapacity = elementData.length;
    // 新的长度此时 0 + (0 >> 1), newCapacity = 0
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 初始化场景: 0 - 10 < 0 ? true newCapacity = 10
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 初始化场景: 10 - 2147483639 > 0 返回 false
    if (newCapacity - MAX_ARRAY_SIZE > 0)
     // 超大长度才可以执行这个方法, 必须大于 MAX_ARRAY_SIZE 一般不会
        newCapacity = hugeCapacity(minCapacity);
    // 复制原数组中的元素, 并扩容
    elementData = Arrays.copyOf(elementData, newCapacity);
}

上看说的是初始化场景,下面看一下其他场景,也是相当简单

private void ensureCapacityInternal(int minCapacity) {
 /*
 calculateCapacity() 方法, 正常扩容返回 size + 1, 比如 10 + 1, 因为默认长度为 10 当再次新增数据时就会出发扩容
 ensureExplicitCapacity() 方法, 调用扩容
 */
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    /*
 elementData 不等于空数组
 返回当前的 size + 1, 即 10 + 1 返回 11
 */
    return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
    // 增量, 记录修改/更新次数
    modCount++;  

    // 其他: 11 - 10 > 0 true, 触发扩容, 如果当前下表是 5 的话 5 + 1 =6, 6 < 10 是, 此时不会出发扩容
    if (minCapacity - elementData.length > 0)
     // 扩容操作
        grow(minCapacity);
}
private void grow(int minCapacity) {
    // 老的长度 10
    int oldCapacity = elementData.length;
    // 新的长度此时 10 + (10 >> 1), newCapacity = 15
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    // 15 - 11 < 0 ? false
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 15 - 2147483639 > 0 返回 false
    if (newCapacity - MAX_ARRAY_SIZE > 0)
     // 超大长度才可以执行这个方法, 必须大于 MAX_ARRAY_SIZE 一般不会
        newCapacity = hugeCapacity(minCapacity);
    // 复制原数组中的元素, 并扩容 newCapacity = 15
    elementData = Arrays.copyOf(elementData, newCapacity);
}

结论

1、 触发扩容的关键是

当前 size + 1 是否大于当前容量,如果大于容量则证明,集合不够用了,需要扩容。如果小与当前容量则证明集合还有容量不需要扩容!

2、 每次扩容的大小是

oldCapacity + (oldCapacity >> 1) 即: 10 + (10 >> 1)

即:当前容量的 1.5 倍!

以上为个人经验,希望能给大家一个参考,也希望大家多多支持我们。

(0)

相关推荐

  • 详解ArrayList的扩容机制

    目录 一.ArrayList 了解过吗?它是啥?有啥用? 二.ArrayList 如何指定底层数组大小的 三.数组的大小一旦被规定就无法改变 四.ArrayList 具体是怎么添加数据的 五.ArrayList 又是如何删除数据的呢 六.ArrayList 是线程安全的吗?不安全的表现 七.为什么线程不安全还要用它呢 一.ArrayList 了解过吗?它是啥?有啥用? 众所周知,Java 集合框架拥有两大接口 Collection 和 Map,其中,Collection 麾下三生子 List.S

  • Java中Arraylist动态扩容方法详解

    前言 本文主要给大家介绍了关于Java中Arraylist动态扩容的相关内容,分享出来供大家参考学习,下面话不多说了,来一起看看详细的介绍吧. ArrayList 概述 ArrayList是基于数组实现的,是一个动态数组,其容量能自动增长.ArrayList不是线程安全的,只能用在单线程环境下.实现了Serializable接口,因此它支持序列化,能够通过序列化传输:实现了RandomAccess接口,支持快速随机访问,实际上就是通过下标序号进行快速访问:实现了Cloneable接口,能被克隆.

  • Java基础之ArrayList的扩容机制

    我们知道Java中的ArrayList对象底层是基于数组实现的,而数组是有长度限制的,那基于数组实现的ArrayList是否有长度限制呢?我们通过ArrayList的构造方法来剖析 ArrayList提供了3种构造方法以便我们来获取: ArrayList(int initialCapacity) 第一种需要赋值长度进行new ArrayList() 第二种无参构造,不需要赋值数组初始长度 ArrayList(Collection<? extends E> c) 第三种入参一个继承了Collec

  • Java使用数组实现ArrayList的动态扩容的方法

    提到数组大家肯定不会陌生,但我们也知道数组有个缺点就是在创建时就确定了长度,之后就不能更改长度.所以Java官方向我们提供了ArrayList这个可变长的容器.其实ArrayList底层也是用数组进行实现的,今天我们就自己使用数组实现ArrayList的功能. 一.整体框架 废话不多说,我们以存放int类型元素为例,看一下ArrayList需要的成员变量和需要实现的方法. public class ArrayList private int size;//用来记录实际存储元素个数 private

  • Java中的ArrayList容量及扩容方式

    目录 查看JDK1.8 ArrayList的源代码 1.默认初始容量为10 2.最大容量为 Integer.MAX_VALUE - 8 3.扩容方式: Java ArrayList() 扩容原理 先看下 ArrayList 的属性以及构造方法,这个比较重要 上看说的是初始化场景,下面看一下其他场景,也是相当简单 结论 查看JDK1.8 ArrayList的源代码 1.默认初始容量为10 /** * Default initial capacity. */ private static final

  • Java中为什么ArrayList初始化容量大小为10

    目录 背景 为什么HashMap的初始化容量为16? ArrayList的初始化容量是10吗? 为什么ArrayList的初始化容量为10? 小结 背景 看ArrayList源码时,无意中看到ArrayList的初始化容量大小为10,这就奇怪了!我们都知道ArrayList和HashMap底层都是基于数组的,但为什么ArrayList不像用HashMap那样用16作为初始容量大小,而是采用10呢? 于是各方查找资料,求证了这个问题,这篇文章就给大家讲讲. 为什么HashMap的初始化容量为16?

  • 盘点Java中延时任务的多种实现方式

    目录 场景描述 实现方式 一.挂起线程 二.ScheduledExecutorService 延迟任务线程池 三.DelayQueue(延时队列) 四.Redis-为key指定超时时长,并监听失效key 五.时间轮 六.消息队列-延迟队列 场景描述 ①需要实现一个定时发布系统通告的功能,如何实现? ②支付超时,订单自动取消,如何实现? 实现方式 一.挂起线程 推荐指数:★★☆ 优点: JDK原生(JUC包下)支持,无需引入新的依赖: 缺点: (1)基于内存,应用重启(或宕机)会导致任务丢失 (2

  • Java中实现线程的三种方式及对比_动力节点Java学院整理

    Java中创建线程主要有三种方式: 一.继承Thread类创建线程类 (1)定义Thread类的子类,并重写该类的run方法,该run方法的方法体就代表了线程要完成的任务.因此把run()方法称为执行体. (2)创建Thread子类的实例,即创建了线程对象. (3)调用线程对象的start()方法来启动该线程. package com.thread; public class FirstThreadTest extends Thread{ int i = 0; //重写run方法,run方法的方

  • 浅谈java中String的两种赋值方式的区别

    类似普通对象,通过new创建字符串对象.String str = new String("Hello"); 内存图如下图所示,系统会先创建一个匿名对象"Hello"存入堆内存(我们暂且叫它A),然后new关键字会在堆内存中又开辟一块新的空间,然后把"Hello"存进去,并且把地址返回给栈内存中的str, 此时A对象成为了一个垃圾对象,因为它没有被任何栈中的变量指向,会被GC自动回收. 直接赋值.如String str = "Hello&

  • 浅谈Java中实现深拷贝的两种方式—clone() & Serialized

    clone() 方法麻烦一些,需要将所有涉及到的类实现声明式接口 Cloneable,并覆盖Object类中的clone()方法,并设置作用域为public(这是为了其他类可以使用到该clone方法). 序列化的方法简单,需要将所有涉及到的类实现接口Serializable package b1ch06.clone; import java.io.Serializable; class Car implements Cloneable, Serializable { private String

  • Java中遍历ConcurrentHashMap的四种方式详解

    这篇文章主要介绍了Java中遍历ConcurrentHashMap的四种方式详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 方式一:在for-each循环中使用entries来遍历 System.out.println("方式一:在for-each循环中使用entries来遍历");for (Map.Entry<String, String> entry: map.entrySet()) { System.out.pr

  • 区分Java中的ArrayList和LinkedList

    一:ArrayList和LinkedList的大致区别如下: 1.ArrayList是实现了基于动态数组的数据结构,ArrayList实现了长度可变的数组,在内存中分配连续的空间.遍历元素和随机访问元素的效率比较高 2.LinkedList基于链表的数据结构, 插入.删除元素时效率比较高  故:[插入.删除操作频繁时,可使用LinkedList来提高效率]LinkedList提供对头部和尾部元素进行添加和删除操作的方法,插入/删除第一个和最后一个效率比较高: 3:ArrayList和Linked

  • Java中switch的三种用法方式

    Java中switch的三种用法详解: switch居然有三种方式 ? 作为一个接触java不久的人来说,这确实让我吃了一惊! 根据版本,在java14开始, switch语句有了一个很大的调整, 这就让swicth语句有了更多的操作和选择,在代码上,更加的简便灵活, 让我们试试这神奇的switch吧! 使用switch这个关键词, 我们可以很好的解决if-else 中多重选择的尴尬场面! Java中switch的三种用法详解: switch 标准方式 switch - > 用法: switch

  • Java中获取时间戳的三种方式对比实现

    Java中获取时间戳 三种方式对比 最近项目开发过程中发现了项目中获取时间戳的业务.而获取时间戳有以下三种方式,首先先声明推荐使用System类来获取时间戳,下面一起看一看三种方式. 1.System.currentTimeMillis() System类中的currentTimeMillis()方法是三种方式中效率最好的,运行时间最短.开发中如果设计到效率问题,推荐使用此种方式获取. System.currentTimeMillis() 2.new Date().getTime() 除了Sys

随机推荐