题目描述

不使用任何内建的哈希表库设计一个哈希映射（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 现在为 [[1,1], [2,2]]
myHashMap.get(3);    // 返回 -1（未找到），myHashMap 现在为 [[1,1], [2,2]]
myHashMap.put(2, 1); // myHashMap 现在为 [[1,1], [2,1]]（更新已有的值）
myHashMap.get(2);    // 返回 1 ，myHashMap 现在为 [[1,1], [2,1]]
myHashMap.remove(2); // 删除键为 2 的数据，myHashMap 现在为 [[1,1]]
myHashMap.get(2);    // 返回 -1（未找到），myHashMap 现在为 [[1,1]]

题解

这个问题可以通过使用一个定长的数组来模拟哈希表的存储结构。

1. 初始化哈希表：创建一个定长的数组 buckets，每个元素是一个链表，用于解决哈希冲突。
2. 哈希函数：实现一个哈希函数 hash(key)，将键映射到数组索引。
3. put操作：计算键的哈希值，然后在对应的链表中插入或更新键值对。
4. get操作：计算键的哈希值，然后在对应的链表中查找键并返回其值。
5. remove操作：计算键的哈希值，然后在对应的链表中删除键。

代码实现

class MyHashMap {
private:vector<list<pair<int, int>>> buckets;static const int BUCKET_SIZE = 769; // 使用一个素数作为桶的数量public:MyHashMap() : buckets(BUCKET_SIZE) {}int hash(int key) { return key % BUCKET_SIZE; }void put(int key, int value) {int index = hash(key);for (auto& kv : buckets[index]) {if (kv.first == key) {kv.second = value;return;}}buckets[index].emplace_front(key, value);}int get(int key) {int index = hash(key);for (auto& kv : buckets[index]) {if (kv.first == key) {return kv.second;}}return -1;}void remove(int key) {int index = hash(key);for (auto it = buckets[index].begin(); it != buckets[index].end();++it) {if (it->first == key) {buckets[index].erase(it);return;}}}
};

复杂度分析

● 时间复杂度：
○ put 操作：平均情况下是 O(1)，最坏情况下是 O(n)，其中 n 是哈希桶中链表的长度。
○ get 操作：平均情况下是 O(1)，最坏情况下是 O(n)。
○ remove 操作：平均情况下是 O(1)，最坏情况下是 O(n)。
● 空间复杂度：O(n)，其中 n 是哈希映射中存储的元素总数。这里使用了一个大小为 BUCKET_SIZE 的 vector 和若干个 list。
这个实现利用了链地址法来解决哈希冲突，通过 vector 和 list 的组合提供了一个高效的哈希映射实现。