所以，我正在观看其中一个关于他们如何进行采访的谷歌视频(https://www.youtube.com/watch?v=XKu_SEDAykw)，我发现他们的解决方案很奇怪。由于有很多聪明的人在谷歌工作，我现在想知道我是否做错了什么，或者他们是否做错了。让我总结一下任务和解决方案，以防您不想观看：
任务是为以下问题提供有效的算法：
给定一个整数数组 A 和一个单独的整数 a，找到两个索引 i，j，使得 A[i]+A[j] = a。
他们从对数组进行排序开始，并生成一个很好的线性时间算法。但是面试官问如果数组没有排序会发生什么。他们提出了以下线性时间算法(他们说首先对数组进行排序，然后使用他们的线性时间算法太慢了，尽管它会在nlogn时间内运行)：
他们从第一个到最后一个遍历数组，并使用哈希集来存储他们已经看到的数字。然后他们只需要检查数组每个索引的哈希集(即我是否已经看到了我需要获得总和的数字)，并且由于这显然在恒定时间内是可能的，因此整个算法以线性时间运行(本质上是哈希集的数量 * Array.length)。
现在我的批评：我认为这个解决方案存在一个巨大的缺陷，本质上在于碰撞的可能性。由于他们假设 nlogn 很慢，我们可以假设哈希集的条目少于 logn 许多不同的条目。现在，给定任何大的输入，当将 n 个数字散列到最多登录多个集合中时，发生冲突的概率趋向于 1。因此，他们交换了非常适度的速度提升(他们假设该阵列的 100 亿个很大，但随后对数(基数 2)仍然小于 30。然而，将这种速度与哈希集算法相匹配将意味着超过 3 亿个数字将被哈希到同一位置)，对于几乎确定的错误算法。
我要么误解了哈希处理的某些内容，要么这是解决问题的糟糕解决方案。同样，安全的nlogn算法并不比他们给出的算法慢多少，除非数组变得太大以至于哈希算法肯定会发生冲突。
如果一个恒定时间算法为小数组抛硬币并总是对大数组说是，我不会感到惊讶，平均成功率与他们的哈希集解决方案相同。
如果我误解了散列，请指出这一点，因为我发现很难相信他们会在一流的计算机工程公司犯这样的错误。
需要明确的是，"哈希集"是一个哈希表，其中键是整个条目;没有关联的值，所以关于键的唯一有趣的事实是它存在。这是哈希表实现中的一个小细节。
如前所述，您的陈述没有根据，即哈希集的大小需要小于log n以减少查找时间。反之亦然：哈希集的大小(桶的数量)应该与数据集的大小成线性关系，因此哈希链的预期长度为 O(1)。(对于复杂性分析，哈希链的预期长度是 1 还是 1,000 并不重要：两者都是 O(1)。
但是，即使预期的哈希表查找不是 O(1)，哈希仍然比排序有一个巨大的优势：哈希很容易并行化。这对谷歌来说非常重要，因为只有并行算法才能处理谷歌大小的数据集。
在实践中，这个问题的一个简单解决方案(我认为：我没有看过视频)是使用两个不同的哈希值。第一个哈希将每个数字分配给服务器，因此它具有非常大的存储桶大小，因为每个服务器都有很多数据。然后，每个服务器使用自己的哈希函数将自己的数据映射到自己的存储桶。
现在，我可以并行扫描整个数据集(使用其他服务器)，对于每个条目，询问相应的存储服务器(我使用主哈希计算)加法逆是否在其数据集中。由于每个条目只能存储在一台服务器上(或一组服务器，如果为了可靠性而复制数据)，因此我实际上不必打扰不相关的服务器。(在实践中，我会接受一堆查询，按服务器存储它们，然后并行地向每个服务器发送查询列表，因为这可以减少连接设置时间。但校长是一样的。
这是一种非常简单且几乎无限可扩展的问题方法，我认为面试官会很高兴听到它。并行排序要困难得多，在这种情况下，复杂性是完全不必要的。
当然，你很可能有一个很好的论据支持你自己喜欢的策略，一个好的面试官也会很高兴听到一个好的论点，即使这不是他们以前想到的。优秀的工程师总是乐于讨论好的想法。这种讨论不能从假设两种不同的想法之一一定是"愚蠢的"开始。
由于他们假设 nlogn 很慢，我们可以假设哈希集的 logn 少于 logn 许多不同的条目
错。哈希表的大小将为 O(len(A))。这不会使算法花费超过线性预期时间，因为在算法的运行时中没有哈希表大小的乘法因子。
此外，虽然可能会发生冲突，但通常假定哈希表具有某种冲突解决策略。碰撞不会产生不正确的结果。