数组(顺序存储)基本原理

简介: 本章讲解数组的底层原理,区分静态与动态数组。通过静态数组实现动态数组的增删查改,揭示随机访问O(1)的成因与连续内存的利弊,助你理解数据结构本质。

数组(顺序存储)基本原理
我们在说「数组」的时候有多种不同的语境,因为不同的编程语言提供的数组类型和 API 是不一样的,所以开头先统一一下说辞,方便后面的讲解。
我认为暂且可以把「数组」分为两大类,一类是「静态数组」,一类是「动态数组」。
「静态数组」就是一块连续的内存空间,我们可以通过索引来访问这块内存空间中的元素,这才是数组的原始形态。
而「动态数组」是编程语言为了方便我们使用,在静态数组的基础上帮我们添加了一些常用的 API,比如 push, insert, remove 等等方法,这些 API 可以让我们更方便地操作数组元素,不用自己去写代码实现这些操作。
本章的内容就是带大家仅仅使用最原始的静态数组,自己实现一个动态数组,实现增删查改的常见 API。以后你在使用标准库提供的数据结构时,就知道它们的底层运行原理了。
有了动态数组,后面讲到的队列、栈、哈希表等复杂数据结构都会依赖它进行实现。
静态数组
静态数组在创建的时候就要确定数组的元素类型和元素数量。只有在 C++、Java、Golang 这类语言中才提供了创建静态数组的方式,类似 Python、JavaScript 这类语言并没有提供静态数组的定义方式。
静态数组的用法比较原始,实际软件开发中很少用到,写算法题也没必要用,我们一般直接用动态数组。但为了理解原理,在这里还是要讲解一下。
定义一个静态数组的方法如下:
就这,没有其他什么操作了。
拿 C++ 来举例吧,int arr[10] 这段代码到底做了什么事情呢?主要有这么几件事:
1、在内存中开辟了一段连续的内存空间,大小是 10 sizeof(int) 字节。一个 int 在计算机内存中占 4 字节,也就是总共 40 字节。
2、定义了一个名为 arr 的数组指针,指向这段内存空间的首地址。
那么 arr[1] = 2 这段代码又做了什么事情呢?主要有这么几件事:
1、计算 arr 的首地址加上 1
sizeof(int) 字节(4 字节)的偏移量,找到了内存空间中的第二个元素的首地址。
2、从这个地址开始的 4 个字节的内存空间中写入了整数 2
😸写给初学者
我记得以前刚上大学的时候要学 C 语言基础,有些同学就绕不清楚什么指针的数组,数组的指针,绕来绕去的。其实只要明白了上面这个简单的流程,一切就很清楚了。
1、为什么数组的索引从 0 开始?就是方便取地址。arr[0] 就是 arr 的首地址,从这个地址往后的 4 个字节存储着第一个元素的值;arr[1] 就是 arr 的首地址加上 1 4 字节,也就是第二个元素的首地址,这个地址往后的 4 个字节存储着第二个元素的值。arr[2], arr[3] 以此类推。
2、因为数组的名字 arr 就指向整块内存的首地址,所以数组名 arr 就是一个指针。你直接取这个地址的值,就是第一个元素的值。也就是说,
arr 的值就是 arr[0],即第一个元素的值。
3、如果不用 memset 这种函数初始化数组的值,那么数组内的值是不确定的。因为 int arr[10] 这个语句只是请操作系统在内存中开辟了一块连续的内存空间,你也不知道这块空间是谁使用过的二手内存,你也不知道里面存了什么奇奇怪怪的东西。所以一般我们会用 memset 函数把这块内存空间的值初始化一下再使用。
当然,上面讲的这些内容都是针对 C/C++,因为大家学习计算机基础的时候都接触过。其他比如 Java Golang 这种语言,静态数组创建出来后会自动帮你把元素值都初始化为 0,所以不需要再显式进行初始化。
😀总结
我梳理一下上面的因果逻辑,静态数组本质上就是一块连续的内存空间,int arr[10] 这个语句我们可以得知:
1、我们知道这块内存空间的首地址(数组名 arr 就指向这块内存空间的首地址)。
2、我们知道了每个元素的类型(比如 int),也就是知道了每个元素占用的内存空间大小(比如一个 int 占 4 字节,32 bit)。
3、这块内存空间是连续的,其大小为 10 * sizeof(int) 即 40 字节。
所以,我们获得了数组的超能力「随机访问」:只要给定任何一个数组索引,我可以在 O(1)O(1) 的时间内直接获取到对应元素的值。
因为我可以通过首地址和索引直接计算出目标元素的内存地址。计算机的内存寻址时间可以认为是 O(1)O(1),所以数组的随机访问时间复杂度是 O(1)O(1)。
但是,一个人最大的优势往往也是他的最大劣势。数组连续内存的特性给了他随机访问的超能力,但它也因此吃了不少苦,下面介绍。
增删改查

