在不维护两个哈希映射的情况下，维护和快速查找哪些对象包含特定令牌(字符串)的最佳方式

Question

我的系统接收一个documentID和表示与文档相关联的令牌的字符串列表。我试图优化的主要指标是返回与给定令牌关联的所有文档ID的列表。我很有信心，我应该从HashMap<String, HashSet<Integer>> tokenLookupMap这样的东西开始，其中字符串是令牌，哈希集是包含该令牌的文档ID集。棘手的部分是如何轻松处理被新的令牌列表覆盖的文档(插入使用新输入完全覆盖现有的令牌列表(。例如，如果我的输入看起来像：

insertDocument(docId: 1, tokens: {token1, token2, token3} )
// query on token1 returns docIDs:[1]
insertDocument(docId: 2, tokens: {token1, token2, token3} )
// query on token1 returns docIDs:[1, 2]
insertDocument(docId: 1, tokens: {token4, token5, token6} )
// query on token1 returns docIDs:[2]
// query on token4 returns docIDs:[1]

我需要能够有效地更新tokenLookupMap中的所有值，以反映被覆盖文档中不再存在的任何令牌。目前，我正在维护第二散列映射CCD_；相反的"；lookup透视图，这样我就可以快速查找与给定文档id关联的令牌，并在覆盖之前删除旧的令牌。这无疑允许我通过令牌优化查找(插入时间与查询一样重要(，但让两个结构表示相同的东西并共享大量重叠空间会让我觉得很傻，甚至很危险。除了插入的空间增加和时间略有增加外，我在技术上还面临着结构不同步的风险。

有没有更好的方法可以让我做到这一点？我总是可以把这两个散列映射放在一个单独的类中，并用有限的公共方法将其锁定，但有没有办法改变结构，也许可以避免同时维护两个结构？以下是最相关的代码：

private HashMap<Integer, HashSet<String>> documentLookupMap;
private HashMap<String, HashSet<Integer>> tokenLookupMap;
private void insertDocument(int docId, HashSet<String> tokens ) {
if( documentLookupMap.containsKey(docId)) {
// if we've aleady indexed a doc with the same id we need to clean up first
var oldTokens = documentLookupMap.get(docId);
for (String token : oldTokens) {
tokenLookupMap.get(token).remove(docId);
// not sure if this is beneficial big picture on large data sets / space constraints
if(tokenLookupMap.get(token).isEmpty()) {
tokenLookupMap.remove(token);
}
}
}
documentLookupMap.put(docId, tokens);
for (String token : tokens) {
tokenLookupMap.computeIfAbsent(token,t->new HashSet<Integer>()).add(docId);
}
}
private Set<Integer> getDocsForToken(String token) {
return tokenLookupMap.containsKey(token) ? tokenLookupMap.get(token) : new HashSet<Integer>();
}

这需要有效地扩展到数以万计的文档/令牌

提前感谢您的任何见解！

Answer 1

我想到的一件事是在单独的类中维护Document Token关系，并维护两个仅用于查找的映射：

class Document {
Integer docId;
//using arrays saves some space and tokens don't seem to change that often
Token[] tokens;
}
class Token {
String token;
Set<Document> documents;
}
Map<Integer, Document> docs = new HashMap<>();
Map<String, Token> tokens = new WeakHashMap<>();

当插入一个新文档时，你基本上清除了令牌集并重新构建它：

private void insertDocument(int docId, Set<String> tokens ) {
Document doc = docs.computeIfAbsent(docId, ...);

//clear the tokens
for( Token old : doc.tokens ) {       
old.documents.remove(doc);
}

//add the new tokens
Set<Token> newTokens = new HashSet<>();
for( String t: tokens ) {
Token newToken = tokens.computeIfAbsent(t, ...);
newToken.documents.add(doc);
newTokens.add(newToken);
}
doc.tokens = newTokens.toArray(new Token[0]);
}

当然，这可以优化为忽略未更改的令牌。

请注意对令牌使用WeakHashMap：由于令牌可能在某个时刻被放弃，因此它们不应该再占用任何内存。WeakHashMap将允许垃圾收集器删除那些其他人无法访问的内容，例如那些没有在任何文档中列出的内容。

当然，gc启动之前可能需要一些时间，同时令牌查找可能会返回不再使用的令牌。如果令牌不再具有文档引用，则需要手动筛选这些令牌，或者从令牌映射中删除这些令牌。