热门标签 | HotTags
当前位置:  开发笔记 > 运维 > 正文

在java中ArrayList集合底层的扩容原理

这篇文章主要介绍了在java中ArrayList集合底层的扩容原理,文中有非常详细的代码示例,对正在学习java的小伙伴们有一定的帮助,需要的朋友可以参考下

第一章 前言概述

第01节 概述

底层说明

ArrayList是List的实现类,它的底层是用Object数组存储,线程不安全

后期应用

适合用于频繁的查询工作,因为底层是数组,可以快速通过数组下标进行查找

第02节 区别

区别方向 ArrayList集合 LinkedList集合
线程安全 不安全 不安全
底层原理 Object类型数组 双向链表
随机访问 支持(实现 RandomAccess接口) 不支持
内存占用 ArrayList 浪费空间, 底层是数组,末尾预留一部分容量空间 LinkedList占用空间比ArrayList多,存在头尾地址值占用空间

小结

ArrayList 集合的特点:

1. 线程不安全

2. 底层数据结构是数组(查询快,增删慢,支持快速随机访问)

3. 内存占用会存在部分浪费,末尾会预留一部分容量空间

第二章 核心代码

第01节 成员变量

代码

public class ArrayList extends AbstractList implements List, RandomAccess, Cloneable, java.io.Serializable{ 

	/**
	 * 默认初始容量大小, 默认初始化容量为10
	 */
	private static final int DEFAULT_CAPACITY = 10;

	/**
	 * 空数组。当集合内容置空的时候,底层使用空数组标记
	 */
	private static final Object[] EMPTY_ELEMENTDATA = {};

	/**
	* 用于无参数构造方法,创建对象的时候,使用这个数组定义。
	* 相比上面的数组 EMPTY_ELEMENTDATA 可以进行区分,知道在添加元素的过程当中,容量增加多少
	*/
	private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

	/**
	 * 保存ArrayList数据的数组,这个数组会不断的改变,前面没有被 final 修饰表示地址值会发生的变化
	 */
	transient Object[] elementData; // non-private to simplify nested class access

	/**
	 * ArrayList 所包含的元素个数,也就是在 ArrayList 集合底层,通过 size()方法,获取到的元素个数
	 */
	private int size; 
}

补充

1. ArrayList 集合底层存在6个成员变量
	还有一个 private static final long serialVersiOnUID= 8683452581122892189L;  
	序列化使用, 目前针对于当前的操作过程当中, 暂时不会使用得到。

2. ArrayList 集合当中核心的两个成员变量
	A. 底层维护数组  		transient Object[] elementData;
	B. 存储的元素个数		private int size; 

第02节 构造方法

代码

public class ArrayList extends AbstractList implements List, RandomAccess, Cloneable, java.io.Serializable{ 

    /**
     * 构造一个初始长度为0的空数组。
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    /**
     * 在构造方法当中,传递一个参数集合c,将集合 c 转换成为新的列表
	 * elementData 当中的数据,就是新集合存放的数据
     * c.toArray 就是将原始集合的数据取出
	 * 如果取出的集合长度不为零的情况下,则复制 参数集合c 到 elementData 当中
	 * 如果取出的集合长度为零的情况下,则赋值为空数组  EMPTY_ELEMENTDATA 
     */
    public ArrayList(Collection<&#63; extends E> c) {
        elementData = c.toArray();
        if ((size = elementData.length) != 0) { 
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else { 
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }
	
	 /**
     * 指定参数的长度大小
	 * 如果初始化的长度大于0,则返回新的数组
	 * 如果初始化的长度等于0,则返回默认的空数组作为集合 this.elementData = EMPTY_ELEMENTDATA;
	 * 如果初始化的长度小于0,则出现非法参数异常
     */
    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);
        }
    }
}

补充(一) 无参构造创建对象

在这里插入图片描述

补充(二)带参构造创建对象,带有int类型参数

在这里插入图片描述

补充(三)带参构造创建对象,带有 集合类型参数

在这里插入图片描述

第三章 扩容操作

第01节 扩容代码

核心方法介绍

来自于 ArrayList 集合当中的方法:
	1. public boolean add(E e){ ... }
	2. private void add(E e, Object[] elementData, int s){ .... }
	3. private Object[] grow()
	4. private Object[] grow(int minCapacity)

