如何在大型HashSet中统计指定字符串出现次数并实现O(1)查询

要实现指定字符串（前缀）在单词集合中的出现次数O(1)查询，核心思路是提前预处理所有可能的前缀并缓存计数，而非每次查询都遍历集合。

具体步骤 #

1. 预处理阶段：构建前缀统计字典
   遍历HashSet中的每个单词，生成该单词的所有前缀（比如"houses"的前缀是"h"、"ho"、"hou"、"hous"、"house"、"houses"），用一个HashMap记录每个前缀的出现次数——每生成一个前缀，就将对应键的计数加1。

2. 查询阶段：直接读取缓存结果
   查询指定字符串的出现次数时，直接从HashMap中取出对应值即可；若该字符串不是任何单词的前缀，返回0。这一步时间复杂度严格为O(1)。

代码示例（Java） #

import java.util.*;

public class PrefixCounter {
    public static void main(String[] args) {
        // 初始化单词集合
        Set<String> wordSet = new HashSet<>(Arrays.asList("hello", "hi", "houses", "holder"));
        // 构建前缀统计Map
        Map<String, Integer> prefixCountMap = new HashMap<>();

        // 预处理所有单词的前缀
        for (String word : wordSet) {
            StringBuilder prefixBuilder = new StringBuilder();
            for (char c : word.toCharArray()) {
                prefixBuilder.append(c);
                String prefix = prefixBuilder.toString();
                // 更新计数：存在则加1，不存在则设为1
                prefixCountMap.put(prefix, prefixCountMap.getOrDefault(prefix, 0) + 1);
            }
        }

        // 示例查询：统计"ho"的出现次数
        String targetPrefix = "ho";
        int count = prefixCountMap.getOrDefault(targetPrefix, 0);
        System.out.println(count); // 输出2
    }
}

方案优势 #

• 查询效率：预处理是一次性操作（时间复杂度O(N*L)，N为单词数，L为单词平均长度），后续所有查询均为O(1)，完全满足即时查询要求。
• 对比原方案：将HashSet转字符串用正则匹配的方式，每次查询都要遍历整个集合（O(N)复杂度），单词量越大效率越低，而预处理后的缓存查询彻底解决了这个问题。

注意事项 #

• 内存占用：如果单词量极大，前缀总数会相应增加，但英文单词的前缀重复率很高，实际内存开销在可接受范围内。
• 动态更新：如果后续需要对单词集合进行增删操作，必须同步更新前缀统计Map，否则计数会失效。

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