arrays - 随机存取存储器如何工作？为什么是恒定时间随机访问？

Question

或者换句话说，为什么访问数组中的任意元素需要恒定的时间(而不是 O(n) 或其他时间)？

我用谷歌搜索了我的心，寻找这个问题的答案，但没有找到一个很好的答案，所以我希望你们中的一个人可以与我分享你的低级知识。

只是为了让您了解我希望得到的答案有多低，我会告诉您为什么我认为这需要持续的时间。

当我说 array[4] = 12在程序中，我实际上只是将内存地址的位表示存储到寄存器中。硬件中的这个物理寄存器会根据我输入的位表示打开相应的电信号。然后这些电信号会以某种方式神奇地(希望有人能解释这个魔法)访问物理/主内存中的正确内存地址。

我知道这很粗糙，但这只是为了让您了解我正在寻找什么样的答案。

(编者注:从 OP 稍后的评论中，他了解到地址计算需要恒定的时间，只是想知道之后会发生什么。)

Answer 1

因为软件喜欢 O(1) “工作”内存，因此硬件被设计为以这种方式运行

基本点是程序的地址空间被抽象地认为具有 O(1) 访问性能，即无论您想读取任何内存位置，它都应该花费一些恒定的时间(无论如何这与它之间的距离无关和最后一次内存访问)。因此，作为数组只不过是连续的地址空间块，它们应该继承这个属性(访问数组的元素只是将索引添加到数组的起始地址，然后取消引用获得的指针)。

这个属性来自于这样一个事实，一般来说，程序的地址空间与 PC 的物理 RAM 有一些对应关系，正如名称(随机存取存储器)部分暗示的那样，它本身应该具有这样的属性，无论您想要访问的 RAM 中的位置，您可以在恒定时间内到达它(例如，与磁带驱动器相反，其中查找时间取决于您必须移动到那里的实际磁带长度)。

现在，对于“常规” RAM，此属性(至少 AFAIK)为真-当处理器/主板/内存 Controller 要求 RAM 芯片获取一些数据时，它会在恒定时间内这样做；细节与软件开发并不真正相关，并且存储芯片的内部结构在过去多次更改，并且将来会再次更改。如果您对当前 RAM 的详细信息的概述感兴趣，可以查看 here关于 DRAM。

一般概念是 RAM 芯片不包含必须移动的磁带或必须定位的磁盘臂；当您在某个位置向他们询问一个字节时，工作(主要是更改某些硬件多路复用器的设置，将输出连接到存储字节状态的单元)对于您可能要求的任何位置都是相同的；因此，您将获得 O(1) 性能

这背后有一些开销(逻辑地址必须由 MMU 映射到物理地址，各个主板部件必须相互通信以告​​诉 RAM 获取数据并将其带回处理器，...... )，但硬件被设计为在或多或少恒定的时间内这样做。

所以:

数组映射到地址空间，该地址空间映射到 RAM，具有 O(1) 随机访问；作为所有映射(或多或少)O(1)，数组保持了 RAM 的 O(1) 随机访问性能。

相反，对软件开发人员来说很重要的一点是，尽管我们看到一个平面地址空间并且它通常映射在 RAM 上，但在现代机器上，访问任何元素具有相同的成本是错误的。事实上，访问同一区域中的元素比在地址空间中跳转要便宜得多，因为处理器有几个板载缓存(=更小但更快的片上存储器)，用于保存最近使用的数据和内存那是在同一个街区；因此，如果您具有良好的数据局部性，内存中的连续操作将不会继续访问 ram(其延迟比缓存长得多)，并且最终您的代码将运行得更快。

此外，在内存压力下，提供虚拟内存的操作系统可以决定将地址空间中很少使用的页面移动到磁盘，并在访问它们时按需获取它们(响应页面错误)；这样的操作非常昂贵，并且再次强烈偏离访问任何虚拟内存地址都是相同的想法。