在LightWAN系统中,有个DomainSet域名的集合对象,单个DomainSet包含数10万个不等的域名,给一个域名,高效判断这个DomainSet中是否包含这个指定域名 要注意域名的层级,比如google.com是包含maps.google.com这个域名的 Java实现
时间: 2023-05-27 21:06:54 浏览: 80
可以使用Trie树来实现高效的域名匹配。Trie树是一种树形数据结构,用于高效地存储和搜索字符串集合。对于DomainSet中的每个域名,都可以将其按照层级拆分成若干个部分,然后依次插入到Trie树中。比如对于google.com,可以将其拆分成["google", "com"]两个部分,然后将其插入到Trie树中。对于maps.google.com,可以将其拆分成["maps", "google", "com"]三个部分,然后将其插入到Trie树中。最后,对于需要判断的指定域名,也按照层级拆分成若干个部分,然后从Trie树的根节点开始依次搜索,如果存在某个节点的值与指定域名的某个部分相等,就继续向下搜索;如果不存在这样的节点,或者指定域名的所有部分都被搜索完毕但仍未找到,就说明指定域名不在该DomainSet中。
Java代码实现如下:
```java
public class DomainSet {
private TrieNode root;
public DomainSet(String[] domains) {
root = new TrieNode();
for (String domain : domains) {
String[] parts = domain.split("\\.");
TrieNode node = root;
for (int i = parts.length - 1; i >= 0; i--) {
String part = parts[i];
TrieNode child = node.children.get(part);
if (child == null) {
child = new TrieNode();
node.children.put(part, child);
}
node = child;
}
node.isEnd = true;
}
}
public boolean contains(String domain) {
String[] parts = domain.split("\\.");
TrieNode node = root;
for (int i = parts.length - 1; i >= 0; i--) {
String part = parts[i];
TrieNode child = node.children.get(part);
if (child == null) {
return false;
}
if (child.isEnd) {
return true;
}
node = child;
}
return false;
}
private static class TrieNode {
Map<String, TrieNode> children;
boolean isEnd;
TrieNode() {
children = new HashMap<>();
isEnd = false;
}
}
}
```
其中,TrieNode表示Trie树中的一个节点,包含一个子节点的映射表children和一个是否为单词结尾的标记isEnd。在构造函数中,对于每个域名,都将其拆分成若干个部分,然后从Trie树的根节点开始依次插入;在contains方法中,也将指定域名拆分成若干个部分,然后从Trie树的根节点开始依次搜索,如果存在某个节点的isEnd为true,就说明指定域名在该DomainSet中。
阅读全文