[706] 设计哈希映射
https://leetcode-cn.com/problems/design-hashmap/description/
- algorithms
- Easy (58.60%)
- Likes: 124
- Dislikes: -
- Total Accepted: 22.7K
- Total Submissions: 38.6K
- Testcase Example: ‘[“MyHashMap”,”put”,”put”,”get”,”get”,”put”,”get”,”remove”,”get”]\n’ +
‘[[],[1,1],[2,2],[1],[3],[2,1],[2],[2],[2]]’
不使用任何内建的哈希表库设计一个哈希映射（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]]
提示：
0 <= key, value <= 106- 最多调用
104次put、get和remove方法
进阶：你能否不使用内置的 HashMap 库解决此问题？
方法1: 暴力一维数组
适用于key范围较小的情况
class MyHashMap {
public:
/** Initialize your data structure here. */
MyHashMap() {
const int N = 1000001;
data = vector<int>(N, -1); //直接初始化为-1
}
/** value will always be non-negative. */
void put(int key, int value) {
data[key] = value;
}
/** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
int get(int key) {
return data[key];
}
/** Removes the mapping of the specified value key if this map contains a mapping for the key */
void remove(int key) {
data[key] = -1;
}
private:
vector<int> data;
};
方法2: 二维数组, 稀疏数组节省空间
通过设置两个hash值来避免冲突
class MyHashMap {
public:
/** Initialize your data structure here. */
MyHashMap() {
data.resize(N);
}
auto getHashValue1(int key){
return key % N;
}
auto getHashValue2(int key){
return key / N;
}
/** value will always be non-negative. */
void put(int key, int value) {
auto hashkey1 = getHashValue1(key);
auto hashkey2 = getHashValue2(key);
if(data[hashkey1].empty()){
data[hashkey1].resize(N, -1);
}
data[hashkey1][hashkey2] = value;
}
/** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
int get(int key) {
auto hashkey1 = getHashValue1(key);
auto hashkey2 = getHashValue2(key);
if(data[hashkey1].empty()){
return -1;
}
return data[hashkey1][hashkey2];
}
/** Removes the mapping of the specified value key if this map contains a mapping for the key */
void remove(int key) {
auto hashkey1 = getHashValue1(key);
auto hashkey2 = getHashValue2(key);
if(!data[hashkey1].empty()){
data[hashkey1][hashkey2] = -1;
}
}
private:
const int N = 1001;
vector<vector<int>> data;
};
方法3: 链地址法 无头节点
这是一种处理冲突的方法, 具体原理如图:
此方法不使用头节点(dummy head node), 将所有关键字为同义词的记录存储在同一线性链表中, 减小空间开销, 但每次都需要判断是否为空节点
需注意当移除键值对时, 对于头节点与非头节点要分开讨论
struct MyListNode{
int key;
int val;
MyListNode* next;
MyListNode() : key(-1), val(-1), next(nullptr) {}
MyListNode(int _key, int _val) : key(_key), val(_val), next(nullptr) {}
};
class MyHashMap {
public:
/** Initialize your data structure here. */
MyHashMap() {
data.resize(N);
}
auto getHashValue(int key){
return key % N;
}
/** value will always be non-negative. */
void put(int key, int value) {
auto hashkey = getHashValue(key);
auto& head = data[hashkey];
if(head==nullptr){
head = new MyListNode(key, value);
return;
}
auto p = head;
auto tail = p;
// add value which has been added
while(p != nullptr){
if(p->key == key){
p->val = value;
return;
}
tail = p;
p = p->next;
}
// add new value
tail->next = new MyListNode(key, value);
}
/** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
int get(int key) {
auto hashkey = getHashValue(key);
auto& head = data[hashkey];
if(head==nullptr){
return -1;
}
auto p = head;
while(p != nullptr){
if(p->key == key){
return p->val;
}
p = p->next;
}
return -1;
}
/** Removes the mapping of the specified value key if this map contains a mapping for the key */
void remove(int key) {
auto hashkey = getHashValue(key);
auto& head = data[hashkey];
if(head==nullptr){
return;
}
auto p = head;
MyListNode* prev = nullptr;
while(p != nullptr){
if(p->key == key){
// remove head
if(prev == nullptr){
auto dummy = head;
head = head->next; // nullptr
dummy->next = nullptr;
delete dummy;
}
else{
prev->next = p->next;
p->next = nullptr;
delete p;
}
return;
}
prev = p;
p = p->next;
}
}
private:
const int N = 1001;
vector<MyListNode*> data;
};
方法4: 链地址法 有头节点
头节点一直存在, 省去了对头节点的判断, 但略占空间
struct MyListNode{
int key;
int val;
MyListNode* next;
MyListNode() : key(-1), val(-1), next(nullptr) {}
MyListNode(int _key, int _val) : key(_key), val(_val), next(nullptr) {}
};
class MyHashMap {
public:
/** Initialize your data structure here. */
MyHashMap() {
data.resize(N, new MyListNode());
}
auto getHashValue(int key){
return key % N;
}
/** value will always be non-negative. */
void put(int key, int value) {
auto hashkey = getHashValue(key);
auto& head = data[hashkey];
auto p = head;
auto tail = p;
// add value which has been added
while(p != nullptr){
if(p->key == key){
p->val = value;
return;
}
tail = p;
p = p->next;
}
// add new value
tail->next = new MyListNode(key, value);
}
/** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
int get(int key) {
auto hashkey = getHashValue(key);
auto& head = data[hashkey];
auto p = head;
while(p != nullptr){
if(p->key == key){
return p->val;
}
p = p->next;
}
return -1;
}
/** Removes the mapping of the specified value key if this map contains a mapping for the key */
void remove(int key) {
auto hashkey = getHashValue(key);
auto& head = data[hashkey];
auto p = head;
MyListNode* prev = nullptr;
while(p != nullptr){
if(p->key == key){
prev->next = p->next;
p->next = nullptr;
delete p;
return;
}
prev = p;
p = p->next;
}
}
private:
const int N = 1001;
vector<MyListNode*> data;
};
方法5: 开放地址法 线性探测
算法原理:
$$
H_i = (H(key) + d_i) \space MOD \space m \quad i=1, 2, \cdots, k(k<=m-1)
$$
class MyHashMap {
public:
/** Initialize your data structure here. */
MyHashMap() {
hashtable = vector<pair<int, int>>(N, {-1, -1});
}
auto getHashValue(int key){
int k = key % N;
while(hashtable[k].first != key && hashtable[k].first != -1){
k = (k + 1) % N;
}
return k;
}
/** value will always be non-negative. */
void put(int key, int value) {
auto k = getHashValue(key);
hashtable[k] = {key, value};
}
/** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
int get(int key) {
auto k = getHashValue(key);
if(hashtable[k].first == -1){
return -1;
}
return hashtable[k].second;
}
/** Removes the mapping of the specified value key if this map contains a mapping for the key */
void remove(int key) {
auto k = getHashValue(key);
if(hashtable[k].first != -1){
hashtable[k].first = -2;
}
}
private:
const static int N = 20011;
vector<pair<int, int>> hashtable;
};