来自于其他类当中的功能
	1. Arrays.copyOf(elementData, newCapacity);  表示来自于 数组工具类 Arrays 当中的 copyOf() 底层使用的是 System.arraycopy() 方法
	2. Math.max(DEFAULT_CAPACITY, minCapacity)   表示来自于 数学工具类 Math 当中的 max() 方法,比较两个数据最大值,取较大者,返回

核心代码解释

public class ArrayList extends AbstractList implements List, RandomAccess, Cloneable, java.io.Serializable{ 

    /**
     * 将指定的元素添加到此集合的末尾位置
     *
     * modCount 是来自于父类的 AbstractList 当中的成员变量
     * add(e, elementData, size) 调用自己下面的重载方法
	 * return true  表示当前的方法,一定可以添加成功,因为List系列的集合添加数据都是允许成功的 true 如果是Set此方法返回false
     */
    public boolean add(E e) {
        modCount++;
        add(e, elementData, size);
        return true;
    }
	
	
	/**
     * 这个方法是私有方法,仅仅自己可以使用。不允许外界访问得到。便于上面的 add() 方法重载调用的
	 * 参数1: 表示需要添加的元素数据 E e
	 * 参数2: 表示成员变量当中, 需要维护管理的底层数组  Object[] elementData
     * 参数3: 表示成员变量当中, size 容器 elementData 当中存放的真实有效的数据个数
	 * 方法里面的逻辑: 当size已经等于了内部容器 elementData 的最大长度,则准备进行扩容的操作,扩容使用 grow() 方法
	 * 无论上面是否进行了扩容的操作,这里都需要将添加的元素赋值到数组当中,也就是 elementData[s] = e;
	 * 并且将当前成员变量的 size 在原始数据的基础上面,增加1,表示添加了新的元素之后,长度变化了,增加了1
     */
    private void add(E e, Object[] elementData, int s) {
        if (s == elementData.length)
            elementData = grow();
        elementData[s] = e;
        size = s + 1;
    }
	
	
	/**
     * 这个方法是私有方法,仅仅自己可以使用。不允许外界访问得到。便于上面的 add() 方法调用的
	 * 方法的内部调用了 ArrayList 当中自己重载的方法 grow(size + 1) 同时传入了参数。
	 * 这里参数的含义,表示的是 集合当中总长度 size + 1 表示在原始size基础上增加1 
	 * 方法的返回值是一个新的数组,也就是扩容之后的数组
     */
	private Object[] grow() {
        return grow(size + 1);
    }


    /**
     * 这个方法是私有方法,仅仅自己可以使用。不允许外界访问得到。便于上面的 grow() 方法调用的
	 * 这里的参数 minCapacity ,就是上面传入的参数 size + 1,也就是说最小容量 minCapacity = size + 1
	 * 方法体当中的执行逻辑:
	 * 		1. 获取到了底层维护数组的长度 int oldCapacity = elementData.length; 这里就是旧容量 oldCapacity
	 *      2. 判断旧容量 oldCapacity 是否小于0,也就是 else 的逻辑,
	 *				如果满足 if 当中的逻辑, 则表示 旧数组当中存在数据,并且 旧数组并不是 默认容量的空数组地址值
	 *					说明: 扩容过的就不会是之前默认 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的地址值
	 *					在这种情况下,就会得到 1.5被的数组长度整数,传递给 Arrays.copyOf()方法进行扩容,得到新数组返回
	 * 				如果满足 else 当中的逻辑,则返回 DEFAULT_CAPACITY 和 minCapacity 较大值。
	 * 					说明: DEFAULT_CAPACITY 值表示的是成员变量,默认为 10   
	 *					说明: minCapacity 在低于10的时候,表示的会是扩容添加的长度1,2,3..9.10.11..
     */
    private Object[] grow(int minCapacity) {
        int oldCapacity = elementData.length;
        if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            int newCapacity = ArraysSupport.newLength(oldCapacity,
                    minCapacity - oldCapacity, /* minimum growth */
                    oldCapacity >> 1           /* preferred growth */);
            return elementData = Arrays.copyOf(elementData, newCapacity);
        } else {
            return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
        }
    }
}

到此这篇关于在java中ArrayList集合底层的扩容原理的文章就介绍到这了,更多相关ArrayList集合扩容原理内容请搜索以前的文章或继续浏览下面的相关文章希望大家以后多多支持!


