数组下标寻址算法
算法
发布于: 2021-07-14

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

从 0 开始或从 1 开始

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

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

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

寻址从 1 开始

假设有一一维数组 int32 位 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 才可以计算对应的第一地址。

寻址由 0 开始

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

address = 2000 + x * 4

查找下标 0的第一地址

address = 2000 + 0 * 4 // 2000

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

address = 2000 + 4 * 4 // 2016

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

下标由 1 开始的编程语言

  • Lua

  • pascal

相关链接

Developer On Line: Why The Array Index Should Start From 0

Citation Needed << blarg? (tive.org)

C/C++ 数组的下标为何要从 0 开始,而不从 1 开始? - 知乎 (zhihu.com)

Lua 的 table 索引默认从 1 开始,这样做有什么好处? - 知乎 (zhihu.com)