Google是愚蠢的还是我？与可能发生冲突的哈希集与经典安全算法

因此，我正在观看其中一部有关他们如何进行采访的Google视频（https://www.youtube.com/watch?v=XKu_SEDAykw），我发现他们的解决方案很奇怪。由于Google的工作人员很多，所以我现在想知道我是否做错了什么，或者他们做错了。让我总结一下任务和解决方案，以防您不想看它：

任务是为以下问题提供有效的算法：

给定一个整数数组A和一个单独的整数a，找到两个索引i，j，使得A [i] + A [j] = a。

他们从对数组进行排序开始，并产生一个不错的线性时间算法。但是然后，面试官问如果不对数组进行排序会发生什么情况。他们提出了以下线性时间算法（他们说先对数组排序然后使用线性时间算法太慢，尽管它会以nlogn的时间运行）：

他们从头到尾遍历数组，并使用哈希集存储他们已经看到的数字。然后，他们只需要检查数组的每个索引的哈希集（即我是否已经看到需要获取和的数字），并且由于这显然可以在恒定时间内进行，因此整个算法都在线性时间内运行（本质上是哈希集的数量* Array.length）。

现在我的批评是：我认为这种解决方案存在一个巨大的缺陷，本质上在于可能发生碰撞。由于它们假定nlogn较慢，因此我们可以假设哈希集具有比logn少的许多不同条目。现在，在有大量输入的情况下，将n个数字散列到最多log个很多集合中时，发生冲突的可能性趋于1。因此，他们以非常适度的速度增加进行交易（他们假设该数组的速度为100亿，但是对数（以2为底）仍然小于30。但是，将此速度与哈希集算法匹配将意味着超过3亿）数字将被散列到同一位置），几乎可以确定是错误的算法。

我或者对哈希有误解，或者这是解决该问题的糟糕方法。同样，安全的nlogn算法不会比他们给出的算法慢很多，除非数组变得太大以至于哈希算法肯定会发生冲突。

如果一个恒定时间算法为小型数组投入一枚硬币并始终对大型数组说“是”，那么它们的哈希集解决方案平均具有相同的成功率，我不会感到惊讶。

如果我对散列有所误解，请指出，因为我很难相信他们会在一流的计算机工程公司犯这样的错误。

需要明确的是，“哈希集”是一个哈希表，其中键是整个条目。没有关联的值，所以关于密钥的唯一有趣的事实是它的存在。这是哈希表实现中的次要细节。

如前所述，您的陈述没有理由说散列集的大小需要小于log n才能减少查找时间。这是另一回事：哈希集的大小（存储桶数）在数据集的大小中应为线性，以便哈希链的预期长度为O（1）。（对于复杂度分析，哈希链的预期长度是1还是1,000都无关紧要：两者均为O（1）。）

但是，即使预期的哈希表查找不是O（1），哈希仍然比排序有一个巨大的优势：哈希很容易并行化。这对Google非常重要，因为只有并行算法才能处理Google大小的数据集。

在实践中，对这个问题的最佳解决方案（我认为：我还没有看过视频）将使用两个不同的哈希值。第一个散列将每个数字分配给服务器，因此，由于每个服务器具有大量数据，因此它具有很大的存储桶大小。然后，每个服务器使用自己的哈希函数将自己的数据映射到自己的存储桶。

现在，我可以并行扫描整个数据集（使用其他服务器），对于每个条目，询问适当的存储服务器（我使用主哈希解决），其数据集中是否存在加法逆。由于每个条目只能存储在一个服务器（或一组服务器，如果为了可靠性而复制数据）上，因此我实际上不必打扰无关的服务器。（在实践中，我将处理一堆查询，按服务器对它们进行存储，然后（并行）向每台服务器发送查询列表，因为这样可以减少连接建立时间。但是原理是相同的。）

这是解决问题的一种非常简单且几乎无限可扩展的方法，我认为面试官很乐意听到这一问题。并行排序要困难得多，在这种情况下，完全不需要复杂性。

当然，您可能会有一个很好的论据来支持自己的首选策略，一个好的面试官也会很高兴听到一个很好的论据，即使这不是他们以前想到的。好的工程师总是愿意讨论好的想法。而且，讨论不能从以下两个假设开始：两个不同的想法之一必须是“愚蠢的”。