0

最近我遇到了一个问题，问有多少位足以用这些假设散列一个网页：

  1. 有 10 亿个网页
  2. 网页平均长度为300字
  3. 我们有 250,000 个英文单词
  4. 页面是 ASCII

显然这个问题没有一个正确的答案，但这个问题的目的是看看一般方法是如何工作的。

4

1 回答 1

2

您还没有定义“散列网页”的含义；该短语出现在这个问题和互联网上的其他几个页面中。在那些其他页面中，它用于表示计算校验和（例如使用sha1sum）以验证内容是否完整。如果这就是你的意思，那么你需要对任何页面的所有位进行“散列”；平均而言，即 300 * 8 * 平均英语单词长度。题目没有说明平均英文字长，但是如果是五个字母加一个空格，那么每页的平均位数是6*300*8或者14400。

如果你的意思是把所有网页的所有单词放入一个索引结构中，以允许搜索找到包含任何给定单词集的所有网页，一个答案是大约 10^13 位：在一个索引结构中有 3000 亿个单词引用十亿页；每个引用使用 log_2(1G) 位，或者大约 30 位，如果引用是天真的存储的话；因此 9 万亿位，或大约 10^13。您还可以计算出十亿个 URL 的原始存储至少比这小一个数量级，即最多 10^12 位。可以使用特殊方法将引用存储减少几个数量级，但由于 URL 更容易压缩或紧凑保存（例如，通过 trie），引用存储可能仍然远远超过存储 URL 所需的存储量.

于 2012-10-11T02:03:38.350 回答