LeetCode 706. 设计哈希映射（数组法，稀疏矩阵法，链地址法，开放定址法）

本文主要是介绍LeetCode 706. 设计哈希映射（数组法，稀疏矩阵法，链地址法，开放定址法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

思路：

参考：https://leetcode-cn.com/problems/design-hashmap/solution/706-she-ji-ha-xi-ying-she-by-jyj407-nzcz/

解法1：
因为数据不大，直接用数组保存每个值的映射。

class MyHashMap {
private:vector<int>cache;
public:/** Initialize your data structure here. */MyHashMap() {cache.resize(1000005,-1);}/** value will always be non-negative. */void put(int key, int value) {cache[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 cache[key];}/** Removes the mapping of the specified value key if this map contains a mapping for the key */void remove(int key) {cache[key] = -1;}
};

解法2：
二维稀疏矩阵，节省空间

class MyHashMap {
private:vector<vector<int>>data;int N = 1001;
public:/** Initialize your data structure here. */MyHashMap() {data.resize(N);}int getHashKey1(int x) {return x / N;}int getHashKey2(int x) {return x % N;}/** value will always be non-negative. */void put(int key, int value) {int hashKey1 = getHashKey1(key);int hashKey2 = getHashKey2(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) {int hashKey1 = getHashKey1(key);int hashKey2 = getHashKey2(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) {int hashKey1 = getHashKey1(key);int hashKey2 = getHashKey2(key);if(data[hashKey1].size()) data[hashKey1][hashKey2] = -1;}
};

解法3：
构建哈希表，拉链法解决哈希冲突

struct MyListNode {int key,val;MyListNode* next;MyListNode(): key(-1),val(-1),next(nullptr){}MyListNode(int _key,int _val):key(_key),val(_val),next(nullptr){}
};
class MyHashMap {
private:vector<MyListNode*>data;int N = 1009;
public:MyHashMap() {data.resize(N,new MyListNode());}int getHashKey(int key) {return key % N;}void put(int key, int value) {int hashKey = getHashKey(key);MyListNode *head = data[hashKey];MyListNode *p = head;MyListNode *tail = p;while(p != nullptr) {if(p -> key == key) {p -> val = value;return;}tail = p;p = p -> next;}tail -> next = new MyListNode(key,value);}int get(int key) {int hashKey = getHashKey(key);MyListNode* head = data[hashKey];MyListNode* p = head;while(p != nullptr) {if(p -> key == key) {return p -> val;}p = p -> next;}return -1;}void remove(int key) {int hashKey = getHashKey(key);MyListNode* head = data[hashKey];MyListNode* prev = head;MyListNode* p = head -> next;while(p != nullptr) {if(p -> key == key) {prev -> next = p -> next;p -> next = nullptr;delete(p);return;}prev = p;p = p -> next;}}
};

解法4：
STL实现的双向链表，使用双向链表的原因是在已知迭代器（指针）的情况下可以做到O(1)删除。

class MyHashMap {
private:vector<list<pair<int,int>>>data;int N = 1009;
public:MyHashMap() {data.resize(N);}int getHashKey(int key) {return key % N;}list<pair<int,int>>::iterator find(int key) {int hashKey = getHashKey(key);auto& it = data[hashKey];for(auto iter = it.begin();iter != it.end();iter++) {if(iter -> first == key) {return iter;}}return it.end();}void put(int key, int value) {int hashKey = getHashKey(key);auto iter = find(key);if(iter != data[hashKey].end()) {iter -> second = value;return;}data[hashKey].push_back({key,value});}   int get(int key) {int hashKey = getHashKey(key);auto iter = find(key);if(iter != data[hashKey].end()) {return iter -> second;}return -1;}void remove(int key) {int hashKey = getHashKey(key);auto iter = find(key);if(iter != data[hashKey].end()) {data[hashKey].erase(iter);}}
};

解法5：
C++实现的双向链表

struct MyListNode {int key,val;MyListNode* next;MyListNode* prev;MyListNode():key(-1),val(-1),next(nullptr),prev(nullptr){}MyListNode(int _key,int _val):key(_key),val(_val),next(nullptr),prev(nullptr){}
};
class MyHashMap {
private:vector<MyListNode*>data;int N = 1009;
public:MyHashMap() {data.resize(N,new MyListNode());}int getHashKey(int key) {return key % N;}MyListNode* find(int key) {int hashKey = getHashKey(key);MyListNode* head = data[hashKey];while(head != nullptr) {if(head -> key == key) return head;head = head -> next;}return nullptr;}void del(MyListNode* p) {p -> prev -> next = p -> next;if(p -> next) p -> next -> prev = p -> prev;p -> next = p -> prev = nullptr;delete(p);}void put(int key, int value) {int hashKey = getHashKey(key);MyListNode* p = find(key);MyListNode* head = data[hashKey];if(p != nullptr) {p -> val = value;return;}MyListNode* newNode = new MyListNode(key,value);newNode -> next = head -> next;if(head -> next != nullptr) {head -> next -> prev = newNode;}head -> next = newNode;newNode -> prev = head;}int get(int key) {int hashKey = getHashKey(key);MyListNode* iter = find(key);if(iter != nullptr) {return iter -> val;}return -1;}void remove(int key) {int hashKey = getHashKey(key);  MyListNode* iter = find(key);if(iter != nullptr) {del(iter);}}
};

解法6：
开放定址，线性探测

class MyHashMap {
private:const static int N = 20005;vector<pair<int,int>>hashTable;
public:MyHashMap() {hashTable.resize(N,{-1,-1});}int getHashKey(int key) {int k = key % N;while(hashTable[k].first != key && hashTable[k].first != -1) {k = (k + 1) % N;}return k;}void put(int key, int value) {int k = getHashKey(key);hashTable[k] = {key,value};}int get(int key) {int k = getHashKey(key);return hashTable[k].second;}void remove(int key) {int k = getHashKey(key);if(hashTable[k].first != -1) {hashTable[k].first = -2;}}
};

这篇关于LeetCode 706. 设计哈希映射（数组法，稀疏矩阵法，链地址法，开放定址法）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---