在LightWAN系统中,DomainSet是一组域名的集合,单个DomainSet包含数10万个不等的域名,指定一个域名,需要高效判断这个DomainSet中是否包含这个指定域名 要注意域名的层级,比如google.com是包含maps.google.com这个域名的 用Java代码设计并实现DomainSet的数据结构,不使用Trie树
时间: 2023-05-27 10:07:06 浏览: 148
域名判断,用于检测域名是否正确
4星 · 用户满意度95%
一种可行的数据结构是使用哈希表和二叉搜索树的组合。
首先,将每个域名按照"."分割成一个个的子域名,例如"maps.google.com"可以分割成"com"、"google"和"maps"三个子域名。
然后,将每个子域名插入到一个哈希表中,哈希表的键为子域名,值为一个二叉搜索树,用于存储该子域名下的所有子域名。
例如,插入"com"子域名时,哈希表的键为"com",值为一个空的二叉搜索树;插入"google"子域名时,哈希表的键为"google",值为一个只包含"com"子域名的二叉搜索树;插入"maps"子域名时,哈希表的键为"maps",值为一个只包含"google"和"com"子域名的二叉搜索树。
最后,要判断一个指定域名是否在DomainSet中,只需要按照"."分割成子域名,从哈希表中查找每个子域名对应的二叉搜索树,然后在二叉搜索树中查找下一个子域名,直到所有子域名都被找到或者在中途找不到对应的子域名。
以下是Java代码实现:
```
public class DomainSet {
private Map<String, TreeSet<String>> domains = new HashMap<>();
public void addDomain(String domain) {
String[] parts = domain.split("\\.");
String key = "";
for (int i = parts.length - 1; i >= 0; i--) {
String subdomain = parts[i];
TreeSet<String> set = domains.computeIfAbsent(key, k -> new TreeSet<>());
set.add(subdomain);
key = subdomain + "." + key;
}
}
public boolean contains(String domain) {
String[] parts = domain.split("\\.");
String key = "";
for (int i = parts.length - 1; i >= 0; i--) {
String subdomain = parts[i];
TreeSet<String> set = domains.get(key);
if (set == null || !set.contains(subdomain)) {
return false;
}
key = subdomain + "." + key;
}
return true;
}
}
```
阅读全文