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

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

1. put(key, value)：插入键值对，键为字符串类型。
2. get(key)：返回键对应的值，若键不存在返回空。
3. remove(key)：删除键值对。
4. prefixSearch(prefix)：返回所有键以指定前缀开头的键值对。

要求：put、get、remove 操作平均时间复杂度为 O(L)（L 为键的长度），prefixSearch 时间复杂度为 O(L + K)（K 为匹配的键数量）。

解题过程

步骤1：分析需求与数据结构选择

• 单纯使用哈希表（如 unordered_map）可快速实现 put、get、remove，但无法高效支持前缀搜索（需遍历所有键，O(N) 复杂度）。
• Trie（字典树） 天然支持前缀搜索，但需结合哈希表来存储每个键对应的值，以支持快速查找和删除。

选择方案：

• 用 Trie 存储所有键的字符路径，每个 Trie 节点记录一个哈希表，存储以当前节点为结尾的键的值（支持键的重复插入覆盖）。
• 通过 Trie 的路径搜索实现前缀匹配。

步骤2：设计 Trie 节点结构

每个 Trie 节点包含：

1. children：哈希表（字符 → 子节点指针），替代固定大小的数组，节省空间。
2. value：可选字段，若当前节点是某个键的结尾，存储该键对应的值（但需处理键覆盖问题）。

优化：

• 若直接在每个节点存 value，删除操作需处理路径重叠的键（如先插入 "apple"，再插入 "app"）。
• 更安全的方法：在 Trie 中只记录键的路径，另用一个全局哈希表 key_value_map 存储键值对，Trie 节点仅标记键的结束（布尔标志位）。

步骤3：具体实现方案

数据结构定义

#include <unordered_map>
#include <string>
#include <vector>
using namespace std;

class TrieNode {
public:
    unordered_map<char, TrieNode*> children;
    bool isEnd;  // 标记当前节点是否为某个键的结尾
    TrieNode() : isEnd(false) {}
};

class PrefixHashMap {
private:
    TrieNode* root;
    unordered_map<string, int> key_value_map;  // 独立存储键值对

    // 辅助函数：在 Trie 中插入键的路径
    void insertKeyToTrie(const string& key) {
        TrieNode* node = root;
        for (char c : key) {
            if (node->children.find(c) == node->children.end()) {
                node->children[c] = new TrieNode();
            }
            node = node->children[c];
        }
        node->isEnd = true;  // 标记键结束
    }

    // 辅助函数：删除键的路径（若没有其他键依赖该路径）
    void removeKeyFromTrie(const string& key) {
        TrieNode* node = root;
        vector<TrieNode*> path = {root};  // 记录路径节点，用于回溯删除
        for (char c : key) {
            if (node->children.find(c) == node->children.end()) return;
            node = node->children[c];
            path.push_back(node);
        }
        node->isEnd = false;  // 取消结束标记

        // 从叶子节点向上回溯，删除无用的节点
        for (int i = path.size() - 1; i > 0; i--) {
            TrieNode* cur = path[i];
            TrieNode* parent = path[i - 1];
            if (cur->children.empty() && !cur->isEnd) {
                parent->children.erase(key[i - 1]);  // 删除父节点对当前节点的引用
                delete cur;
            } else {
                break;  // 当前节点有其他键依赖，停止删除
            }
        }
    }

public:
    PrefixHashMap() { root = new TrieNode(); }

    // 操作1：插入键值对
    void put(string key, int value) {
        if (key_value_map.find(key) != key_value_map.end()) {
            key_value_map[key] = value;  // 键已存在，覆盖值
        } else {
            insertKeyToTrie(key);  // 在 Trie 中插入路径
            key_value_map[key] = value;
        }
    }

    // 操作2：获取值
    int get(string key) {
        if (key_value_map.find(key) != key_value_map.end()) {
            return key_value_map[key];
        }
        return -1;  // 键不存在
    }

    // 操作3：删除键值对
    void remove(string key) {
        if (key_value_map.find(key) == key_value_map.end()) return;
        key_value_map.erase(key);
        removeKeyFromTrie(key);  // 从 Trie 中删除路径（若无用）
    }

    // 操作4：前缀搜索
    vector<pair<string, int>> prefixSearch(string prefix) {
        vector<pair<string, int>> result;
        TrieNode* node = root;
        // 遍历前缀字符
        for (char c : prefix) {
            if (node->children.find(c) == node->children.end()) {
                return result;  // 前缀不存在
            }
            node = node->children[c];
        }
        // 从当前节点开始DFS收集所有以 prefix 开头的键
        dfs(node, prefix, result);
        return result;
    }

    // DFS 收集所有匹配的键
    void dfs(TrieNode* node, string current, vector<pair<string, int>>& result) {
        if (node->isEnd) {
            string key = current;
            if (key_value_map.find(key) != key_value_map.end()) {
                result.push_back({key, key_value_map[key]});
            }
        }
        for (auto& child : node->children) {
            dfs(child.second, current + child.first, result);
        }
    }
};

步骤4：复杂度分析

• put/get/remove：
  • 哈希表操作 O(1)，Trie 插入/删除/查找路径 O(L)，总体 O(L)。
• prefixSearch：
  • 定位前缀节点 O(L)，DFS 收集所有匹配键 O(K)（K 为结果数量），总体 O(L + K)。

步骤5：边界情况处理

1. 空键处理：若键为空字符串，prefixSearch("") 应返回所有键。
2. 覆盖插入：插入已存在的键时，需覆盖值并保持 Trie 结构不变。
3. 删除不存在的键：直接忽略。
4. Trie 路径清理：删除键后需回溯删除无用的节点，避免内存泄漏。

总结
通过结合 Trie 的前缀匹配能力和 哈希表 的快速查找，本设计高效满足了所有操作要求。关键点在于用哈希表独立存储键值对，Trie 仅管理键的路径关系，从而简化删除和覆盖操作的处理。