哈希算法题目：设计一个支持前缀搜索的哈希映射 题目描述 设计一个哈希映射，除了支持常规的 put(key, value) 、 get(key) 和 remove(key) 操作外，还需要支持 startsWith(prefix) 操作，用于返回所有键以指定前缀开头的键值对。要求高效实现前缀搜索功能。 解题过程 基础哈希映射设计 首先使用标准哈希表（字典）存储键值对，以支持快速的插入、查找和删除操作。键和值可以是任意类型，但为简化，假设键为字符串。 前缀搜索的挑战 直接遍历所有键检查前缀的暴力方法时间复杂度为 O(N* L)（N 是键的数量，L 是前缀长度），效率低。需要优化查询过程。 使用 Trie（前缀树）辅助 Trie 结构 ：每个节点包含子节点的映射（字符到子节点）和可选的值（若当前节点是键的结尾）。 整合思路 ：维护一个主哈希表存储所有键值对，同时维护一个 Trie 结构，其中每个节点存储以当前路径为前缀的所有键的集合（或计数）。 操作同步 ： put(key, value) ：在主哈希表插入键值对，同时在 Trie 中沿路径遍历，为每个前缀节点添加该键（或计数+1）。 get(key) ：直接通过主哈希表查询。 remove(key) ：从主哈希表删除键值对，同时在 Trie 中沿路径遍历，从每个前缀节点移除该键（或计数-1）。 startsWith(prefix) ：在 Trie 中定位到前缀的最后一个节点，返回该节点下所有键的集合（通过深度优先搜索收集）。 优化细节 空间优化 ：Trie 节点仅存储子节点指针和键集合的引用，避免重复存储键字符串。 惰性删除 ：移除键时，Trie 中可保留空节点，后续操作再清理，以平衡效率。 批量返回 ： startsWith 返回迭代器或分页结果，避免一次性加载大量数据。 复杂度分析 put / remove ：O(L)（L 为键长），需更新 Trie。 get ：O(1)，直接访问哈希表。 startsWith ：O(L + K)，其中 K 是匹配键的数量（收集结果需 O(K)）。 总结 通过结合哈希表与 Trie，既保证了常规操作的高效性，又实现了前缀搜索的优化。此结构适用于需要前缀查询的场景（如自动补全系统）。