数组通常如何在底层工作？

Question

他们如何将索引直接映射到值，而无需迭代索引？

如果它相当复杂，我在哪里可以阅读更多内容？

Answer 1

数组只是一块连续的内存，从某个已知地址开始。因此，如果起始地址是p，并且您想要访问第i个元素，那么您只需要计算：

p + i * size

其中size是每个元素的大小（以字节为单位）。

粗略地说，访问任意内存地址需要恒定的时间。

Answer 2

本质上，计算机内存可以描述为一系列寻址槽。要创建一个数组，您需要留出一个连续的块。因此，如果您的阵列需要 50 个插槽，则可以从内存中预留 50 个插槽。在此示例中，假设您为名为 A 的数组预留了从 1019 到 1068 的插槽。A 中的插槽 0 是内存中的插槽 1019。 A 中的插槽 1 是内存中的插槽 1020。 A 中的插槽 2 是内存中的插槽 1021，依此类推。因此，一般来说，要获取数组中的第 n 个槽，我们只需执行 1019+n 即可。所以我们需要做的就是记住起始槽是什么并适当地添加它。

如果我们想确保不会写入超出数组末尾的内存，我们可能还想存储 A 的长度并根据它检查 n 。还有一种情况是，并非我们希望跟踪的所有值都具有相同的大小，因此我们可能有一个数组，其中数组中的每个项目占用多个槽。在这种情况下，如果 s 是每个项目的大小，那么我们需要预留 s 乘以数组中的项目数，并且当我们获取第 n 个项目时，我们需要在开头添加 s 时间 n 而不仅仅是 n 。但在实践中，这很容易处理。唯一的限制是数组中的每个项目的大小相同。

Answer 3

维基百科对此解释得很好：

http://en.wikipedia.org/wiki/Array_data_struct

基本上，选择一个内存基础。然后将索引添加到基数中。像这样：

if base = 2000 and the size of each element is 5 bytes, then:
array[5] is at 2000 + 5*5.
array[i] is at 2000 + 5*i.

二维数组乘以这种效果，像这样：

base = 2000, size-of-each = 5 bytes
array[i][j] is at 2000 + 5*i*j

如果每个索引的大小不同，则需要更多计算：

for each index
  slot-in-memory += size-of-element-at-index

因此，在这种情况下，几乎不可能不进行迭代而直接映射。