问谷歌面试问题

EN

一些问题：

1. 散列碰撞可能是可能的主要问题之一。
2. 当数据存储在磁盘中作为哈希表时，频繁读取磁盘也是效率低下的。

答案在一定程度上取决于他们讨论的是一个经典的哈希表实现(比如hashtable / HashMap )还是更复杂的实现。最后，按照今天的标准，对于一台机器/VM来说，30 GB的内存仍然相当大。

所以想想下面发生了什么：

1. 它必须在某个大规模数组中任意位置进行读写。
2. 如果超出某种程度，它就必须增长；参见Java实现中的“负载因子”。
3. 在垃圾收集语言/实现中，存储在哈希表中的所有对象都需要由垃圾收集器检查。

这就导致了以下问题：

1. 现在还不清楚，即使是今天的操作系统也能很好地分配数十个GBs中的内存块。
2. 为了简单起见，假设表的一半实际上是由表本身使用的(不是键和值对象)。所以里面有一个15 gb的数组。因此，每次表增长时，都需要至少再分配15 gb。
3. 即使分配了几十个GB数组，OS也会分页一些内存。因为我们假设了一个很好的哈希函数，所以如果我们使用数组中的大部分数据，我们就会中断页面缓存。会有很多页面错误。
4. 假设我们不使用所有的数据。有些键经常使用，而另一些则不常用。为了说明，假设每个键值都很小-- 128个字节。为了简单起见，假设我们将哈希表中的所有内容都存储为值。所以30G/128 =~250 m条目。但是比如说25k常用的钥匙。(25k /250 m= 0.01%)。但是如果有了一个好的散列函数，这些函数就会均匀地散布在庞大的数组中。即使页面大小很小--比如说4kb，25K (条目)* 128字节(条目大小)= ~3.5Mb的常用数据成本为25K (条目)* 4K (页面大小)=~100 to内存，需要在.效率高达3.5%！
5. 在Java世界中，从业者不推荐堆大小大于4-8GB。当然，也有类似阿祖尔的东西，但这就证明了这一点--一个典型的垃圾收集器并不能很好地扩展到这些大小。

我同意其他海报，谷歌正在寻找作为一个解决方案分发。但我认为，在内心，一个简单的哈希表停止扩展超过一个点。在上面，

1. 如果所有条目的访问相对比较均匀，则必须分发
2. 如果大部分时间都能访问到一些地图，那么使用两张地图(其中一张是最常用的)可以为您买到很多东西。
3. 在Java世界中，使用存储堆外数据的专用映射也可以为您提供性能；例如，请参阅彼得·劳瑞的作品。
4. 即使只是在哈希表中对底层数组进行条带化(就像Java的ConcurrentHashMap那样)，当您不得不增加哈希表时，也可以为您带来重大的改进。

我认为面试官对分布式哈希表的预期是这样的，因为30 my的哈希表不能存储在一台机器上(至少在当前64位的世界中是这样)；根据我个人的经验，相当多的google都围绕着分布式计算、地图缩减等。