推荐阅读
  • 顶新国际PMI集团与美云智数再次携手,共同开启“数智化”采购的新篇章。顶新国际集团作为中国领先的综合食品企业,成立于1958年,旗下品牌包括著名的方便面品牌康师傅、快餐品牌德克士以及开创中国便利店先河的全家FamilyMart。此次合作将借助美云智数在数字化转型领域的专业优势,进一步提升顶新国际的供应链管理效率和智能化水平,推动其在竞争激烈的市场环境中实现可持续发展。 ... [详细]
  • 提升 Kubernetes 集群管理效率的七大专业工具
    Kubernetes 在云原生环境中的应用日益广泛,然而集群管理的复杂性也随之增加。为了提高管理效率,本文推荐了七款专业工具,这些工具不仅能够简化日常操作,还能提升系统的稳定性和安全性。从自动化部署到监控和故障排查,这些工具覆盖了集群管理的各个方面,帮助管理员更好地应对挑战。 ... [详细]
  • 《Spring in Action 第4版:全面解析与实战指南》
    《Spring in Action 第4版:全面解析与实战指南》不仅详细介绍了Spring框架的核心优势,如简洁易测试、低耦合特性,还深入探讨了其轻量级和最小侵入性的设计原则。书中强调了声明式编程的优势,并通过基于约定的方法简化开发流程。此外,Spring的模板机制有效减少了重复代码,而依赖注入功能则由容器自动管理,确保了应用的灵活性和可维护性。 ... [详细]
  • 在日常的项目开发中,测试环境和生产环境通常采用HTTP协议访问服务。然而,从浏览器的角度来看,这种访问方式会被标记为不安全。为了提升安全性,当前大多数生产环境已经转向了HTTPS协议。本文将详细介绍如何在Spring Boot应用中配置SSL证书,以实现HTTPS安全访问。通过这一过程,不仅可以增强数据传输的安全性,还能提高用户对系统的信任度。 ... [详细]
  • 本文探讨了使用Python进行微服务架构设计的合理性和适用性。首先,介绍了微服务的基本概念及其在现代软件开发中的重要性。接着,通过具体的业务场景,详细分析了Python在微服务架构设计中的优势和挑战。文章还讨论了在实际应用中可能遇到的问题,并提出了相应的解决方案。希望本文能够为从事Python微服务开发的技术人员提供有价值的参考和指导。 ... [详细]
  • Windows 7 忘记登录密码?详细教程教你如何安全重置密码 ... [详细]
  • 本文详细探讨了Java事件处理机制的核心概念与实现原理,内容浅显易懂,适合初学者逐步掌握。通过具体的示例和详细的解释,读者可以深入了解Java事件模型的工作方式及其在实际开发中的应用。 ... [详细]
  • 当 EXCLUDE_DEAD 设置为 1 时,为何没有容器被移除? ... [详细]
  • 深入理解 Java 控制结构的全面指南 ... [详细]
  • 2012年9月12日优酷土豆校园招聘笔试题目解析与备考指南
    2012年9月12日,优酷土豆校园招聘笔试题目解析与备考指南。在选择题部分,有一道题目涉及中国人的血型分布情况,具体为A型30%、B型20%、O型40%、AB型10%。若需确保在随机选取的样本中,至少有一人为B型血的概率不低于90%,则需要选取的最少人数是多少?该问题不仅考察了概率统计的基本知识,还要求考生具备一定的逻辑推理能力。 ... [详细]
  • 本文详细介绍了如何在Java Web服务器上部署音视频服务,并提供了完整的验证流程。以AnyChat为例,这是一款跨平台的音视频解决方案,广泛应用于需要实时音视频交互的项目中。通过具体的部署步骤和测试方法,确保了音视频服务的稳定性和可靠性。 ... [详细]
  • Spring框架的核心组件与架构解析 ... [详细]
  • 本文对常见的字符串哈希函数进行了全面分析,涵盖了BKDRHash、APHash、DJBHash、JSHash、RSHash、SDBMHash、PJWHash和ELFHash等多种算法。这些哈希函数在不同的应用场景中表现出各异的性能特点,通过对比其算法原理、计算效率和碰撞概率,为实际应用提供了有价值的参考。 ... [详细]
  • (1)前期知识:1. 单机架构:单一服务器计算机——其处理能力和存储容量有限。2. 集群架构(负载均衡器与多节点服务器)——通过增加节点数量来提升系统性能和可靠性,实现高效的任务分配和资源利用。 ... [详细]
  • 如何使用CSS3创建圆角边框效果? ... [详细]
author-avatar
海蓝透了我的心
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有