数组下标寻址算法 - Lihaoya 的博客

数组下标寻址算法

发布于: 2021-07-14

主流编程语言的数组下标都是从 0 开始的，数组是如何进行寻址的呢？本文主要介绍寻址算法的一种思想，相关扩展信息附在文末。

从 0 开始或从 1 开始

在计算机科学中，数组数据结构 （英语：array data structure），简称数组（英语：Array），是由相同类型的元素（element）的集合所组成的数据结构，分配一块连续的内存来存储。利用元素的索引（index）可以计算出该元素对应的存储地址。

数组是一种被使用非常频繁的数据结构，比如 Java 中的 ArrayList 正是利用数组实现的 List 接口。

数组也由于其内存连续的特性，可以通过算法直接计算出索引对应元素在内存中的位置。访问内存中的某个地址是极快的，数组在随机查找上有着极好的性能（此处查找性能指的是数组下标，并不是数组内元素。优化数组中元素随机查找性能可以参考 Java 中的 HashMap 等实现）

假设有一一维数组 int 为 32 位 4 个字节大小：

int[] array = [0, 0, 0, 0, 0]

若第一地址或基础地址为 2000 则数组内元素起始位置分别为 2000 2004 2008 2012 2016

下面我们写一下寻址算法👇🏻

address = 2000 + (x - 1) * 4

查找下标 1的第一地址

address = 2000 + (1 - 1) * 4 // 2000

查找下标 2的第一地址

address = 2000 + (2 - 1) * 4 // 2004

查找下标 5的第一地址

address = 2000 + (5 - 1) * 4 // 20016

如果下标由 1 开始，每次都要将下标减 1 才可以计算对应的第一地址。

依旧按照上方 array示例，数组元素下标由 0 开始，我们写一下寻址算法👇🏻

address = 2000 + x * 4

查找下标 0的第一地址

address = 2000 + 0 * 4 // 2000

由于下标从 0 开始，则最后一个元素下标为 4

address = 2000 + 4 * 4 // 2016

下标为 0 算法更加简单，并减少了一次计算。