【深度揭秘】为什么很多语言的数组下标是从0开始的？

作者丨手艺人

来源丨IT烂笔头

数组的随机访问

尽管大家都知道了什么是数组，但是还是用官方的术语描述一下：数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。

我们可以抓住里面的几个重点词汇，来充分理解数组这种结构。 

1、线性表，就是数据的排列从前到后顺序排列，就像一条线，像队列、栈列表、数组等都是线性表结构。 

当然有线性表结构就有非线性表结构：

2、连续内存空间和相同的数据类型。为啥数据访问一个数据效率非常高？那是因为数组的定义将数组这种结构定好了规矩，线性连续给了我们快速随机访问的机会。但是同时也带来了不好的地方，如果我们向其中插入或者删除一条数据是比较费劲的。 

来看看数组是怎么实现随机访问的？ 

假设有这么一个数组：
java int[] a = new int[10]; 
操作系统给分配了一块连续的内存空间，假设为1000~1039，那么内存的首地址就是base_add = 1000

如果你去走访亲戚，你需要知道的是什么？亲戚家的地址吧（具体到门牌号），内存也一样，我们想读取内存里面的数据，操作系统也是通过内存的地址来访问的，那么问题来了，内存的地址是怎么知道呢？ 

这就涉及到操作系统的寻址，比如我想获取a[2]的值，那么操作系统先会根据下面的公式计算对应内存的地址：

 a[2]的地址 = base_add + 2 * data_unit_size 

dataunitsize表示该数据类型每个元素的大小，当前是int类型为4个字节，所以算出来a[2]的地址就是1008 

那是不是可以说数组的查找的时间复杂度就是O(1)？当然不是了，正常情况下我们查找数可不是通过下标来查找的，我们是通过值来查找的，即便是二分查找时间复杂度也是O(logn)。 

删除和插入怎么就低效了

1、插入操作
假设我们要在长度为n的数组的第k个位置插入一个数据，我们就要讲第k~n的数往后挪，同理如果在最后插入就不需要挪位置，如果在第一个位置插入就要挪n个数，所以平均时间复杂度就是：（1+2+3+...+n)/n=O(n)

当然，如果不要求插入后顺序还保持原来一样，有个讨巧的插入方法就是讲第K个元素放到最后，将待插入的数放到第K个位置。 

举个例子，假设数组 a[10]中存储了如下 5 个元素：a，b，c，d，e。 

我们现在需要将元素 x 插入到第 3 个位置。我们只需要将 c 放入到 a[5]，将 a[2]赋值为 x 即可。最后，数组中的元素如下：a，b，x，d，e，c。

2、删除操作. 

其实和插入操作是相似的，当我们对长度为n的数组的第K个数组进行删除时，需要对后面的数据进行向前搬移操作，同理，时间复杂度和插入一样也是O(n)，这里就不详细介绍了。

当然，在不考虑维持连续性的特殊情况下，为了提高删除的效率，没必要每次删除立即进行搬移操作，不然如果连续删除数据，就要连续进行多次的搬移。比较讨巧的办法是将待删除的元素进行标记，实际未做删除，等等内存不足的时候，将这些标记的数据统一进行删除操作。这样就会大大减少删除操作带来的大量数据搬移操作。 

灾难！数组越界啦

对于Java来说发生数据越界的时候会抛出异常，但是对于有些语言比如C语言发生数组越界的时候并不会给你异常提示，比如下面这段代码： 

int i = 0; int arr[3] = {0};for(;i<=3;i++) {  arr[i] = 0;  System.out.println("test");  }

显然定义的是长度为3的数组，但是循环条件是<=，所以会访问到数组外面的内存，而a[3]的地址刚好是存储i的内存，所以当循环到a[3]时又赋值为0，相当于i=0;所以这个循环永远结束不了，“hello world”会一直打印。 

所以，对于C语言来说，如果没控制好下标，发生数组越界会出现莫名其妙的逻辑问题，还很难调试。这也是很多病毒利用数组越界来非法访问内存来攻击系统。 

各种容器满天飞，还需要数组？

对于Java开发者来说，ArrayList再熟悉不过了，它为我们封装好了各种API来操作，比使用数组方便的多，而且是支持动态扩容的，因为数组是要提前订好大小的，当大小不满足的时候，需要重新定义大的数组进行复制操作，这显然很不方便，而容器类是内部有动态的分配的机制，当大小不够的时候自动的扩容，当然这也是非常耗性能的。如果能确定数据的大小，提前指定容器的大小更好。 

那是不是意味着数组没有存在的必要，那也不是的，比如在下面的情况： 

• ArrayList是不能存储基本数据类型的，需要使用他们对应的装箱类，而拆箱和装箱显然都是非常耗性能的，如果特别关注性能，又需要使用基本数据类型，使用数组比使用ArrayList性能更好

• 定义多维数组时，使用数组更加的直观
  

• 如果数据大小事先知道，而对数据的操作比较简单。用不到ArrayList的大多API，这时候可以优先使用数组

小结：对于上层业务开发者，由于业务变化大，操作数据变化频繁，使用容器更加方便，牺牲一点性能对系统的整体功能影响不大。但是如果是做比较偏底层的开发就需要关注性能了，性能一丁点的提升，影响也是很广泛的，所以选择数组比较合适。

回到主题

为什么数组从0开始呢？
从数组存储的内存模型来看，下标比较确切的定义是“偏移”，如果用a来表示数组的首地址，那么a[0]就表示偏移为0的位置。a[x]就表示偏移x个类型大小（int 4个字节）的的位置。java a[x]_address = base_address + x * data_type_size;

但是如果从1开始计数呢，那么寻址公式就变成：
java a[x]_address = base_address + (x-1) * data_type_size;  
显然要多运算减一的操作，对于数组数据结构的定义是偏基础库的，对于性能要求当然是要追求极致的，多一步和少一步运算都是非常重要的参考点，所以为了更好的性能选择从0开始而不是从1开始。 

当然也有历史因素，因为最早的C语言设计者使用从0开始的，所以后面的语言都延续了这一做法，这样能减少程序员学习语言的成本。当然也有一些不是从0开始的语言，这里就不举例了，感兴趣的同学可以自行去搜索一下。 

总结

数组这种数据结构对于随机访问的效率特别高，但是对于插入和删除的效率就比较低了，对于业务开发者来说使用容器类比较省时实力，而对于偏底层开发者来说选择性能更好的数组就更合适了。 

-End-

最近有一些小伙伴，让我帮忙找一些 面试题 资料，于是我翻遍了收藏的 5T 资料后，汇总整理出来，可以说是程序员面试必备！所有资料都整理到网盘了，欢迎下载！