探索Java集合框架—数据结构、ArrayList集合

一、背景介绍

Java集合的使用相信大家都已经非常得心应手,但是我们怎么做到知其然,更知其所以然这种出神入化的境界呢?我们揭开集合框架底层神秘面纱来一探究竟

目录

一、背景介绍

二、思路&方案

数据结构是什么?

数据结构可以分为线性和非线性两种数据结构

线性数据结构:

非线性数据结构:

Java集合分类

Collection接口:

Map接口:

三、过程

ArrayList和LinkedList的区别有哪些?

ArrayList是如何存储数据的?

ArrayList扩容机制

①、如何进行扩容的?

②、增加元素

③、ArrayList给指定位置插入元素

④、删除元素

按照下标位置删除元素

按照内容删除元素

四、总结


二、思路&方案

在说集合之前我们要先了解数据结构这一概念

数据结构是什么?

数据结构时对数据进行组织和存储一种方式,数据使用不同的数据结构组织和存储时所带来的时间和空间性能也是不同的。List、Set、Map集合背后使用了不同的数据结构,我们理解为集合是一种数据结构的具体实现。例如:可以使用数组结构来实现集合,当访问数组元素的时候通过数组下标查找时更快。

程序=数据结构+算法。数据结构还提供了一些各种查找、排序算法,集合可以用来解决一堆数据的处理问题,如:查找、排序、去重等等

数据结构可以分为线性和非线性两种数据结构

线性数据结构:

特点:

一对一的关系并且逻辑上有序,数据元素之间存在一个前后关系,每个元素只有一个直接前驱和一个直接后去

组成:

  • 数组(Array):相同类型元素并且连续存储
  • 链表(LinkedList):一系列node节点,每个节点包括数据、指向下一个节点的指针
  • 栈(Stack):先进后出(LIFO),在栈顶进行删除和插入操作
  • 队列(Queue):先进先出(FIFO),在队尾插入、对头删除元素

非线性数据结构:

特点:

多对多关系,数据元素之间不存在直接的前后关系,元素和元素之间通过指针相连,

包括:

  • 树(Tree):一组node节点组成,每个父节点下级可以有子节点,节点之间是上下层次关系
  • 图(Graph):一组节点、边之间的关系
  • 堆(Heap):实现优先队列
  • 散列表(Hash Table):根据关键字可以直接查询数据,通过散列函数确认存储位置

结合上面讲到的数据结构,我们来看下Java究竟是如何应用的


Java集合分类

集合相关类和接口都在java.util中,从宏观上我们把Java集合分为了以Collection为中心的实现类、以Map为中心的实现类, Collection和Map两个接口下面分别有不同的实现类,它们都是用来存储和操作数据的集合

Collection接口:

特点:

一组对象的集合,通过索引或迭代器访问元素,元素可以重复

包括:

  • List:有序集合
  • Set:无序集合
  • Queue:先进先出集合

Map接口:

特点:

键值对映射的集合,通过key查找value,每个key是唯一的

包括:

  • HashMap:通过哈希表实现,无序
  • TreeMap:基于红黑树实现,有序
  • LinkedHashMap:哈希表+双向链表实现,顺序插入

今天先重点来讲讲List集合中ArrayList增删改查是如何实现的



三、过程

ArrayList和LinkedList的区别有哪些?

ArrayList是如何存储数据的?

底层是数组,数组存储的数据的特点是元素类型相同并且数组容量固定

数组存储容量固定?那在实际业务场景中数据肯定是不固定的呀?如何解决?

ArrayList扩容机制

ArrayList提供了自动扩容机制,当插入数据时候底层会先判断是否需要扩容,如果当前容量+1超过数组长度,就会进行扩容,反之。

①、如何进行扩容的?

ArrayList内部封装了一个动态再分配的对象数组,ArrayList的底层数据库初始容量为10,扩容因子为1.5

 

②、增加元素

当我们第一次添加元素使用add()方法添加元素的过程中,底层的流程是这样的:

内部会调用ensureExplicitCapacity()方法判断添加元素之后的数组长度是否大于数组容量,如果超出数组容量调用grow()方法扩容,否则给数组长度+1

当第一次对数组进行add添加元素的时候,才会把内部的数组扩容为10,这也是数组的第一次扩容

 注意:

  • 数组长度是指当前数组内元素的个数
  • 数组容量是指数组所能容纳的长度

