或者换句话说，为什么访问数组中的任意元素需要恒定的时间（而不是O(n)其他时间）？
我用谷歌搜索了这个问题的答案，但没有找到一个很好的答案，所以我希望你们中的一个可以与我分享你的低级知识。
只是为了让您了解我希望得到的答案有多低，我会告诉您为什么我认为这需要恒定的时间。
当我说array[4] = 12在程序中时，我实际上只是将内存地址的位表示存储到寄存器中。硬件中的这个物理寄存器将根据我输入的位表示打开相应的电信号。然后，这些电信号将以某种神奇的方式（希望有人能解释其中的魔力）访问物理/主存储器中的正确内存地址。
我知道这很粗略，但这只是为了让您了解我正在寻找什么样的答案。
（编者注：从 OP 后来的评论中，他了解到地址计算需要恒定的时间，并且只是想知道之后会发生什么。）
基本点是程序的地址空间被认为是抽象地具有 O(1) 访问性能，即无论您想读取什么内存位置，它都应该花费一些恒定的时间（无论如何这与它之间的距离无关）和最后一次内存访问）。因此，作为数组只不过是地址空间的连续块，它们应该继承此属性（访问数组的元素只需将索引添加到数组的起始地址，然后取消引用获得的指针）。
这个属性来自这样一个事实，一般来说，程序的地址空间与 PC 的物理 RAM 有一些对应关系，正如名称（随机存取存储器）部分暗示的那样，它本身应该具有这样的属性，无论在您想要访问的 RAM 中的位置，您可以在恒定时间内到达它（例如，相对于磁带驱动器，寻道时间取决于您必须移动到那里的磁带的实际长度）。
现在，对于“常规”RAM，此属性（至少 AFAIK）是正确的 - 当处理器/主板/内存控制器要求 RAM 芯片获取一些数据时，它会在恒定时间内这样做；细节与软件开发无关，内存芯片的内部结构过去曾多次更改，将来还会再次更改。如果您对当前 RAM 的详细信息的概述感兴趣，可以在此处查看有关 DRAM 的信息。
一般概念是 RAM 芯片不包含必须移动的磁带或必须定位的磁盘臂；当您在某个位置向他们询问一个字节时，对于您可能要求的任何位置，工作（主要是更改某些硬件多路复用器的设置，将输出连接到存储字节状态的单元）都是相同的；因此，您将获得 O(1) 的性能
这背后有一些开销（逻辑地址必须由 MMU 映射到物理地址，各个主板部件必须相互通信以告诉 RAM 获取数据并将其带回处理器，...... )，但硬件设计为在或多或少恒定的时间内这样做。
所以：
数组映射到地址空间，该地址空间映射到 RAM，具有 O(1) 随机访问；作为所有映射（或多或少）O(1)，数组保持 RAM 的 O(1) 随机访问性能。
相反，对软件开发人员来说重要的一点是，尽管我们看到一个平坦的地址空间并且它通常映射到 RAM 上，但在现代机器上，访问任何元素具有相同的成本是错误的。事实上，访问同一区域中的元素可能比在地址空间中跳转便宜得多，因为处理器有几个板载缓存（=更小但更快的片上内存）来保存最近使用的数据和内存那是在同一个街区；因此，如果您具有良好的数据局部性，内存中的连续操作将不会一直撞击 ram（其延迟比缓存长得多），最终您的代码将运行得更快。
此外，在内存压力下，提供虚拟内存的操作系统可以决定将您地址空间中很少使用的页面移动到磁盘，并在它们被访问时按需获取它们（以响应页面错误）；这样的操作非常昂贵，并且再次严重偏离了访问任何虚拟内存地址都是相同的想法。
从数组的开头到任何给定元素的计算只需要两个操作，一个乘法（乘以 sizeof(element)）和加法。这两个操作都是常数时间。通常使用今天的处理器，它基本上可以立即完成，因为处理器针对这种访问进行了优化。
当我在程序中说 array[4] = 12 时，我实际上只是将内存地址的位表示存储到寄存器中。硬件中的这个物理寄存器将根据我输入的位表示打开相应的电信号。然后，这些电信号将以某种神奇的方式（希望有人能解释其中的魔力）访问物理/主存储器中的正确内存地址。
我不太确定你在问什么，但我没有看到任何与硬件魔法中真正发生的事情相关的答案。希望我的理解足以通过这个冗长的解释（这仍然是非常高的水平）。
array[4] = 12;
因此，从评论看来，您必须获取数组的基地址，然后乘以数组元素的大小（或者如果可以进行优化，则进行移位）以获得地址（从您的程序的角度来看）内存位置。蝙蝠的权利，我们有一个问题。这些物品是否已经在登记册中，还是我们必须去拿它们？数组的基地址可能在寄存器中，也可能不在寄存器中，具体取决于这行代码周围的代码，特别是它之前的代码。该地址可能位于堆栈或其他位置，具体取决于您声明它的位置和方式。这可能与需要多长时间无关。优化编译器可能（经常）预先计算数组 [4] 的地址并将其放置在某个地方以便它可以进入寄存器并且乘法永远不会在运行时发生，因此计算绝对不正确与其他随机访问相比，随机访问的数组 [4] 的时间是固定的。根据处理器的不同，一些直接模式是一条指令，其他指令需要更多，这也与该地址是从 .text 还是堆栈等读取有关的一个因素，等等......为了避免鸡和蛋这个问题死，假设我们有计算出数组[4] 的地址。
从程序员的角度来看，这是一个写操作。从一个简单的处理器开始，没有缓存，没有写缓冲区，没有 mmu 等。最终，简单的处理器会将地址放在处理器内核的边缘，带有写入选通和数据，每个处理器总线都不同于其他处理器系列，但大致相同，地址和数据可以在同一周期或不同周期中出现。命令类型（读、写）可以同时发生，也可以不同。但命令出来了。处理器内核的边缘连接到解码该地址的内存控制器。结果是一个目的地，这是一个外围设备，如果是，是哪一个，在什么总线上，这个内存是什么，如果是，在什么内存总线上等等。假设 ram，假设这个简单的处理器有 sram 而不是 dram。在苹果与苹果的比较中，Sram 更贵、更快。sram 有一个地址和写/读选通脉冲和其他控制。最终您将拥有事务类型、读/写、地址和数据。然而，SRAM 的几何形状将路由和存储各个位在它们各自的晶体管对/晶体管组中。
一个写周期可能是一劳永逸的。完成交易所需的所有信息，这是一个写入，这是地址，这是数据，当场就知道。内存控制器可以选择告诉处理器写事务已完成，即使数据不在内存附近。该地址/数据对将花时间进入内存，处理器可以继续运行。一些系统虽然设计是这样的，但处理器写入事务会等待，直到有信号返回以指示写入已经到达内存。在火灾和忘记类型设置中，该地址/数据将在某个地方排队，然后进入内存。队列不能无限深，否则它将是 ram 本身，所以它是有限的，并且有可能并且很可能连续的许多写入可以比另一端写入内存更快地填充该队列。此时，当前和/或下一次写入必须等待队列表明还有空间。因此，在这种情况下，您的写入速度有多快，您的简单处理器是否受 I/O 限制都与先前的事务有关，这些事务可能是也可能不是该指令之前的写入指令。
现在添加一些复杂性。ECC 或任何您想称呼它的名称（EDAC，是另一个名称）。ECC 内存的工作方式是写入都是固定大小的，即使您的实现是四个 8 位宽的内存部分，每次写入为您提供 32 位数据，您必须固定 ECC 覆盖并且您必须同时写入数据位和 ecc 位（必须在整个宽度上计算 ecc）。因此，如果这是一个 8 位写入，例如写入 32 位 ECC 保护存储器，那么该写入周期需要一个读取周期。读取 32 位（检查读取时的 ecc）修改该 32 位模式中的新 8 位，计算新的 ecc 模式，写入 32 位加上 ecc 位。自然，写入周期的读取部分可能会以 ecc 错误结束，这只会让生活变得更加有趣。通常可以纠正单位错误（如果不能纠正，ECC/EDAC 有什么好处），多位错误则不能。硬件如何设计来处理这些故障会影响接下来发生的事情，读取故障可能只是回溯到导致写入事务故障的处理器，或者它可能会作为中断返回，等等。但这里是另一个随机访问的地方与另一个不同，这取决于正在访问的内存，并且读取-修改-写入的访问大小肯定比简单的写入花费更长的时间。
即使没有 ECC，Dram 也可以属于这种固定宽度类别。实际上，所有内存在某些时候都属于这一类。存储器阵列在硅上针对以位为单位的特定高度和宽度进行了优化。您不能违反该内存，它只能在该级别以该宽度的单位进行读取和写入。硅库将包括许多几何形状的 ram，设计人员将为他们的零件选择这些几何形状，零件将有固定的限制，通常您可以使用多个零件来获得该尺寸的整数倍宽度，有时设计会如果只有某些位发生变化，则允许您仅写入其中一个部分，或者某些设计会强制所有部分亮起。注意下一个 ddr 系列模块是如何插入家用计算机或笔记本电脑的，第一波是板子两边的很多部分。然后，随着该技术变得越来越陈旧，越来越乏味，它可能会变成电路板两侧的零件更少，最终在该技术过时之前在电路板的一侧变得更少，我们已经进入下一个。
这个固定宽度类别也带有对齐惩罚。不幸的是，大多数人都是在 x86 机器上学习的，这不会像许多其他平台一样限制您使用对齐的访问。如果允许，未对齐访问在 x86 或其他系统上存在一定的性能损失。当人们第一次学习有关对齐访问的程序员时，通常是当人们去 mips 或通常在某些电池供电设备上的手臂时。并且遗憾地发现它们是痛苦的而不是祝福（由于编程的简单性和由此带来的硬件优势）。简而言之，如果您的内存是 32 位宽并且只能访问、读取或写入，一次 32 位，这意味着它仅限于对齐访问。32 位宽内存上的内存总线通常没有低地址位 a[1: 0] 因为它们没有用。从程序员的角度来看，那些低位是零。如果我们的写入是针对这些 32 位存储器之一的 32 位，并且地址是 0x1002。然后有人必须读取地址 0x1000 处的内存并获取我们的两个字节并修改该 32 位值，然后将其写回。然后取地址 0x1004 的 32 位并修改两个字节并将其写回。单个写入的四个总线周期。如果我们向地址 0x1008 写入 32 位，尽管这将是一个简单的 32 位写入，没有读取。然后写回来。然后取地址 0x1004 的 32 位并修改两个字节并将其写回。单个写入的四个总线周期。如果我们向地址 0x1008 写入 32 位，尽管这将是一个简单的 32 位写入，没有读取。然后写回来。然后取地址 0x1004 的 32 位并修改两个字节并将其写回。单个写入的四个总线周期。如果我们向地址 0x1008 写入 32 位，尽管这将是一个简单的 32 位写入，没有读取。
SRAM 与 DRAM。DRAM 非常慢，但超级便宜。每比特晶体管数量的一半到四分之一。（4 用于 SRAM，例如 1 用于 DRAM）。只要电源打开，Sram 就会记住这一点。DRAM 必须像可充电电池一样被刷新。即使电源停留在一个位上，也只会被记住很短的时间。因此，沿途的一些硬件（ddr 控制器等）必须定期执行总线周期，告诉 ram 记住一定的内存块。这些周期从您想要访问该内存的处理器中窃取时间。dram 很慢，盒子上可能写着 2133Mhz（2.133ghz）。但它真的更像 133Mhz ram，对 0.133Ghz。第一个作弊是 ddr。通常，数字世界中的事情每个时钟周期发生一次。时钟进入断言状态，然后进入取消断言状态（1 和 0），一个周期就是一个时钟。DDR意味着它可以在高半周期和低半周期都做一些事情。这样 2133Ghz 内存就真正使用了 1066mhz 时钟。然后发生类似并行的管道，您可以以如此高的速率快速输入命令，但最终必须实际访问该 ram。整体 DRAM 是不确定的并且非常缓慢。另一方面，Sram 不需要刷新，只要电源打开就可以记住。可以快几倍（133mhz * N），以此类推。它可以是确定性的。您可以以如此高的速率快速输入命令，但最终必须实际访问该内存。整体 DRAM 是不确定的并且非常缓慢。另一方面，Sram 不需要刷新，只要电源打开就可以记住。可以快几倍（133mhz * N），以此类推。它可以是确定性的。您可以以如此高的速率快速输入命令，但最终必须实际访问该内存。整体 DRAM 是不确定的并且非常缓慢。另一方面，Sram 不需要刷新，只要电源打开就可以记住。可以快几倍（133mhz * N），以此类推。它可以是确定性的。
下一个障碍，缓存。缓存有好有坏。缓存通常由 sram 制成。希望您对缓存有所了解。如果处理器或上游的某个人已将事务标记为不可缓存，则它会通过未缓存的方式到达另一侧的内存总线。如果可缓存，则在表中查找地址的一部分，这将导致命中或未命中。这是一次写入，取决于缓存和/或事务设置，如果未命中，它可能会传递到另一端。如果命中，则数据将被写入缓存内存，这取决于缓存类型，它也可能传递到另一端，或者数据可能位于缓存中等待其他一些数据块将其驱逐，然后它被写入另一端。缓存肯定会进行读取，有时会使写入不确定。顺序访问具有最大的好处，因为您的驱逐率较低，缓存行中的第一次访问相对于其他访问速度较慢，然后其余的访问速度较快。无论如何，这就是我们得到这个随机访问术语的地方。随机访问与旨在使顺序访问更快的方案背道而驰。
有时缓存的远端有一个写缓冲区。一个相对较小的队列/管道/缓冲区/fifo，包含一些写入事务。另一个火并忘记交易，这些好处。
多层缓存。l1，l2，l3...L1 通常是最快的，无论是技术还是接近度，通常是最小的，从那里开始，它的速度和大小都会上升，其中一些与内存成本有关。我们正在执行写入操作，但是当您执行启用缓存的读取操作时，请了解如果 l1 未命中，则转到 l2，如果未命中，则转到 l3，如果未命中，则转到主存，然后 l3、l2 和l1 all 将存储一个副本。因此，所有 3 项均未命中当然是最痛苦的，并且比完全没有缓存的情况要慢，但是顺序读取将为您提供现在处于 l1 且超快的缓存项，以便缓存成为有用的顺序读取与直接从慢速 DRAM 读取那么多内存相比，通过缓存线总体上花费的时间应该更少。一个系统不必有 3 层缓存，它可以变化。
缓存有助于解决对齐问题。但是，跨缓存行的非对齐访问当然会受到更严重的惩罚。缓存倾向于使用称为缓存行的内存块进行操作。这些通常是另一侧内存大小的整数倍。例如 32 位内存，例如高速缓存行可能是 128 位或 256 位。因此，如果并且当高速缓存行在高速缓存中时，由于未对齐写入而导致的读取-修改-写入对更快的内存不利，仍然比对齐更痛苦，但没有那么痛苦。如果它是未对齐的读取，并且地址使得该数据的一部分位于高速缓存行边界的一侧，而另一侧位于另一侧，则必须读取两条高速缓存行。例如，一个 16 位的读取可能会花费你很多字节读取最慢的内存，显然比没有缓存时慢几倍。取决于缓存和内存系统的一般设计方式，如果您跨缓存线边界进行写入，它可能会同样痛苦，或者可能没有那么多它可能有一部分写入缓存，而另一部分则消失在远端作为较小尺寸的写入。
下一层复杂性是 mmu。允许处理器和程序员产生平坦内存空间的错觉和/或控制缓存或不缓存的内容，和/或内存保护，和/或所有程序都在同一地址空间中运行的错觉（因此您的工具链始终可以编译/link 例如地址 0x8000）。mmu 在处理器内核端占用一部分虚拟地址。在一个表或一系列表中查找，这些查找通常位于系统地址空间中，因此这些查找中的每一个都可能是上述所有内容中的一个或多个，因为每个都是系统内存上的内存周期。即使您尝试进行写入，这些查找也可能导致 ecc 错误。最终经过一次或两次或三次或更多次读取后，mmu 已经确定了 mmu 另一侧的地址是什么，和属性（可缓存与否等）并传递给下一件事（l1 等），以上所有内容均适用。一些 mmus 在其中有一些先前事务的缓存，请记住，因为程序是顺序的，所以用于提高内存性能错觉的技巧是基于顺序访问，而不是随机访问。因此，一些查找可能会存储在 mmu 中，因此它不必立即进入主存储器......
因此，在具有 mmus、缓存、dram 的现代计算机中，特别是顺序读取，而且写入可能比随机访问更快。差异可能是巨大的。顺序读取或写入中的第一个事务在那一刻是随机访问，因为它从未被看到过或有一段时间了。一旦序列继续，尽管优化按顺序排列，接下来的几个/一些明显更快。事务的大小和对齐方式在性能中也起着重要作用。虽然有很多非确定性的事情发生，但作为具有这些知识的程序员，您可以修改您的程序以使其运行得更快，或者如果不幸或故意修改您的程序以使其运行得更慢。在这些系统之一上，顺序通常会更快。随机访问将是非常不确定的。数组[4]=12；其次是数组[37]=12；这两个高级操作在计算写入地址和实际写入本身时可能会花费显着不同的时间。但例如discarded_variable=array[3]; 数组[3]=11；数组[4]=12；通常可以比 array[3]=11; 执行得更快。数组[4]=12；
C 和 C++ 中的数组具有随机访问权限，因为它们以有限的、可预测的顺序存储在 RAM（随机存取存储器）中。因此，需要一个简单的线性运算来确定给定记录的位置 (a[i] = a + sizeof(a[0]) * i)。该计算具有恒定的时间。从 CPU 的角度来看，不需要“seek”或“rewind”操作，它只是告诉内存“加载地址 X 的值”。
但是：在现代 CPU 上，获取数据需要恒定时间的想法不再正确。它需要恒定的摊销时间，具体取决于给定的数据是否在缓存中。
尽管如此 - 一般原则是无论地址如何，从 RAM 中获取一组给定的 4 或 8 个字节的时间都是相同的。例如，如果您从一个干净的状态访问 RAM[0] 和 RAM[4294967292]，CPU 将在相同数量的周期内获得响应。
#include <iostream>
#include <cstring>
#include <chrono>
// 8Kb of space.
char smallSpace[8 * 1024];
// 64Mb of space (larger than cache)
char bigSpace[64 * 1024 * 1024];
void populateSpaces()
{
memset(smallSpace, 0, sizeof(smallSpace));
memset(bigSpace, 0, sizeof(bigSpace));
std::cout << "Populated spaces" << std::endl;
}
unsigned int doWork(char* ptr, size_t size)
{
unsigned int total = 0;
const char* end = ptr + size;
while (ptr < end) {
total += *(ptr++);
}
return total;
}
using namespace std;
using namespace chrono;
void doTiming(const char* label, char* ptr, size_t size)
{
cout << label << ": ";
const high_resolution_clock::time_point start = high_resolution_clock::now();
auto result = doWork(ptr, size);
const high_resolution_clock::time_point stop = high_resolution_clock::now();
auto delta = duration_cast<nanoseconds>(stop - start).count();
cout << "took " << delta << "ns (result is " << result << ")" << endl;
}
int main()
{
cout << "Timer resultion is " <<
duration_cast<nanoseconds>(high_resolution_clock::duration(1)).count()
<< "ns" << endl;
populateSpaces();
doTiming("first small", smallSpace, sizeof(smallSpace));
doTiming("second small", smallSpace, sizeof(smallSpace));
doTiming("third small", smallSpace, sizeof(smallSpace));
doTiming("bigSpace", bigSpace, sizeof(bigSpace));
doTiming("bigSpace redo", bigSpace, sizeof(bigSpace));
doTiming("smallSpace again", smallSpace, sizeof(smallSpace));
doTiming("smallSpace once more", smallSpace, sizeof(smallSpace));
doTiming("smallSpace last", smallSpace, sizeof(smallSpace));
}
现场演示：http: //ideone.com/9zOW5q
输出（来自ideone，可能并不理想）
Success time: 0.33 memory: 68864 signal:0
Timer resultion is 1ns
Populated spaces
doWork/small: took 8384ns (result is 8192)
doWork/small: took 7702ns (result is 8192)
doWork/small: took 7686ns (result is 8192)
doWork/big: took 64921206ns (result is 67108864)
doWork/big: took 65120677ns (result is 67108864)
doWork/small: took 8237ns (result is 8192)
doWork/small: took 7678ns (result is 8192)
doWork/small: took 7677ns (result is 8192)
Populated spaces
strideWork/small: took 10112ns (result is 16384)
strideWork/small: took 9570ns (result is 16384)
strideWork/small: took 9559ns (result is 16384)
strideWork/big: took 65512138ns (result is 134217728)
strideWork/big: took 65005505ns (result is 134217728)
我们在这里看到的是缓存对内存访问性能的影响。我们第一次点击 smallSpace 时，访问所有 8kb 的小空间大约需要 8100ns。但是当我们立即再次调用它时，两次，它在 ~7400ns 处减少了 ~600ns。
现在我们开始做 bigspace，它比当前的 CPU 缓存更大，所以我们知道我们已经炸毁了 L1 和 L2 缓存。
回到小的，我们确定现在没有缓存，我们再次看到第一次〜8100ns，第二次看到〜7400。
我们吹出缓存，现在我们引入不同的行为。我们使用跨步循环版本。这会放大“缓存未命中”效应并显着影响时间，尽管“小空间”适合 L2 缓存，因此我们仍然看到第 1 遍和接下来的 2 遍之间有所减少。