嵌套哈希与哈希

Question

我正在建立一个webcrawler，我希望尽可能减少在查找已经访问过的网站和更新已经访问过的网站列表上花费的时间。 我想知道哪种数据结构最适合这样的列表。你知道吗

1. 散列的散列：给定一个网站，将域散列到第一个散列表中，然后将url的最后一部分散列到第二个散列表中（当然，第二个散列表与第一个散列表中映射的域一样多，即每个域都有自己的散列表）。你知道吗

   pro：第一个表和嵌套表中最快的查找时间

   con：执行困难？

2. 哈希：简单哈希表对于每个url，映射表中的url。你知道吗

   pro：更简单的方法和实现

   con：查找值的时间较慢（必须在整个表中查找）

提前谢谢！你知道吗

Answer 1

通常最好是一个哈希表，因为在一般情况下查找时间是恒定的，使得一个查找比两个查找更可取。Python哈希表还专门针对处理字符串进行了优化（请参见here）。你知道吗

如果您仍然想实现“hash of hash”解决方案，只需使用dict of set。dict键是域，值是一组子域url。你知道吗

seen_pages = dict()

# Adding a page
seen_pages.setdefault(domain, set()).add(subdomain)

# Check whether page was seen before
is_known = False
seen_subdomains = seen_pages.get(domain)
if seen_subdomains is not None:
    is_known = subdomain in seen_subdomains

如果您真的很好奇在您的特定情况下，表的大小是否真的会减慢速度，那么只需实现这两个版本。代码上的差异应该是最小的。为了进行正确的测试，请预先编译一个url列表，并使用timeit评估这两个实现。你知道吗

不管怎样，我怀疑哈希表查找时间将是您在这里最紧迫的瓶颈。最好把优化时间花在代码的其他方面。你知道吗