哈希算法题目：设计一个支持前缀搜索的哈希映射（Trie与哈希结合）

题目描述
设计一个支持以下操作的哈希映射：

1. put(key, value)：插入键值对
2. get(key)：返回键对应的值，如果键不存在返回-1
3. remove(key)：删除键值对
4. startsWith(prefix)：返回是否存在以prefix为前缀的键

要求结合哈希表和Trie（前缀树）的特性，实现高效的前缀搜索功能。

解题过程

步骤1：理解数据结构需求

• 普通哈希映射能高效完成put/get/remove操作（O(1)时间复杂度）
• 但前缀搜索需要检查所有键，最坏情况需要O(n)时间
• Trie树专门处理前缀搜索，搜索前缀的时间复杂度为O(m)（m为前缀长度）

步骤2：设计复合数据结构

class TrieNode:
    def __init__(self):
        self.children = {}  # 字符到子节点的映射
        self.is_end = False  # 标记是否单词结束

class PrefixHashMap:
    def __init__(self):
        self.hash_map = {}     # 存储实际的键值对
        self.trie_root = TrieNode()  # Trie根节点用于前缀搜索

步骤3：实现put操作

def put(self, key: str, value: int) -> None:
    # 1. 更新哈希映射
    self.hash_map[key] = value
    
    # 2. 更新Trie树
    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  # 标记单词结束

步骤4：实现get操作

def get(self, key: str) -> int:
    return self.hash_map.get(key, -1)  # 直接查询哈希表

步骤5：实现remove操作

def remove(self, key: str) -> None:
    # 1. 从哈希映射中删除
    if key in self.hash_map:
        del self.hash_map[key]
    
    # 注意：Trie树中通常不实际删除节点，只是标记is_end=False
    # 实际应用中可根据需要实现完整的Trie删除逻辑

步骤6：实现startsWith操作

def startsWith(self, prefix: str) -> bool:
    node = self.trie_root
    for char in prefix:
        if char not in node.children:
            return False
        node = node.children[char]
    return True  # 成功遍历完前缀说明存在

步骤7：处理边界情况

def put(self, key: str, value: int) -> None:
    if not key:  # 处理空键
        return
    
    # 如果键已存在，需要更新值但Trie结构不变
    self.hash_map[key] = value
    
    # 只有新键才需要添加到Trie（或者总是更新Trie）
    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

步骤8：完整实现代码

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: int) -> None:
        if not key:
            return
        self.hash_map[key] = value
        
        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) -> int:
        return self.hash_map.get(key, -1)
    
    def remove(self, key: str) -> None:
        if key in self.hash_map:
            del self.hash_map[key]
            # 简单实现：不在Trie中实际删除节点
            # 复杂实现：需要递归删除无用的Trie节点
    
    def startsWith(self, prefix: str) -> bool:
        if not prefix:
            return False
            
        node = self.trie_root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True
    
    def getAllKeysWithPrefix(self, prefix: str) -> List[str]:
        """扩展功能：获取所有以prefix为前缀的键"""
        if not prefix:
            return []
        
        # 先定位到前缀的最后一个节点
        node = self.trie_root
        for char in prefix:
            if char not in node.children:
                return []
            node = node.children[char]
        
        # 深度优先搜索收集所有键
        results = []
        self._dfs_collect(node, prefix, results)
        return results
    
    def _dfs_collect(self, node: TrieNode, current: str, results: List[str]):
        if node.is_end and current in self.hash_map:
            results.append(current)
        
        for char, child_node in node.children.items():
            self._dfs_collect(child_node, current + char, results)

步骤9：复杂度分析

• put操作：O(m)，m为键的长度
• get操作：O(1)，直接哈希表查询
• remove操作：O(1)，哈希表删除
• startsWith操作：O(m)，m为前缀长度
• 空间复杂度：O(n×m)，n为键的数量，m为平均键长

这种设计结合了哈希表的快速查询和Trie树的高效前缀搜索，适用于需要频繁进行前缀匹配的场景。