谷歌面试问题 [已关闭]

答案部分取决于他们是在谈论经典的哈希表实现（如Java中的HashTable / HashMap）还是更复杂的东西。最后，按照今天的标准，对于一台机器/虚拟机来说，30 GB的内存仍然很大。

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

1. 它必须在某个大型数组中的任意位置读取写入。
2. 如果它超出某种程度的填充，它必须增长;请参阅 Java 实现中的“负载因子”。
3. 在垃圾回收语言/实现中，哈希表中存储的所有对象都需要由垃圾回收器检查

这会导致以下问题：

1. 目前尚不清楚，即使是今天的操作系统也能很好地处理数十GB内存块的分配。
2. 为简单起见，假设表的一半实际上由表本身使用（而不是键和值对象）。所以里面有一个15 GB的数组。因此，每次表增长时，您至少需要再分配 15 GB
3. 即使分配了数十 GB 的阵列，操作系统也会对其中一些内存进行分页。由于我们假设了一个好的哈希函数，如果我们使用数组中的大部分数据，我们将中断页面缓存。会有很多页面错误。
4. 假设我们没有使用所有数据。有些键经常使用，有些则不然。为了说明这一点，假设每个键值都很小 - 128个字节。为简单起见，假设我们将哈希表中的所有内容都存储为值。所以 30G/128 = ~ 250M 条目。但说25k常用键。（25k / 250M = 0.01%）。但是有了良好的哈希函数，它们将均匀地分散在巨大的数组中。即使页面大小很小 - 比如4kb，25K（条目）* 128字节（条目大小）= ~3.5Mb的常用数据也会花费我们25K（条目）* 4K（页面大小）= ~100Mb的内存，需要保持页面...效率高达3.5%！
5. 在 Java 世界中，从业者不建议堆大小大于 4 - 8Gb。当然，有像Azul这样的东西，但这仅仅证明了这一点 - 典型的垃圾收集器不能很好地扩展到这些大小。

我同意谷歌正在寻找分布式解决方案的其他海报。但我认为从本质上讲，一个简单的哈希表停止扩展到一个点之外。在上面，

1. 如果相对均匀地访问所有条目，则必须进行分发
2. 如果大多数时间访问某些地图，则使用两张地图（一张用于最常用的地图）可以为您带来很多好处。
3. 在Java世界中，使用从堆中存储数据的专用映射也可以为您带来性能。例如，参见Peter Lawrey的作品。
4. 即使简单地将底层数组剥离到哈希表中（就像Java的ConcurrentHashMap所做的那样），当你必须增加哈希表时，也可以为你带来重大的改进。

我认为面试官期待分布式哈希表的行，因为30GB哈希表不能存储在一台机器上（至少在当前的64位世界中）;从我个人的经验来看，相当多的谷歌Qs都围绕着分布式计算，map-reduce等，