无需维护双哈希表，高效查询含指定令牌的文档ID最优方案

问题背景 #

系统需接收文档ID及其关联的令牌字符串列表，核心需求是快速根据令牌返回所有关联的文档ID。当前实现采用HashMap<String, HashSet<Integer>>构建令牌到文档ID的正向映射，但处理文档令牌列表被完全覆盖的场景时，必须额外维护HashMap<Integer, HashSet<String>>来清理旧令牌的关联关系，存在以下问题：

• 空间冗余：双映射结构存储了重复的关联数据
• 数据同步风险：两个映射需严格保持一致，并发场景下易出现数据不一致

方案需支持数万级文档与令牌的高效扩展。

场景示例 #

insertDocument(docId: 1, tokens: {token1, token2, token3} )
// 查询token1返回docIDs:[1]
insertDocument(docId: 2, tokens: {token1, token2, token3} )
// 查询token1返回docIDs:[1, 2]
insertDocument(docId: 1, tokens: {token4, token5, token6} )
// 查询token1返回docIDs:[2]
// 查询token4返回docIDs:[1]

当前实现代码 #

private HashMap<Integer, HashSet<String>> documentLookupMap;
private HashMap<String, HashSet<Integer>> tokenLookupMap;

private void insertDocument(int docId, HashSet<String> tokens ) {

    if( documentLookupMap.containsKey(docId)) {
        // 清理旧令牌关联
        var oldTokens = documentLookupMap.get(docId);
        for (String token : oldTokens) {
            tokenLookupMap.get(token).remove(docId);
            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>();
}

优化方案：版本号验证+延迟清理 #

该方案通过版本号标记文档的令牌状态，无需维护严格同步的双映射结构，既保证查询性能，又避免数据同步风险。

核心结构设计 #

// 存储每个文档的当前令牌快照与版本号
private static class TokenSnapshot {
    Set<String> tokens;
    int version;

    TokenSnapshot(Set<String> tokens, int version) {
        this.tokens = new HashSet<>(tokens);
        this.version = version;
    }
}

private final Map<Integer, TokenSnapshot> docTokenMap = new HashMap<>();
// 令牌 -> 文档ID -> 关联版本号（仅保留当前/历史版本关联，查询时验证有效性）
private final Map<String, Map<Integer, Integer>> tokenDocVersionMap = new HashMap<>();
// 原子生成版本号，保证并发场景下版本唯一
private final AtomicInteger versionGenerator = new AtomicInteger(0);

核心方法实现 #

插入/更新文档令牌

private void insertDocument(int docId, Set<String> tokens) {
    int newVersion = versionGenerator.incrementAndGet();
    TokenSnapshot oldSnapshot = docTokenMap.put(docId, new TokenSnapshot(tokens, newVersion));

    // 更新新令牌的文档版本关联
    for (String token : tokens) {
        tokenDocVersionMap.computeIfAbsent(token, k -> new HashMap<>())
                          .put(docId, newVersion);
    }

    // 可选：立即清理旧令牌的过期关联（若追求实时空间优化）
    // 若允许延迟清理，可跳过此步骤，留到查询时自动清理
    if (oldSnapshot != null) {
        for (String oldToken : oldSnapshot.tokens) {
            Map<Integer, Integer> docVersions = tokenDocVersionMap.get(oldToken);
            if (docVersions != null) {
                docVersions.remove(docId);
                if (docVersions.isEmpty()) {
                    tokenDocVersionMap.remove(oldToken);
                }
            }
        }
    }
}

根据令牌查询文档ID

private Set<Integer> getDocsForToken(String token) {
    Map<Integer, Integer> docVersions = tokenDocVersionMap.get(token);
    if (docVersions == null) {
        return Collections.emptySet();
    }

    Set<Integer> validDocs = new HashSet<>();
    Iterator<Map.Entry<Integer, Integer>> iterator = docVersions.entrySet().iterator();
    while (iterator.hasNext()) {
        Map.Entry<Integer, Integer> entry = iterator.next();
        int docId = entry.getKey();
        int storedVersion = entry.getValue();
        TokenSnapshot currentSnapshot = docTokenMap.get(docId);

        // 仅保留与文档当前版本匹配的关联
        if (currentSnapshot != null && currentSnapshot.version == storedVersion) {
            validDocs.add(docId);
        } else {
            // 清理过期无效的关联条目
            iterator.remove();
        }
    }

    // 若令牌下已无有效文档，移除该令牌的映射
    if (docVersions.isEmpty()) {
        tokenDocVersionMap.remove(token);
    }

    return validDocs;
}

方案优势 #

1. 无同步风险：通过版本号验证关联有效性，即使并发更新也不会出现数据不一致
2. 空间高效：无需存储双向重复映射，旧关联可通过延迟清理自动回收
3. 性能优异：核心操作均为O(1)复杂度，插入/查询性能可支持数万级规模扩展
4. 灵活可控：可选择立即清理或延迟清理旧关联，平衡实时性与性能

内容的提问来源于stack exchange，提问作者Blasterdude8