哈希算法题目：设计一个基于哈希的自动完成系统 题目描述 设计一个自动完成系统，用户输入一个前缀时，系统返回频率最高的前3个搜索词。若频率相同，按字典序排序。系统需支持以下操作： insert(query) ：记录用户输入的一次查询，更新其频率。 autoComplete(prefix) ：根据历史查询，返回以 prefix 为前缀的频率最高的前3个词。 解题过程 步骤1：分析需求与数据结构选择 需要快速根据前缀匹配候选词，并按频率和字典序排序。 核心问题：如何高效存储和检索前缀对应的词？ 选择数据结构： 哈希表 ：存储每个查询词及其频率（ HashMap<String, Integer> ）。 前缀树（Trie） ：每个节点存储以当前路径为前缀的所有词的频率，便于快速检索。 堆（优先队列） ：在前缀树节点中维护一个最小堆（容量为3），动态保存当前前缀下的Top 3词，避免每次全量排序。 步骤2：设计前缀树节点 每个Trie节点包含： children[26] ：指向下一字符的节点（假设仅小写字母）。 minHeap ：存储当前节点对应前缀的Top 3词（按频率和字典序排序）。 注意：堆中需保存词的频率，但排序规则为： 频率高的优先；频率相同则字典序小的优先 （最小堆需自定义比较器，使堆顶元素为最弱候选）。 步骤3：实现插入操作 更新哈希表： frequencyMap.put(query, frequencyMap.getOrDefault(query, 0) + 1) 。 遍历前缀树，从根节点开始，逐个字符向下移动： 若字符节点不存在，则创建新节点。 更新当前路径节点的堆： 若堆中已有该词，移除旧频率词，重新插入新频率词（需重构堆）。 若堆大小不足3，直接加入新词。 若堆已满，比较新词与堆顶词：若新词更优，替换堆顶并调整堆。 步骤4：实现自动完成操作 根据前缀遍历前缀树，找到前缀的最后一个字符节点。 若节点不存在，返回空列表。 返回该节点堆中所有词（需按频率降序、字典序升序重新排序，因为堆中顺序不是最终顺序）。 步骤5：优化细节 堆维护时机 ：在插入时更新路径上所有节点的堆，确保每次自动完成操作只需O(1)时间获取结果。 频率更新处理 ：若词已存在于堆中，需先删除旧记录再插入新记录（使用哈希表辅助定位堆中元素较复杂，可简单维护一个全局频率映射，堆中只存词引用）。 举例说明 假设历史查询： ["apple", "app", "apply", "book"] ，频率为 {"apple":3, "app":2, "apply":2, "book":1} 。 输入前缀 "app" ： 前缀树路径 a→p→p 的堆中存储 [app, apply, apple] （按频率和字典序排序）。 返回： ["apple", "app", "apply"] （频率3的apple排最前，频率相同的按字典序）。 总结 通过哈希表维护全局频率，前缀树维护前缀关系，堆动态保存Top 3结果，实现了高效插入和自动完成操作。时间复杂度：插入O(L·logK)（L为词长，K=3），自动完成O(1)。