数组和哈希映射如何在访问中保持恒定时间？

Question

具体来说:给定哈希(或数组索引),机器如何在恒定时间内获取数据？

在我看来,即使通过所有其他存储器位置(或其他),也需要花费相当于传递的位置数量的时间量(因此线性时间).一位同事曾勇敢地向我解释这一点,但在我们开始接触电路时不得不放弃.

例:

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

在位置20访问"foo"是不变的,因为我们知道哪个桶"foo"在.我们是如何神奇地到达那个桶而不通过所有其他的途中？要到达一个街区#20的房子,你仍然需要通过其他19 ...

Answer 1

我们是如何在没有通过所有其他人的情况下神奇地进入那个桶的？

"我们"根本不"去"桶.RAM物理工作的方式更像是在所有桶监听的通道上广播存储桶的号码,而被调用的号码将向您发送其内容.

计算发生在CPU中.从理论上讲,CPU与所有内存位置的距离相同(实际上并非如此,因为缓存可能会对性能产生巨大影响).

如果你想要粗略的细节,请阅读"每个程序员应该了解的内存".

Answer 2

然后要了解你必须看看如何组织和访问内存.您可能需要查看地址解码器的工作方式.问题是,你不必通过所有其他地址来获取你想要的内存.你实际上可以跳到你想要的那个.否则我们的电脑真的很慢.

Answer 3

与必须按顺序访问内存的图灵机不同,计算机使用随机存取存储器或RAM,这意味着如果他们知道数组的起始位置,并且他们知道他们想要访问数组的第20个元素,他们知​​道什么部分记忆要看.

它不像在街道上行驶,更像是在共享邮箱中为您的公寓选择正确的邮件槽.