01、设计哈希Map

哈喽，大家好，我是厨子，在之前的文章里面，已经给大家介绍过了哈希表的基本性质和解决冲突的方式，大家可以结合题目要求，思考一下，这个题目应该怎么做

https://leetcode.cn/problems/design-hashmap/description/

要求不使用任何内建的哈希表库设计一个哈希映射（HashMap）。

实现 MyHashMap 类：

• MyHashMap() 用空映射初始化对象
• void put(int key, int value) 向 HashMap 插入一个键值对 (key, value)。如果 key 已经存在于映射中，则更新其对应的值 value
• int get(int key) 返回特定的 key 所映射的 value；如果映射中不包含 key 的映射，返回 -1
• void remove(key) 如果映射中存在 key 的映射，则移除 key 和它所对应的 value

到这里需求已经很明确了，设计一个类，实现一些函数即可

示例

输入：
["MyHashMap", "put", "put", "get", "get", "put", "get", "remove", "get"]
[[], [1, 1], [2, 2], [1], [3], [2, 1], [2], [2], [2]]

输出：
[null, null, null, 1, -1, null, 1, null, -1]

解释：
MyHashMap myHashMap = new MyHashMap();
myHashMap.put(1, 1);     // myHashMap 现在为 [[1,1]]
myHashMap.put(2, 2);     // myHashMap 现在为 [[1,1], [2,2]]
myHashMap.get(1);        // 返回 1
myHashMap.get(3);        // 返回 -1（未找到）
myHashMap.put(2, 1);     // myHashMap 现在为 [[1,1], [2,1]]（更新已有的值）
myHashMap.get(2);        // 返回 1
myHashMap.remove(2);     // 删除键为 2 的数据，myHashMap 现在为 [[1,1]]
myHashMap.get(2);        // 返回 -1（未找到）

约束条件

• 0 <= key, value <= 10^6
• 最多调用 10^4 次 put、get 和 remove 方法

我们看到这个输入输出的时候可能有点蒙，输入 MyHashMap，就是初始化，put [1,1]，就是填充 key = 1，value = 1 进哈希表，既然我们懂了题意，那我们来看一下

解题思路

这个题目的难点就是，解决冲突的方式，我们这里使用拉链法来帮我们解决冲突

数组 + 链表法

哈希映射的核心思想是通过哈希函数将键映射到数组的索引位置，从而实现 O(1) 的平均时间复杂度。但由于哈希冲突的存在，我们需要采用冲突解决策略。

这里采用拉链法（Separate Chaining），即数组的每个位置存储一个链表，当多个键映射到同一位置时，它们以链表形式存储。

细节剖析

使用取模运算 hash(key) = key % SIZE，将键映射到数组索引

使用链表存储哈希值相同的键值对

定义一个节点类存储键值对，每个数组位置是一个链表的头节点

结构示意图（大致含义）

暂时无法在飞书文档外展示此内容

操作流程图

暂时无法在飞书文档外展示此内容

代码实现

class MyHashMap {
private:
    // 定义链表节点
    struct Node {
        int key;
        int value;
        Node* next;
        Node(int k, int v) : key(k), value(v), next(nullptr) {}
    };

    static const int SIZE = 1009; // 选择质数作为哈希表大小，减少冲突
    Node* table[SIZE];            // 哈希表数组

    // 哈希函数
    int hash(int key) {
        return key % SIZE;
    }

public:
    MyHashMap() {
        // 初始化所有链表头为空
        for (int i = 0; i < SIZE; i++) {
            table[i] = nullptr;
        }
    }

    void put(int key, int value) {
        int idx = hash(key);
        Node* curr = table[idx];

        // 遍历链表查找是否已存在该key
        while (curr != nullptr) {
            if (curr->key == key) {
                curr->value = value; // 找到则更新
                return;
            }
            curr = curr->next;
        }

        // 未找到，插入到链表头（头插法）
        Node* newNode = new Node(key, value);
        newNode->next = table[idx];
        table[idx] = newNode;
    }

    int get(int key) {
        int idx = hash(key);
        Node* curr = table[idx];

        // 遍历链表查找
        while (curr != nullptr) {
            if (curr->key == key) {
                return curr->value;
            }
            curr = curr->next;
        }

        return -1; // 未找到
    }

    void remove(int key) {
        int idx = hash(key);
        Node* curr = table[idx];
        Node* prev = nullptr;

        // 遍历链表查找并删除
        while (curr != nullptr) {
            if (curr->key == key) {
                if (prev == nullptr) {
                    // 删除的是链表头节点
                    table[idx] = curr->next;
                } else {
                    // 删除的是中间或尾部节点
                    prev->next = curr->next;
                }
                delete curr;
                return;
            }
            prev = curr;
            curr = curr->next;
        }
    }

    ~MyHashMap() {
        // 析构函数，释放所有节点内存
        for (int i = 0; i < SIZE; i++) {
            Node* curr = table[i];
            while (curr != nullptr) {
                Node* temp = curr;
                curr = curr->next;
                delete temp;
            }
        }
    }
};

复杂度分析

时间复杂度

• put 操作：平均 O(1)，最坏 O(n)（所有键哈希到同一位置）
• get 操作：平均 O(1)，最坏 O(n)
• remove 操作：平均 O(1)，最坏 O(n)（需要遍历一遍）

其中 n 是哈希表中存储的键值对数量。通过选择合适的哈希表大小（质数），可以使冲突最小化，使操作接近 O(1)。

空间复杂度

O(SIZE + n)，其中 SIZE 是哈希表数组大小，n 是存储的键值对数量