相关文章
|
机器学习/深度学习 数据采集 算法
解码癌症预测的密码:可解释性机器学习算法SHAP揭示XGBoost模型的预测机制
解码癌症预测的密码:可解释性机器学习算法SHAP揭示XGBoost模型的预测机制
1922 0
|
7月前
|
缓存 Java 测试技术
Maven 依赖下载失败的 10 种解决方案:排查指南
本文深入总结了 Maven 依赖下载失败的 10 种常见场景及解决方案,包含 .lastUpdated 文件清理、镜像源切换、网络超时调整、SSL 证书问题、仓库权限配置等企业级实战经验。提供完整的排查流程图和一键修复脚本,帮助你快速定位并解决依赖下载问题。掌握这些技能,你将能够应对 99% 的依赖下载故障。适合 Java 开发者、DevOps 工程师阅读。
Maven 依赖下载失败的 10 种解决方案:排查指南
|
9月前
|
安全 Java 数据挖掘
高效转换Word表格为Excel:Python方案全解析
本文介绍如何用Python自动化将Word表格转为Excel,解决手动复制易出错、耗时长等问题。基于python-docx读取表格,结合openpyxl或pandas写入,支持多表合并、数字格式识别、合并单元格处理及大文件优化,30行代码即可实现高效精准转换。(239字)
1032 13
|
11月前
|
存储 Serverless
哈希冲突
哈希冲突可通过优化哈希函数或采用冲突解决策略应对。开放寻址法通过线性、二次探查或双散列寻找空位,但易导致聚集,影响效率;链表法则在冲突位置构建链表,避免抢占,更适应动态数据,是常用方案之一。
|
SQL 关系型数据库 MySQL
阿里云RDS云数据库全解析:产品功能、收费标准与活动参考
与云服务器ECS一样,关系型数据库RDS也是很多用户上云必买的热门云产品之一,阿里云的云数据库RDS主要包含RDS MySQL、RDS SQL Server、RDS PostgreSQL、RDS MariaDB等几个关系型数据库,并且提供了容灾、备份、恢复、监控、迁移等方面的全套解决方案,帮助您解决数据库运维的烦恼。本文为大家介绍阿里云的云数据库 RDS主要产品及计费方式、收费标准以及活动等相关情况,以供参考。
|
8月前
|
传感器 人工智能 API
章鱼不会把触角外包:为什么通用 Agent 的终局只属于模型厂商
本文以“章鱼触角”为喻,指出通用Agent终局属于模型厂商:真正强大的Agent不是外挂工具链,而是模型原生具备环境感知、工具调用、任务执行与自我修正的闭环能力。能力内化才能避免转译损耗,训练闭环、架构协同、系统效率与入口控制构成厂商不可替代的护城河。应用层机会在于垂直深耕,而非重复封装。(239字)
487 6
|
11月前
|
存储 弹性计算 人工智能
大模型应用开发
大模型应用开发指通过API与大模型交互,构建智能化应用。不同于传统Java开发,其核心在于调用部署在云端或本地的大模型服务。企业可选择开放API、云平台或本地服务器部署,各具成本、安全与性能权衡。本章将详解部署方式与开发实践,助你快速入门。
|
11月前
|
存储 算法 安全
加密算法
加密算法主要分为对称加密(如AES、SM4)、非对称加密(如RSA、SM2)、哈希摘要(如SHA-2、SM3)、电子签名及密码存储技术。对称加密加解密快但需保密密钥;非对称加密使用公私钥,安全性高但速度慢;哈希摘要用于验证数据完整性,不可逆。各类算法在信息安全中各有应用场景。
|
11月前
|
存储 NoSQL 关系型数据库
Geohash 编码
Geohash编码将经纬度转换为字符串,通过不断二分地球经纬度区间,交叉组合生成区域编码,再转为Base32简化表示。它用于高效存储和查询地理位置,广泛应用于Redis、MySQL等系统,具有相同前缀的编码代表相近区域,便于空间索引与检索。
|
11月前
|
NoSQL Java 数据库连接
SpringBoot框架
SpringBoot简化Spring开发,核心功能包括starter起步依赖、自动配置及内嵌服务器支持。通过@SpringBootApplication实现自动化配置,支持多种配置方式,优先级为:命令行参数 > 系统属性 > properties > yml/yaml。可自定义starter实现模块化集成。