示意图:

那如果要添加的元素不足数组容量呢?现在我们来看下具体是如何扩容的?

假设场景:数组中已经有10个元素,需要添加第11个元素

calculateCapacity方法内部首先会判断elementData数组是否是默认的空数组(看是否往数组里面添加了元素),如果不是默认数组则返回添加元素之后数组所需要的长度

如果添加元素之后的数组长度超出了数组容量,则说明需要扩容,调用grow()方法进行扩容

 grow()方法内部会调用一个交copyOf方法进行扩容,会创建一个1.5倍的新数组,将原来的数组元素挪到新数组中

此时ArrayList扩容为原来的大小+原来大小/2=10+5=15,数组扩容后容量为15

 扩容后的数组示意图如下:

add(E e)添加元素的流程为:

第一步、判断是否需要扩容:

        需要扩容

                ①、计算新数组容量:newCapacity = oldCapacity + (oldCapacity >> 1)

                ②、创建新数组:elementData = Arrays.copyOf(elementData, newCapacity)

第二步、追加元素到数组末尾 。  elementData[size++] =element;

第三步、添加成功

③、ArrayList给指定位置插入元素

示例:

添加指定位置流程如下:

第一步、检查下标是否越界

        越界:抛出IndexOutOfBoundsException异常

第二步、判断是否需要扩容,如果需要扩容则扩容

第三步、后移元素.从指定要插入元素位置依次向后移动一个位置,此时指定要插入的位置为空

第四步、插入新元素。将要插入的元素放入指定位置

第五步、更新数组大小。size+1

        

注意: 其中rangeCheckForAdd(index)方法会检查下标是否越界,如果要插入的元素位置超出了当前数组的容量,会抛出”IndexOutOfBoundsException“的异常

 示意图:

④、删除元素

按照下标位置删除元素

按照内容删除元素


四、总结

通过分析源码我们了解了ArrayList底层增删改查操作具体的细节,再次总结

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/113485.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

linux————ELK(日志收集系统集群)

目录 一、为什么要使用ELK 二、ELK作用 二、组件 一、elasticsearch 特点 二、logstash 工作过程 INPUT(输入) FILETER(过滤) OUTPUTS(输出) 三、kibana 三、架构类型 ELK ELKK ELFK ELFKK EFK 四、构建ELk集群…

Apache的简单介绍(LAMP架构+搭建Discuz论坛)

文章目录 1.Apache概述1.1什么是apache1.2 apache的功能及特性1.2.1功能1.2.2特性 1.3 MPM 工作模式1.3.1 prefork模式1.3.2 worker模式1.3.3 event模式 2.LAMP概述2.1 LAMP的组成2.2 LAMP各组件的主要作用2.3 LAMP的工作过程2.4CGI和FastCGI 3.搭建Discuz论坛所需4.编译安装Ap…

Mysql中explain执行计划信息中字段详解

Mysql中explain执行计划信息中字段详解 1. 获取执行计划2. 字段含义2.1 id2.2 select_type2.3 table2.4 partitions2.5 type2.6 possible_keys2.7 key2.8 ley_len2.9 ref2.10 rows2.11 extra 1. 获取执行计划 explain select * from t5; --或 desc select * from t5;2. 字段含…

滑动窗口实例1(长度最小的子数组)

题目: 给定一个含有 n 个正整数的数组和一个正整数 target 。 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl1, ..., numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。 示例 1: …

zookeeper 3.8.1安装和入门使用

1、zookeeper环境搭建(Windows单机版) 1.1、 前提 必须安装jdk 1.8,配置jdk环境变量,步骤略 1.2、安装zookeeper 地址:https://zookeeper.apache.org/ 1.2.1、选择releases版本 1.2.2、下载安装包并解压 1.2.3、配…

前端文件、图片直传OOS、分片上传、el-upload上传(vue+elementUI)

前言:基于天翼云的面相对象存储(Object-Oriented Storage,OOS),实现小文件的直接上传,大文件的分片上传。 开发文档地址:网址 上传之前的相关操作:注册账户,创建 AccessKeyId 和 AccessSecretKey之后&…

企业怎么优化固定资产管理

