纯净、安全、绿色的下载网站

首页|软件分类|下载排行|最新软件|IT学院

当前位置:首页IT学院IT技术

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

zx2015216856   2021-09-13 我要评论
想了解Java中的ArrayList容量及扩容方式的相关内容吗zx2015216856在本文为您仔细讲解Java ArrayList容量扩容的相关知识和一些Code实例欢迎阅读和指正我们先划重点: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 倍!

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


相关文章

猜您喜欢

  • c++写推箱子小游戏 利用c++写一个简单的推箱子小游戏

    想了解利用c++写一个简单的推箱子小游戏的相关内容吗诗一样的代码在本文为您仔细讲解c++写推箱子小游戏的相关知识和一些Code实例欢迎阅读和指正我们先划重点:c++推箱子游戏代码,推箱子游戏代码,C语言写推箱子游戏下面大家一起来学习吧..
  • C++内存模型和名称空间 C++内存模型和名称空间详解

    想了解C++内存模型和名称空间详解的相关内容吗Briwisdom在本文为您仔细讲解C++内存模型和名称空间的相关知识和一些Code实例欢迎阅读和指正我们先划重点:C++内存模型,C++名称空间下面大家一起来学习吧..

网友评论

Copyright 2020 www.sopisoft.net 【绿软下载站】 版权所有 软件发布

声明:所有软件和文章来自软件开发商或者作者 如有异议 请与本站联系 点此查看联系方式