IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> ArrayList扩容机制 -> 正文阅读

[数据结构与算法]ArrayList扩容机制

ArrayList扩容机制

在ArrayList中,声明了三个常量

private static final int DEFAULT_CAPACITY = 10;//默认容量大小为10
private static final Object[] EMPTY_ELEMENTDATA = {};//一个空数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};//一个默认容量的空数组

还声明了一个数组

transient Object[] elementData; // non-private to simplify nested class access

然后再看一下ArrayList的构造方法

这是无参构造

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

这是有参构造

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方法添加元素时会进行扩容

add方法有三个,看一下常用add方法的源码

public boolean add(E e) {
        modCount++;
        add(e, elementData, size);
        return true;
    }
private void add(E e, Object[] elementData, int s) {
        if (s == elementData.length)
            elementData = grow();
        elementData[s] = e;
        size = s + 1;
    }

调用boolean add(E e),首先让modCount++,这是用来记录数组被修改次数的变量,我们先不管它,此时size值为0,再调取void add(E e, Object[] elementData, int s)这个方法,将初始化的elementData,e, 还有size传过去,在这个add方法中先判断数组长度是否与size相等,如果相等,则调用grow()方法进行扩容,扩容后再将e插入到elementData最后,size+1。

看一下grow方法的源码

private Object[] grow() {
        return grow(size + 1);
    }

private Object[] grow(int minCapacity) {
        return elementData = Arrays.copyOf(elementData,
                                           newCapacity(minCapacity));
    }

add方法调用grow的无参方法,无参grow方法又调用带参grow方法,并传入size+1。

在grow方法中,返回一个elementData,elementData等于Arrays.coptOf(element, newCapacity(minCapacity)),这个Arrays.copyOf是一个数组复制方法,将elementData数组赋给newCapacity(minCapacity)返回的新数组中。接着就是重点了,看newCapacity(minCapacity)方法的源码

private int newCapacity(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity <= 0) {
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
                return Math.max(DEFAULT_CAPACITY, minCapacity);
            if (minCapacity < 0) // overflow
                throw new OutOfMemoryError();
            return minCapacity;
        }
        return (newCapacity - MAX_ARRAY_SIZE <= 0)
            ? newCapacity
            : hugeCapacity(minCapacity);
    }

在这个方法中有一个oldCapacity,表示旧的数组容量,还有一个newCapacity表示扩容后的数组容量,这个容量为oldCapacity+(oldCapacity >> 1),这里有一个位运算,表示将oldCapacity右移一位,在二进制中,右移一位相当于除以二,下面举例说明:

十进制2用二进制表示为10,右移一位后变为1,也就是十进制的1
十进制6用二进制表示为110,右移一位后变为11, 也就是十进制的3

所以扩容后的容量相当于oldCapacity * (Capacity / 2),也就有了ArrayList每次扩容都是原来1.5倍的说法。

扩容后判断是否小于minCapacity(注:minCapacity的值为grow传入的size+1),若小于,判断elementData是否为默认大小的空数组,若是,则返回minCapaacity与默认大小比较后的最大值。

若不是,再判断minCapacity是否小于0,若小于0,则抛出异常。最后再返回minCapacity。

oldCapacity由于扩容后没有引用,很快就会被垃圾回收器回收掉,再调用add方法时,还会再走一遍扩容流程,由于此时数组已经经过了一次扩容,他的size与elementData.length不同,直接插入即可,当到达上限后在进行下此次扩容。

我们可以写一段代码来查看ArrayList的容量

获取ArrayList当前容量

import java.lang.reflect.Field;
import java.util.ArrayList;

public class Test{
    public static void main(String args[]) {
        ArrayList<Integer> arrayList = new ArrayList<>();

        System.out.println(getArrayListCapacity(arrayList));

        //增加元素,使其扩容
        arrayList.add(0);
        System.out.println(getArrayListCapacity(arrayList));

        for(int i = 0; i < 10; ++i)
            arrayList.add(0);
        System.out.println(getArrayListCapacity(arrayList));

        for(int i = 0; i < 5; ++i)
            arrayList.add(0);
        System.out.println(getArrayListCapacity(arrayList));
    }

    public static int getArrayListCapacity(ArrayList<?> arrayList) {
        Class<ArrayList> arrayListClass = ArrayList.class;
        try {
            Field field = arrayListClass.getDeclaredField("elementData");
            field.setAccessible(true);
            Object[] objects = (Object[])field.get(arrayList);
            return objects.length;
        } catch (NoSuchFieldException e) {
            e.printStackTrace();
            return -1;
        } catch (IllegalAccessException e) {
            e.printStackTrace();
            return -1;
        }
    }
}

输出结果

0
10
15
22

以上均为个人理解,如有错误,欢迎指正,不胜感激。

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-04-29 12:21:18  更:2022-04-29 12:23:24 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/26 6:33:24-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码