我在数据库中有一个表，其中有4个字符串列，每一行表示被阻止的用户或组。
referrer | ip | userAgent | email
我所说的组是指其中一列（任何一列）可以有通配符（星号），这意味着“阻塞所有列”
例如这一行
www.google.com | 127.0.0.2 | * | yahoo.com
意味着每个以“google.com”为推荐人、“127.0.0.2”asIP和“yahoo.com”为电子邮件的用户请求都需要被屏蔽，而不考虑用户代理，因为它有通配符
下面的代码工作在O（n）的复杂性中，对于小尺寸的表来说已经足够好了，但是我的表包含了100多万行。
class BlacklistEntry {
private String referrer, ip, userAgent, email;
private static List<BlacklistEntry> cache = new ArrayList<>();
BlacklistEntry(String referrer, String ip, String userAgent, String email) {
this.referrer = referrer;
this.ip = ip;
this.userAgent = userAgent;
this.email = email;
}
private static boolean isBlacklisted(String ref, String ip, String ue, String email) {
final String MATCH_ALL = "*";
return cache.stream()
.filter(e ->
(MATCH_ALL.equals(e.getReferrer()) || e.getReferrer().equals(ref)) &&
(MATCH_ALL.equals(e.getIp()) || e.getIp().equals(ip)) &&
(MATCH_ALL.equals(e.getUserAgent()) || e.getUserAgent().equals(ue)) &&
(MATCH_ALL.equals(e.getEmail()) || e.getEmail().equals(email)))
.findFirst()
.isPresent();
}
public String getReferrer() {
return referrer;
}
public void setReferrer(String referrer) {
this.referrer = referrer;
}
public String getIp() {
return ip;
}
public void setIp(String ip) {
this.ip = ip;
}
public String getUserAgent() {
return userAgent;
}
public void setUserAgent(String userAgent) {
this.userAgent = userAgent;
}
public String getEmail() {
return email;
}
public void setEmail(String email) {
this.email = email;
}
public static void main(String[] args) {
cache.add(new BlacklistEntry("google.com", "127.0.0.2", "Mozilla", "yahoo.com"));
cache.add(new BlacklistEntry("r1.com", "127.0.0.3", "Mozilla", "*"));
cache.add(new BlacklistEntry("r2.com", "127.0.0.4", "Mozilla", "yahoo.com"));
System.out.println(isBlacklisted("r2.com", "127.0.0.4", "Mozilla", "yahoo.com"));
System.out.println(isBlacklisted("r1.com", "127.0.0.3", "Mozilla", "sould be true"));
System.out.println(isBlacklisted("*", "127.0.0.3", "*", "*"));
}
}
有比O（N）更好的东西吗？我是否应该考虑使用Lucene？
最佳答案
谢谢你的回答
我的第一个尝试是获取所有排列（使用番石榴感谢我的队友使其干净和清晰），使其成为numberparameters^2，并检查缓存中的集合是否包含其中任何一个
private static boolean check(Set cache, String ref, String ip, String ue, String mail) {
return Sets.powerSet(ImmutableSet.of(0, 1, 2, 3)).stream().map(set -> {
BlacklistKey key = new BlacklistKey("*", "*", "*", "*");
for (Integer idx : set) {
switch (idx) {
case 0:
key.setReferrer(ref);
break;
case 1:
key.setIp(ip);
break;
case 2:
key.setUserAgent(ue);
break;
case 3:
key.setEmail(mail);
}
}
return key;
}).anyMatch(keys::contains);
}
最终使用了Lucene
import org.apache.lucene.analysis.standard.StandardAnalyzer;
import org.apache.lucene.document.Document;
import org.apache.lucene.document.Field;
import org.apache.lucene.document.StringField;
import org.apache.lucene.index.DirectoryReader;
import org.apache.lucene.index.IndexWriter;
import org.apache.lucene.index.IndexWriterConfig;
import org.apache.lucene.index.Term;
import org.apache.lucene.search.BooleanClause;
import org.apache.lucene.search.BooleanQuery;
import org.apache.lucene.search.IndexSearcher;
import org.apache.lucene.search.TermQuery;
import org.apache.lucene.store.RAMDirectory;
import java.io.IOException;
class Blacklist {
private static final String MATCH_ALL = "*";
private static IndexSearcher cache;
private enum Fields {
REFERRER, IP, USER_AGENT, EMAIL
}
private static Document getDocument(String referrer, String ip, String userAgent, String email) {
Document doc = new Document();
doc.add(getStringField(referrer, Fields.REFERRER.name()));
doc.add(getStringField(ip, Fields.IP.name()));
doc.add(getStringField(userAgent, Fields.USER_AGENT.name()));
doc.add(getStringField(email, Fields.EMAIL.name()));
return doc;
}
private static StringField getStringField(String val, String field) {
return new StringField(field, val, Field.Store.NO);
}
private static BooleanQuery createQuery(String referrer, String ip, String userAgent, String email) {
return new BooleanQuery.Builder()
.add(createBooleanQuery(Fields.REFERRER.name(), referrer), BooleanClause.Occur.FILTER)
.add(createBooleanQuery(Fields.IP.name(), ip), BooleanClause.Occur.FILTER)
.add(createBooleanQuery(Fields.USER_AGENT.name(), userAgent), BooleanClause.Occur.FILTER)
.add(createBooleanQuery(Fields.EMAIL.name(), email), BooleanClause.Occur.FILTER)
.build();
}
private static BooleanQuery createBooleanQuery(String key, String value) {
return new BooleanQuery.Builder()
.add(new TermQuery(new Term(key, value)), BooleanClause.Occur.SHOULD)
.add(new TermQuery(new Term(key, MATCH_ALL)), BooleanClause.Occur.SHOULD)
.build();
}
private static boolean isBlacklisted(String ref, String ip, String ue, String email) throws IOException {
BooleanQuery query = createQuery(ref, ip, ue, email);
return cache.search(query, 1).totalHits > 0;
}
public static void main(String[] args) throws IOException {
RAMDirectory directory = new RAMDirectory();
IndexWriter writer = new IndexWriter(directory, new IndexWriterConfig(new StandardAnalyzer()));
writer.addDocument(getDocument("ref1", "127.0.0.ip1", "Mozilla UserAgent1", "email.com"));
writer.addDocument(getDocument("ref2", "127.0.0.ip2", "Mozilla UserAgent2", "*"));
writer.close();
DirectoryReader reader = DirectoryReader.open(directory);
cache = new IndexSearcher(reader);
System.out.println(isBlacklisted("ref1", "127.0.0.ip1", "Mozilla UserAgent1", "email.com"));
System.out.println(isBlacklisted("r2.com", "127.0.0.4", "Mozilla", "yahoo.com"));
System.out.println(isBlacklisted("ref2", "127.0.0.ip2", "Mozilla UserAgent2", "this is ignored"));
System.out.println(isBlacklisted("*", "127.0.0.ip2", "Mozilla UserAgent2", "*"));
}
}