哈希算法题目：设计一个支持前缀搜索的哈希映射

题目描述
设计一个哈希映射，除了支持常规的put(key, value)、get(key)、remove(key)操作外，还需要支持startsWith(prefix)操作，用于返回所有以给定前缀开头的键。要求所有操作的时间复杂度尽可能高效。

解题过程

第一步：理解需求分析
我们需要设计一个特殊哈希结构，在标准哈希映射基础上增加前缀搜索功能。关键点在于：

• 标准操作：插入键值对、按键查找、按键删除
• 特殊操作：前缀搜索，需要高效返回所有匹配前缀的键
• 核心挑战：如何高效实现前缀匹配，而不是精确匹配

第二步：数据结构选择
单纯使用一个标准哈希表无法高效支持前缀搜索，因为需要遍历所有键（O(n)时间）。更优方案是结合哈希表与字典树（Trie）：

• 哈希表：存储完整的键值对，支持O(1)的标准操作
• 字典树：专门存储所有键的前缀结构，支持高效前缀搜索

第三步：详细设计

class TrieNode:
    def __init__(self):
        self.children = {}  # 字符到子节点的映射
        self.is_end = False  # 标记是否为一个完整键的结束

class PrefixHashMap:
    def __init__(self):
        self.hash_map = {}      # 主哈希表，存储键值对
        self.trie_root = TrieNode()  # 字典树根节点
    
    def put(self, key: str, value: any) -> None:
        # 1. 更新哈希表
        self.hash_map[key] = value
        
        # 2. 更新字典树
        node = self.trie_root
        for char in key:
            if char not in node.children:
                node.children[char] = TrieNode()  # 创建新节点
            node = node.children[char]  # 移动到子节点
        node.is_end = True  # 标记键的结束
    
    def get(self, key: str) -> any:
        return self.hash_map.get(key, -1)  # 直接从哈希表查询
    
    def remove(self, key: str) -> bool:
        if key not in self.hash_map:
            return False
        
        # 1. 从哈希表删除
        del self.hash_map[key]
        
        # 2. 从字典树删除（可选实现，可标记为惰性删除）
        # 简单实现：不实际删除节点，仅标记is_end=False
        node = self.trie_root
        for char in key:
            node = node.children[char]
        node.is_end = False
        return True
    
    def startsWith(self, prefix: str) -> List[str]:
        # 1. 在字典树中定位到前缀末尾节点
        node = self.trie_root
        for char in prefix:
            if char not in node.children:
                return []  # 前缀不存在
            node = node.children[char]
        
        # 2. 收集所有以该前缀开头的完整键
        results = []
        self._collect_keys(node, prefix, results)
        return results
    
    def _collect_keys(self, node: TrieNode, current_prefix: str, results: List[str]):
        if node.is_end:
            results.append(current_prefix)  # 找到一个完整键
        
        for char, child_node in node.children.items():
            self._collect_keys(child_node, current_prefix + char, results)

第四步：操作复杂度分析

• put操作：O(m)，其中m为键的长度（需要遍历键的每个字符构建字典树）
• get操作：O(1)，直接访问哈希表
• remove操作：O(m)，需要定位到字典树中键的结束位置
• startsWith操作：O(m + k)，其中m为前缀长度，k为匹配键的总字符数

第五步：优化考虑

1. 内存优化：对于实际删除操作，可以实现真正的节点删除，但需要维护引用计数
2. 性能优化：在字典树节点中缓存以该节点为根的子树中的所有键，牺牲空间换时间
3. 并发安全：添加读写锁支持并发操作

第六步：实际应用场景
这种数据结构特别适用于：

• 自动完成系统（输入前缀提示完整内容）
• 搜索引擎的搜索建议
• 文件系统的路径自动补全
• 联系人列表的快速过滤

通过结合哈希表和字典树的优势，我们既获得了O(1)的标准操作性能，又实现了高效的前缀搜索功能。