在优化固定资产管理的过程中,不仅要关注硬件设备和设施的维护,还要重视软件系统和数据管理。一些可能的方法:  需要建立一套完整的资产管理系统。这个系统应该包括资产的采购、登记、使用、维修、报废等各个环节的管理流程。通过这个系统&a…

智慧工地源码带开发手册文档 app 数据大屏、硬件对接、萤石云

智慧工地解决方案依托计算机技术、物联网、云计算、大数据、人工智能、VR、AR等技术相结合,为工程项目管理提供先进技术手段,构建工地现场智能监控和控制体系,弥补传统方法在监管中的缺陷,最终实现项目对人、机、料、法、环的全方…

Windows安装FFmpeg说明

下载地址 官网 Download FFmpeg Csdn ffmpeg安装包,ffmpeg-2023-08-28-git-b5273c619d-full-build.7z资源-CSDN文库 解压安装,添加环境变量 命令行输入ffmpeg 安装成功

【mysql】MySQL服务无法启动 NET HELPMSG 3534

MySQL服务无法启动 NET HELPMSG 3534 错误描述寻找原因解决方法 错误描述 mysql版本:8.1.0 mysql安装成功之后,使用net start mysql来启动mysql,然后出现了报错 MySQL服务无法启动 NET HELPMSG 3534 寻找原因 1、在cmd中,进入…

React 如何获取上一次 state 的值

React 如何获取上一次 state 的值 一、用 ref 存储上一次的 state 类似 usePrevious function usePrevious(value) {const ref useRef();useEffect(() > {ref.current value;});return ref.current; }二、通过 setState 的入参改为函数获取

electron win系统通知修改通知标题栏

标题栏的 electron.app.Electron 如何修改: var package require("../package.json"); app.setAppUserModelId(package.description); app.setAppUserModelId 在主进程的app这里修改

Flutter 混合开发调试

针对Flutter开发的同学来说,大部分的应用还是Native Flutter的混合开发,所以每次改完Flutter代码,运行整个项目无疑是很费时间的。所以Flutter官方也给我们提供了混合调试的方案【在混合开发模式下进行调试】,这里以Android Stud…

【openEuler创新项目探索】一个Java端的向量化BLAS库VectorBLAS

VectorBLAS简介 VectorBLAS是一个使用Java语言实现的向量化BLAS高性能库,目前已在openEuler社区开源。 VectorBLAS通过循环展开、矩阵分块和内存布局优化等算法优化,对BLAS函数进行了深度优化,并利用VectorAPI JDK提供的多种向量化API实现。…

Baklib是比语雀、Notion、石墨文档更好用的在线知识库管理工具

在当今信息爆炸的时代,如何高效地管理和利用知识成为了每个人都面临的问题。在线知识库管理工具应运而生,帮助用户整理、存储和共享知识。在这篇文章中,我将介绍一个更好用的在线知识库管理工具——Baklib,并探讨它相对于其他知识…

PMAC与Modbus主站进行Modbus Tcp通讯

PMAC与Modbus主站进行Modbus Tcp通讯 创建modbus通讯参数 在项目的PMAC Script Language\Global Includes下创建一个名为00_Modbus_Para.pmh的pmh文件。 Modbus[0].Config.ServerPort 0 Modbus[0].Config.ConnectTimeOut 6000 Modbus[0].Config.SendRecvTimeOut 0 Modbu…

利用Jmeter做接口测试(功能测试)全流程分析

利用Jmeter做接口测试怎么做呢?过程真的是超级简单。 明白了原理以后,把零碎的知识点填充进去就可以了。所以在学习的过程中,不管学什么,我一直都强调的是要循序渐进,和明白原理和逻辑。这篇文章就来介绍一下如何利用…

【机器学习7】特征缩放

特征缩放 🍀特征缩放的重要性🌱归一化🌱标准化🌱更高级的缩放方法🌸导入数据集&将数据集划分为训练集和测试集🌸Sklearn-Learn算法实现归一化🌸Sklearn-Learn算法实现标准化 🍀特…

Google登录SDK

一、接入的准备工作 官方文档链接地址:开始使用一键登录和注册 按照步骤进行接入即可 二、项目参考(Unity项目) 注意:代码版本如果不适用新的Google API 请自行参考最新版本接口 SDKGoogleSignInActivity 主要用于登录的代码。Un…