哈希算法题目：设计一个基于哈希的自动完成系统（支持模糊匹配和频率排序）

题目描述
设计一个自动完成系统，当用户输入一个字符串时，系统能够返回前3个最相关的补全建议。相关度由两个因素决定：

1. 历史频率：用户之前输入过的完整句子的频率
2. 前缀匹配：补全建议必须以当前输入字符串为前缀

系统需要支持两个操作：

• 输入(input(c)): 每次输入一个字符，系统返回当前匹配度最高的3个句子
• 记录(record(sentence)): 记录一个用户输入过的完整句子，更新其频率

解题过程

步骤1：数据结构设计
我们需要设计能够高效支持前缀匹配和频率排序的数据结构：

• 使用Trie树（前缀树）存储所有句子，实现高效前缀匹配
• 每个Trie节点维护一个频率映射，记录以该节点为结尾的句子的频率
• 使用哈希表缓存热门结果，提高查询效率

class TrieNode:
    def __init__(self):
        self.children = {}  # 字符到子节点的映射
        self.sentences = {}  # 以该节点结尾的句子及其频率
        self.is_end = False  # 标记是否为句子结尾

class AutocompleteSystem:
    def __init__(self, sentences, times):
        self.root = TrieNode()
        self.current_input = ""  # 记录当前输入
        self.sentence_freq = {}  # 全局句子频率哈希表
        
        # 初始化历史数据
        for sentence, freq in zip(sentences, times):
            self._insert_sentence(sentence, freq)

步骤2：插入句子的实现
将句子插入Trie树，并更新频率信息：

def _insert_sentence(self, sentence, freq):
    """向Trie树中插入句子并更新频率"""
    node = self.root
    self.sentence_freq[sentence] = self.sentence_freq.get(sentence, 0) + freq
    
    for char in sentence:
        if char not in node.children:
            node.children[char] = TrieNode()
        node = node.children[char]
        # 更新当前节点的句子频率（用于前缀搜索时的排序）
        node.sentences[sentence] = self.sentence_freq[sentence]
    
    node.is_end = True

步骤3：前缀搜索算法
实现基于Trie树的前缀匹配：

def _search_prefix(self, prefix):
    """搜索具有指定前缀的所有句子"""
    node = self.root
    # 遍历到前缀的最后一个字符节点
    for char in prefix:
        if char not in node.children:
            return {}  # 没有匹配的前缀
        node = node.children[char]
    
    return node.sentences  # 返回所有匹配句子的频率映射

步骤4：结果排序和选择
对匹配结果进行排序，选择前3个最优建议：

def _get_top_suggestions(self, sentences_freq, limit=3):
    """根据频率和字典序返回前limit个建议"""
    # 将句子按频率降序、字典序升序排序
    suggestions = []
    for sentence, freq in sentences_freq.items():
        suggestions.append((-freq, sentence))  # 使用负频率实现降序
    
    suggestions.sort()  # 先按频率降序，再按字典序升序
    return [sentence for _, sentence in suggestions[:limit]]

步骤5：完整的输入处理
处理用户输入的每个字符：

def input(self, c):
    """处理用户输入的单个字符"""
    if c == '#':  # 输入结束，记录句子
        if self.current_input:  # 非空句子才记录
            self._insert_sentence(self.current_input, 1)
        self.current_input = ""  # 重置当前输入
        return []
    
    # 追加当前字符
    self.current_input += c
    
    # 搜索匹配前缀的句子
    matched_sentences = self._search_prefix(self.current_input)
    
    # 返回前3个最优建议
    return self._get_top_suggestions(matched_sentences)

步骤6：性能优化 - 缓存机制
添加缓存提高频繁查询的性能：

def __init__(self, sentences, times):
    # ... 其他初始化代码
    self.cache = {}  # 缓存前缀搜索结果

def input(self, c):
    if c == '#':
        # 清空相关缓存
        prefix_to_clear = ""
        for i in range(len(self.current_input)):
            prefix_to_clear = self.current_input[:i+1]
            if prefix_to_clear in self.cache:
                del self.cache[prefix_to_clear]
        
        # 记录句子并重置
        if self.current_input:
            self._insert_sentence(self.current_input, 1)
        self.current_input = ""
        return []
    
    self.current_input += c
    
    # 检查缓存
    if self.current_input in self.cache:
        return self._get_top_suggestions(self.cache[self.current_input])
    
    # 执行搜索并缓存结果
    matched_sentences = self._search_prefix(self.current_input)
    self.cache[self.current_input] = matched_sentences
    
    return self._get_top_suggestions(matched_sentences)

步骤7：完整实现和测试
完整的系统实现和简单测试：

# 初始化系统
sentences = ["i love you", "island", "ironman", "i love leetcode"]
times = [5, 3, 2, 2]
system = AutocompleteSystem(sentences, times)

# 测试输入
print(system.input('i'))  # 返回: ["i love you", "island", "i love leetcode"]
print(system.input(' '))  # 返回: ["i love you", "i love leetcode"]
print(system.input('l'))  # 返回: ["i love you", "i love leetcode"]
print(system.input('o'))  # 返回: ["i love you", "i love leetcode"]
print(system.input('v'))  # 返回: ["i love you", "i love leetcode"]
print(system.input('e'))  # 返回: ["i love you", "i love leetcode"]
print(system.input('#'))  # 结束输入，记录句子

关键要点总结

1. Trie树 + 哈希表的组合提供了高效的前缀匹配和频率管理
2. 频率排序策略确保最相关的结果优先显示
3. 缓存机制优化了频繁查询的性能
4. 实时更新保证新输入的句子能立即影响后续的自动完成建议

这个设计在时间复杂度上，插入操作为O(L)（L为句子长度），查询操作平均为O(1)（得益于缓存），在最坏情况下为O(N)（N为匹配的句子数量）。