嵌套哈希 VS 哈希

Question

我正在构建一个网络爬虫，我希望尽量减少查找已访问站点和更新已访问站点列表所花费的时间。我想知道哪种数据结构最适合这样的列表。

hash of hash：给定一个网站，将域名散列为第一个散列table，然后散列[=52]的最后一部分=] 在二级哈希 table 中（当然二级哈希 table 与第一个哈希 table 中映射的域一样多，即每个域都有自己的哈希 table ]).

pro：第一个 table 和嵌套
中最快的查找时间
con：实施困难？
哈希：简单哈希table对于每个url，将url映射到table.

pro: 更简单的方法和实现

con：查找值的时间较慢（您必须查找整个 table）

提前致谢！

Answer 1

通常单个散列 table 应该更可取，因为查找时间在一般情况下是恒定的，使一次查找比两次查找更可取。 Python 哈希 tables 也专门针对处理字符串进行了优化（参见 here）。

如果您仍想实施 "hash of hash" 解决方案，只需使用集合字典即可。 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

如果您真的很好奇在您的特定情况下 table 的大小是否真的会减慢速度，只需实现两个版本即可。代码差异应该很小。为了进行适当的测试，预编译一个 url 列表并使用 timeit.

评估两个实现

无论如何，我怀疑散列 table 查找时间将是您最紧迫的瓶颈。可能最好将优化时间花在代码的其他方面。

嵌套哈希 VS 哈希

Nested hash VS hash

python

data-structures

hash

hashtable