algorithm - 是什么让表查找如此便宜？

Question

不久前，我了解了一些有关大 O 表示法和不同算法效率的知识。

例如，循环遍历数组中的每一项以对其执行某些操作

foreach(item in array)
    doSomethingWith(item)

是一个O(n) 算法，因为程序执行的循环次数与数组的大小成正比。

不过，令我吃惊的是表查找是 O(1)。即在哈希表或字典中查找键

value = hashTable[key]

无论表有一个键、十个键、一百个键还是十亿个键，都需要相同的循环次数。

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

我能理解第一个 O(n) 算法，因为我可以将它与现实生活中的例子进行比较:如果我有几张纸要盖章，我可以遍历每一张一张一张地打印纸，并在每张纸上贴上邮票。这对我来说很有意义，如果我有 2,000 张纸，使用这种方法盖章所需的时间是我有 1,000 张纸时的两倍。

但我不明白为什么查表是O(1)。我在想，如果我有一本字典，并且我想找到多态性的定义，我将花费 O(logn) 时间来找到它:我'我将打开字典中的某个页面，看看它是按字母顺序排列在多态性 之前还是之后。比方说，如果它在 P 部分之后，我可以在我打开的页面之后删除字典中的所有内容，并对字典的其余部分重复该过程，直到找到单词 多态性。

这不是一个O(1) 过程:与在两页词典中相比，在一千页词典中查找单词通常需要更长的时间。我很难想象一个无论字典大小如何都需要相同时间的过程。

tl;dr:您能否向我解释一下如何使用 O(1) 复杂度进行表查找？

(如果你告诉我如何复制惊人的 O(1) 查找算法，我肯定会得到一个大胖字典，这样我就可以向我所有的 friend 炫耀我的忍者-查字典的技巧)

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

You have the ability to access any page of a dictionary given its page number in constant time

如果这是真的，我很容易看出来。但我不知道为什么这个基本假设是正确的:我会使用相同的过程来按数字查找页面，就像我按单词查找页面一样。

与内存地址相同，加载内存地址使用什么算法？是什么让从一个地址找到一 block 内存如此便宜？换句话说，为什么内存访问是O(1)？

Answer 1

您应该阅读 Wikipedia article .

但本质是您首先对您的 key 应用哈希函数，将其转换为整数索引(这是 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 的机器花费的时间不同)。但通常，我们假设我们机器的存储容量是恒定的，并且比我们可能看到的任何问题规模都大得多。因此，就所有意图和目的而言，这是一个恒定时间的操作。