什么使表查找如此便宜？

Question

前段时间,我学到了一些关于大O符号和不同算法效率的知识.

例如,循环遍历数组中的每个项目以执行某些操作

foreach(item in array)
    doSomethingWith(item)

是一种O(n)算法,因为程序执行的周期数与数组的大小成正比.

令我惊讶的是,表查找是O(1).也就是说,在哈希表或字典中查找键

value = hashTable[key]

无论表格是否有一个密钥,十个密钥,一百个密钥或一个千兆字节密钥,它都会占用相同的周期数.

这真的很酷,我很高兴这是真的,但这对我来说不直观,我不明白为什么这是真的.

我可以理解第一个O(n)算法,因为我可以将它与现实生活中的例子进行比较:如果我有纸张要加盖,我可以逐个浏览每张纸并盖上每张纸.对我来说很有意义的是,如果我有2000张纸,使用这种方法印花的时间比用1000张纸要长两倍.

但我无法理解为什么表查找O(1).我想如果我有一本字典,并且我想找到多态的定义,我将花费O(logn)时间找到它:我将在字典中打开一些页面,看看它是否在多态之前或之后按字母顺序排列.例如,如果它是在P部分之后,我可以在打开的页面之后删除字典中的所有内容,并使用字典的其余部分重复该过程,直到我找到单词polymorphism.

这不是一个O(1)过程:通常需要更长的时间才能在千页词典中找到单词而不是两页词典.我很难想象一个过程需要相同的时间,而不管字典的大小.

tl; dr:你能解释一下如何用O(1)复杂性进行表查找吗？

(如果你告诉我如何复制这个惊人的O(1)查找算法,我肯定会得到一个很大的字典,所以我可以向所有朋友展示我的忍者词典查找技巧)

编辑:大多数答案似乎取决于这个假设:

您可以在固定时间内访问字典中的任何页面

如果这是真的,我很容易看到.但我不知道为什么这个基本假设是正确的:我会使用相同的过程来逐字查找页面.

内存地址也一样,用什么算法加载内存地址？是什么让从地址中找到一块内存变得如此便宜？换句话说,为什么内存访问O(1)？

Answer 1

你应该阅读维基百科的文章.

但实质是你首先将哈希函数应用于你的密钥,它将它转换为整数索引(这是O(1)).然后将其用于索引数组,也就是说O(1).如果散列函数设计得很好,那么在数组中的每个位置只应存储一个(或几个项),因此查找完成.

所以在大规模简化的伪代码中:

ValueType array[ARRAY_SIZE];

void insert(KeyType k, ValueType v)
{
    int index = hash(k);
    array[index] = v;
}

ValueType lookup(KeyType k)
{
    int index = hash(k);
    return array[index];
}

显然,这不会处理冲突,但您可以阅读文章以了解如何处理冲突.

更新

为了解决编辑过的问题,索引到数组是O(1),因为在底层,CPU正在这样做:

    ADD index, array_base_address -> pointer
    LOAD pointer -> some_cpu_register

其中LOAD加载存储在指定地址的内存中的数据.

更新2

而内存负载的原因O(1)实际上只是因为这是我们在讨论计算复杂性时通常指定的公理(参见http://en.wikipedia.org/wiki/RAM_model).如果我们忽略缓存层次结构和数据访问模式,那么这是一个合理的假设.当我们扩展机器的尺寸时,这可能不是真的(具有100TB存储的机器可能不会花费与具有100kB的机器相同的时间量).但通常情况下,我们假设机器的存储容量是恒定的,并且比我们可能看到的任何问题大小都要大得多.因此,对于所有意图和目的,它是一个恒定时间操作.

Answer 2

我会从不同的角度来解决这个问题.希望这能说明为什么访问x[45]和访问x[5454563]需要相同的时间.

RAM布置在电容器的网格(即行和列)中.RAM可以通过激活网格上的特定列和行来寻址特定的内存单元,所以假设你有一个16字节容量的RAM,以4x4网格布局(对于现代计算机而言非常小,但足以说明目的),并且您正在尝试访问内存地址13(1101),首先将地址拆分为行和列,即row 3 (11) column 1 (01).

假设0表示采用左交叉,1表示采取正确的交叉点.因此,当你想要激活第3行时,你会在行的起始门发送一大堆电子,行军电子向右移动,右边到达第3行激活门; 接下来你在列起始门上发送另一支电子军队,柱军电子向左然后向右移动到达第一列激活门.如果行和列都被激活,则只能读/写存储器单元,因此这将允许读/写标记的单元.

所有这些乱码的影响是内存地址的访问时间取决于地址长度,而不是特定的内存地址本身; 如果架构使用32位地址空间(即32个交叉点),则寻址存储器地址45和寻址存储器地址5454563两者仍然必须通过所有32个交叉点(实际上16个交叉点用于行电子和16个交叉点用于列电子).

请注意,实际上,与对电容器充电和放电相比,存储器寻址所需的时间非常少,因此即使我们开始具有512位长度的地址空间(足够用于~1.4*10 ^ 130 yottabyte的RAM,即足以保持在你的RAM中太阳下的一切,这意味着电子必须经过512个交叉点,它实际上不会给实际的内存访问时间增加那么多时间.

请注意,这是现代RAM的粗略过度简化.在现代DRAM中,如果要访问后续内存地址,只需更改列而不花时间更改行,因此访问后续内存比访问完全随机地址要快得多.此外,这个描述完全不知道CPU缓存的影响(尽管CPU缓存也使用类似的网格寻址方案,但是由于CPU缓存使用更快的基于晶体管的电容,因此具有大缓存地址空间的负面影响变得非常关键).然而,重点仍然是,如果你在内存中跳跃,访问其中任何一个将花费相同的时间.