数组和哈希映射如何实现常数时间访问？

Question

具体而言：给定一个哈希（或数组索引），机器如何在常数时间内访问到数据？

我认为即使经过所有其他内存位置（或其他内容），也需要花费与所经过位置数量相同的时间（因此是线性时间）。一位同事曾试图向我解释，但当我们深入讨论电路时，他不得不放弃。

例子：

my_array = new array(:size => 20)
my_array[20] = "foo"
my_array[20] # "foo"

因为我们知道“foo”位于哪个桶中，所以在位置20访问“foo”是恒定的。但我们如何在不经过其他所有桶的情况下神奇地到达那个桶？要到达街区上的第20座房子，您仍然必须经过其他19座...

- keithcelt

---

你知道硬盘盘片是如何不停地旋转的吗？那么，内存条是不会动的；-) - Steve Jessop

如果你能立即跳到第20个房子，那么它将是恒定的。这就是RAM的工作原理。随机访问与顺序访问。在这种情况下，随机意味着您可以从任何“随机”的内存位置读取，而无需先读取其前面的内存。写入也是如此。 - SRM

Answer 1

我们是如何在不经过其他存储单元的情况下神奇地到达那个存储桶的呢？

实际上，“我们”根本不会“去”存储桶。内存物理工作的方式更像是在一个通道上广播存储桶的编号，所有存储桶都在这个通道上监听，并且被叫到编号的那个桶将发送其内容。

计算发生在CPU中。理论上，CPU与所有内存位置的“距离”是相同的（实际上不是，因为缓存会对性能产生巨大影响）。

如果你想了解详细信息，请阅读“每个程序员都应该了解的关于内存的知识”。

- Michael Borgwardt

Answer 2

要理解这一点，必须了解内存的组织和访问方式。你可能需要了解地址解码器的工作原理。事实上，你不需要经过所有其他地址才能访问内存中想要的地址，你可以直接跳转到所需地址。否则我们的计算机将会变得非常缓慢。

- Vincent Ramdhanie

---

但是，对于哈希映射而言，你如何知道需要访问哪一个呢？我的意思是，如果我有一个将字符串映射到整数的映射表，并且我想要访问my_map["dog"]，我要如何知道我需要前往关联数组的哪个索引位置呢？ - seb

关键字“dog”被哈希处理成一个整数，该整数是映射中对应值的索引。 - Vincent Ramdhanie

Answer 3

与图灵机不同，需要按顺序访问内存，计算机使用随机访问内存(RAM)，这意味着如果它们知道数组从哪里开始，并且他们知道要访问数组的第20个元素，它们就知道在内存中查找哪个部分。

这更像是选择共享邮箱中公寓的正确邮箱而不是沿着街道驾驶。

- James

---

我认为这就像从大学图书馆的书库中订购一本书。有人负责在图书馆所宣传的特定时间内交付它。他们可能会沿着一排或多排书走，也可能不会。我很确定他们不一定会经过我所要求的这本书和上一本书之间所有目录编号的书。但这不是我的问题，因为即使他们沿着书架走，他们也足够快地在固定数量的CPU周期内将我的书送到阅览室，而与其目录编号无关。抱歉，是小时数。 - Steve Jessop

Answer 4

有两个重要的事情：

1. my_array 包含了计算机在内存中跳转以获取该数组的信息。
2. index * sizeof type 可以从数组开头得到偏移量。

当数据可以被找到时，1 + 2 = O(1)。

- lukastymo

Answer 5

让我们用C/C++的术语来讨论这个问题；虽然有一些关于C#数组的额外知识，但它并不是真正相关的重点。

给定一个16位整数值的数组：

short[5] myArray = {1,2,3,4,5};

实际发生的是计算机在内存中分配了一块空间。这个内存块为该数组保留，恰好足够容纳整个数组（在我们的例子中为16*5 == 80位 == 10字节），并且是连续的。这些事实是确定的；如果在任何给定时间您的环境中有任何一个或多个不正确，您的程序通常会因访问冲突而崩溃。

因此，考虑到这个结构，变量myArray背后的真正含义是内存块的起始地址。这也是第一个元素的起始位置。每个额外的元素都按顺序排列在第一个元素之后的内存中。为myArray分配的内存块可能如下所示：

00000000000000010000000000000010000000000000001100000000000001000000000000000101
^               ^               ^               ^               ^
myArray([0])    myArray[1]      myArray[2]      myArray[3]      myArray[4]

访问内存地址并读取固定数量的字节被认为是一个常数时间操作。如上图所示，如果您知道三件事情：内存块的起始位置、每个元素的内存大小和您想要的元素的索引，您可以获取每个元素的内存地址。因此，当您在代码中请求myArray[3]时，该请求将通过以下方程式转换为内存地址：

myArray[3] == &myArray+sizeof(short)*3;

因此，通过常数时间计算，您已经找到了第四个元素（索引3）的内存地址，并且通过另一个常数时间操作（或者至少被认为是这样；实际访问复杂度是硬件细节，足够快，您不应该关心），您可以读取该内存。如果您曾经想过，这就是为什么大多数C风格语言中集合的索引从零开始的原因；数组的第一个元素从数组本身的位置开始，没有偏移量（sizeof（anything）* 0 == 0）

在C＃中，有两个显着的区别。 C＃数组具有对CLR有用的一些标头信息。标头首先出现在内存块中，其大小是恒定且已知的，因此寻址方程只有一个关键差异：

myArray[3] == &myArray+headerSize+sizeof(short)*3;

C#不允许在托管环境中直接引用内存，但是运行时本身将使用类似于这样的东西来执行堆外存储器访问。

第二个常见的问题，对于大多数C/C++的变体也是普遍存在的，就是某些类型总是按引用处理。必须使用new关键字创建的所有内容都是引用类型（还有一些对象，如字符串，在代码中看起来像值类型，但实际上也是引用类型）。当实例化引用类型时，它被放置在内存中，不会移动，并且通常不会被复制。表示该对象的任何变量因此在幕后只是内存中对象的内存地址。数组是引用类型（记得myArray只是一个内存地址）。引用类型的数组是这些内存地址的数组，因此访问作为数组元素的对象是一个两步过程；首先计算数组元素的内存地址，然后获取它。那是另一个内存地址，是实际对象的位置（或者至少是可变数据的位置；如何在内存中构造复合类型是一个完全不同的问题）。这仍然是一个常数时间操作；只是比一步多了两步。

- KeithS

---

稀疏数组呢？它们能在常数时间内被访问吗？ - CodeManX

Answer 6

大O符号并不是这样工作的。它应该是衡量特定算法和函数使用了多少计算资源的一种度量标准。它不是用来衡量内存使用量的，如果你在谈论遍历内存，那么它仍然是一个常数时间。如果我需要找到数组的第二个槽位，只需要将偏移量加到指针上即可。现在，如果我有一个树形结构，并且我想要找到一个特定的节点，那么你现在正在谈论O(log n)，因为它不能在第一次查找中找到。平均而言，找到该节点需要O(log n)的时间。

- SRM