谷歌面试问题

Question

这是谷歌面试中的一个问题：

如果哈希表的大小超过30GB，可能会出现什么问题 （忽略坏的哈希函数问题）？

我不知道答案。有什么满意的答案吗？

谢谢。

- alan

---

这取决于情况。您有30GB的内存吗？这将是我首先问他们的问题。 - Brian Roach

重新开放投票：虽然问题标题不太具体，但讨论哈希表如何扩展以及合适的替代方案与编程非常相关。也许发帖人可以重新陈述问题，重点关注大型哈希表的情况。 - Dilum Ranatunga

我投票将此移至programmers.stackexchange.com，但我不希望它被关闭。投票要重新开放。 - Daniel Trebbien

你问为什么是30吗？如果我理解正确的话，这是因为在32位系统上无法工作，因为哈希表头至少需要2^36。 :) - BanditoBunny

Answer 1

答案部分取决于他们是否在谈论经典的哈希表实现（例如Java中的HashTable / HashMap）或更复杂的东西。最终，按照今天的标准，30 GB的内存仍然相当大的单个机器/虚拟机。

所以想一想底层发生了什么：

1. 它必须在某些巨大数组的任意位置读写。
2. 如果填满超过某个度量标准，它必须增长；请参见Java实现中的“负载因子”。
3. 在垃圾收集语言/实现中，哈希表中存储的所有对象都需要被垃圾收集器检查

这导致了以下问题：

1. 即使是现今的操作系统，处理分配数十GB的内存块也不是很清楚。
2. 为了简单起见，假设表格的一半实际上被表格本身使用（而不是键和值对象）。因此，里面有一个15GB的数组。所以每次表格增长时，你需要分配至少另外的15GB。
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这样的东西，但这只是证明了这一点--典型的垃圾收集器不能很好地扩展到这些大小。

我同意其他帖子中的观点，Google正在寻找分布式解决方案。但是我认为，在本质上，简单的哈希表在某个点之后就无法扩展了。在上面的例子中，

1. 如果所有条目被相对均匀地访问，则必须进行分发。
2. 如果有一些条目大多数时间被访问，则使用两个映射（一个用于最常用）可以节省很多时间。
3. 在Java世界中，使用专门存储堆外数据的特殊映射也可以提高性能；例如，请参见Peter Lawrey的工作。
4. 甚至仅将哈希表中的底层数组分成条带（如Java的ConcurrentHashMap所做的那样）也可以在必须增加哈希表时帮助您获得重大改进。

- Dilum Ranatunga

Answer 2

我认为面试官希望听到的是类似于分布式哈希表的解决方案，因为在当前的64位世界中，30GB的哈希表无法存储在单个计算机上；从我的个人经验来看，谷歌的许多问题都涉及到分布式计算、MapReduce等技术。

- vine'th

---

在64位的计算机上，30 GiB的地址是可以被访问的。理论上，在32位的计算机上也是可以访问的，只要操作系统支持类似于Windows的“Address Windowing Extensions API”这样的东西。 - Daniel Trebbien

现在，高端机器可以轻松容纳超过1TiB的RAM...如果你有足够的钱的话；例如：https://www.crn.com.au/news/aws-launches-2tb-ram-super-machine-410273 - Stephen C

Answer 3

一些问题：

1. 哈希碰撞可能是一个主要的可能性问题。
2. 当数据存储在磁盘中作为哈希表时，频繁地进行磁盘读取也会很低效。

- Saurabh Gokhale

---

为什么哈希碰撞必然导致额外的内存消耗？ - Mu Qiao

我也不理解第二个。那怎么会增加额外的内存消耗呢？ - Mu Qiao

为什么哈希碰撞会成为问题？通常，频繁的哈希碰撞是由于较差的哈希函数导致的，但这个问题明确要求忽略这个问题。想象一下，对于这个特定集合中的对象，哈希函数被哈希到不同的值。30 GiB可以通过35位整数进行寻址，所以强制要求每个对象的5个字节是唯一的。这似乎是很合理的。 - Daniel Trebbien

我认为#1不是答案，#2更有可能回答这个问题，因为：除非你实际拥有30Gb的RAM，否则数据存储在具有高吞吐量但对于随机访问具有高延迟的磁盘（HDD）上（这就是哈希表的全部内容）。虽然我不确定SSD是否可以改善这种情况。 - Tomer W