706. 设计哈希映射
706. 设计哈希映射
🟢 🔖 设计
数组
哈希表
链表
哈希函数
🔗 力扣
LeetCode
题目
Design a HashMap without using any built-in hash table libraries.
Implement the MyHashMap
class:
MyHashMap()
initializes the object with an empty map.void put(int key, int value)
inserts a(key, value)
pair into the HashMap. If thekey
already exists in the map, update the correspondingvalue
.int get(int key)
returns thevalue
to which the specifiedkey
is mapped, or-1
if this map contains no mapping for thekey
.void remove(key)
removes thekey
and its correspondingvalue
if the map contains the mapping for thekey
.
Example 1:
Input
["MyHashMap", "put", "put", "get", "get", "put", "get", "remove", "get"]
[[], [1, 1], [2, 2], [1], [3], [2, 1], [2], [2], [2]]
Output
[null, null, null, 1, -1, null, 1, null, -1]
Explanation
MyHashMap myHashMap = new MyHashMap();
myHashMap.put(1, 1); // The map is now [[1,1]]
myHashMap.put(2, 2); // The map is now [[1,1], [2,2]]
myHashMap.get(1); // return 1, The map is now [[1,1], [2,2]]
myHashMap.get(3); // return -1 (i.e., not found), The map is now [[1,1], [2,2]]
myHashMap.put(2, 1); // The map is now [[1,1], [2,1]] (i.e., update the existing value)
myHashMap.get(2); // return 1, The map is now [[1,1], [2,1]]
myHashMap.remove(2); // remove the mapping for 2, The map is now [[1,1]]
myHashMap.get(2); // return -1 (i.e., not found), The map is now [[1,1]]
Constraints:
0 <= key, value <= 10^6
- At most
104
calls will be made toput
,get
, andremove
.
题目大意
不使用任何内建的哈希表库设计一个哈希映射(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
。
解题思路
本题与 第 705 题 解法接近,唯一的区别在于存储的不是 key
本身,而是 (key,value)
对,其他代码都一样。
链地址法:
- 设哈希表的大小为
base
,则可以设计一个简单的哈希函数:hash(x) = x mod base
; - 开辟一个大小为
base
的数组,数组的每个位置是一个链表。当计算出哈希值之后,就插入到对应位置的链表当中; - 由于使用整数除法作为哈希函数,为了尽可能避免冲突,应当将
base
取为一个质数,如base = 769
;
复杂度分析
- 时间复杂度:
O(n / b)
。其中n
为哈希表中的元素数量,b
为链表的数量,假设哈希值是均匀分布的,则每个链表大概长度为n / b
; - 空间复杂度:
O(n+b)
。
代码
class MyHashMap {
constructor() {
this.base = 769;
this.data = new Array(this.base).fill(0).map(() => new Array());
}
// @param {number} key
// @return {number}
hash(key) {
return key % this.base;
}
// @param {number} key
// @param {number} value
// @return {void}
put(key, value) {
const h = this.hash(key);
for (let item of this.data[h]) {
if (item[0] === key) {
item[1] = value;
return;
}
}
this.data[h].push([key, value]);
}
// @param {number} key
// @return {number}
get(key) {
const h = this.hash(key);
for (let item of this.data[h]) {
if (item[0] === key) return item[1];
}
return -1;
}
// @param {number} key
// @return {void}
remove(key) {
const h = this.hash(key);
const hList = this.data[h];
for (let i = 0; i < hList.length; i++) {
if (hList[i][0] === key) {
hList.splice(i, 1);
return;
}
}
}
}
/**
* Your MyHashMap object will be instantiated and called as such:
* var obj = new MyHashMap()
* obj.put(key,value)
* var param_2 = obj.get(key)
* obj.remove(key)
*/
相关题目
题号 | 标题 | 题解 | 标签 | 难度 |
---|---|---|---|---|
705 | 设计哈希集合 | [✓] | 设计 数组 哈希表 2+ | |
1206 | 设计跳表 | 设计 链表 |