题目

不使用任何内建的哈希表库设计一个哈希映射（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]]

解答 & 代码

拉链法解决哈希冲突：

采用整数除法作为哈希函数，为尽可能避免冲突，哈希表的长度应当取一个质数，这里设 **len=769**

对于哈希表的每一位，采用拉链的形式，解决哈希冲突。理论上拉链应该用链表实现，才能实现 O(1) 时间复杂度的删除。但这里的实现为了方便，采用了数组代替链表，并且参考[中等] 380. O(1) 时间插入、删除和获取随机元素的删除方式，将要删除的元素和数组最末端交换位置，再删除数组最后一个元素 ```cpp class MyHashMap { private: vector>> data; int len = 769; // 哈希表的长度，取质数 public: MyHashMap() {

 data.resize(len);

}

// 插入 void put(int key, int value) {

 int hashKey = key % len;    // 在哈希表中的下标
 for(int i = 0; i < data[hashKey].size(); ++i)
 {
     // 如果 key 已在哈希表中，则更新对应的 value
     if(data[hashKey][i].first == key)
     {
         data[hashKey][i].second = value;
         return;
     }
 }
 // key 不在哈希表中，则插入
 data[hashKey].push_back(make_pair(key, value));

}

// 返回 key 对应的 value int get(int key) {

 int hashKey = key % len;
 for(int i = 0; i < data[hashKey].size(); ++i)
 {
     // 如果 key 存在哈希表中，则返回对应的 value
     if(data[hashKey][i].first == key)
         return data[hashKey][i].second;
 }
 // key 不在哈希表中，则返回 -1
 return -1;

}

// 移除 void remove(int key) {

 int hashKey = key % len;
 for(int i = 0; i < data[hashKey].size(); ++i)
 {
     // 如果 key 存在哈希表中，则删除
     // 为了实现数组 O(1) 时间复杂度的删除，将该元素和数组尾部元素交换，在删除数组尾部元素
     // 避免删除当前元素后，数组后面元素的移动带来的时间开销
     if(data[hashKey][i].first == key)
     {
         data[hashKey][i] = data[hashKey].back();
         data[hashKey].pop_back();
         return;
     }
 }

} };

/**

Your MyHashMap object will be instantiated and called as such:
MyHashMap* obj = new MyHashMap();
obj->put(key,value);
int param_2 = obj->get(key);
obj->remove(key); */ ``` 复杂度分析：设哈希表中元素数量为 n，哈希表长为 m

时间复杂度 O(n/m)：设哈希值是均匀分布的，则每个拉链的长度为 n/b，插入、查找、删除都要遍历一条拉链
空间复杂度 O(n)：

执行结果：

执行结果：通过
执行用时：96 ms, 在所有 C++ 提交中击败了 91.72% 的用户
内存消耗：50.7 MB, 在所有 C++ 提交中击败了 88.23% 的用户

hot 100

[简单] 706. 设计哈希映射

题目

解答 & 代码