下图是我们数据结构类(class)的期末作业。
问题是编写一个 DNS 查找程序，使用已注册的域名服务器将域映射到它们的 IP 地址。
我有一些想法，但我想知道这些是否是实现该计划的正确方法。
我想我可以利用哈希表来注册域名服务器。那么registerDNS , 和 deleteDNS方法将是常数时间。
为了注册 URL，又是一个哈希表。但这里困扰我的是他们给了一个 vector<string> &dnsChain ，它提供有关如何转到包含 URL 的 DNS 的信息。
现在registerURL和 deleteURL也是常数时间。但是我们在哈希表的每个单元格中存储了一个 vector ，我认为这会增加空间复杂度。(如果您有一百万个 URL，每个单元格中有一个 dnsChain 和百万个元素怎么办？)
对于 access方法，我相信我们应该在 DNS 哈希表中查找以确保 dnsChain 中的每个 DNS该 URL 的已注册。如果您在 dnsChain 中有 N 个域名服务器，那么访问 O(N) .这可以接受吗？
也有合并两个DNS的合并方法。我的想法是在 DNS 哈希表的每个单元格中使用一个 vector 。如果我们将 DNS2 合并到 DNS1，那么我们可以将 DNS2 推到 DNS1 的 vector 中，这意味着 DNS1 也包含 DNS2。
可以降低空间复杂度吗？我们必须存储 dnsChain在 URL 哈希表的每个单元格中？
我们是否必须遍历 dnsChain 中的每个 DNS？访问一个URL？(如果10^6 DNS访问一个URL，那岂不是很慢？)
或者在这种情况下我可以使用任何其他辅助数据结构或技术(trie、可扩展哈希、BST)吗？
最佳答案
由于这是作业，我只会给出一些非常高水平的建议。
考虑到许多 dnsChains 都有重复的 URL，我建议将 dnsChains 存储在树中，如果链有很多重复且很长，这可能会节省大量空间。需要注意的一件事是，树必须包含添加/删除次数的计数，并且只有在计数达到 0 时才应删除。
布隆过滤器是一种可用于加速访问功能的简洁数据结构。这是概率性的，但偶尔会出现误报，但绝不会出现漏报。这些也在工业中用于加速缓存。可以找到更多信息here .
关于c++ - DNS 查找、哈希表，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/34519148/