解题思路
解法1
超大数组
预先开出max(key)的空间，确保每个key都有一个单独的索引
解法2
拉链数组
超大数组会占用的空间太大，可以将输入的数据分桶，每个桶的数据动态增长
分桶方法
推荐使用质数取余进行分桶
使用质数取余分桶的原因
只要输入的数据足够随机，是否用质数取模无所谓的；
但是实际输入的数据一般是有规律的，如果使用合数取余，当合数和数据存在非1的约数，
那数据只会被分桶到约数的倍数，违背了尽量使各个桶之间的元素数近似相等的原则。
参考：
https://www.zhihu.com/question/20806796/answer/21359160
https://blog.csdn.net/xp178171640/article/details/102929544
代码
解法1
1
2
3
4
5
6
7
8
9
10
11
12
13
| class MyHashMap:
def __init__(self):
self.hash_map = [-1 for _ in range(10**6 + 10)]
def put(self, key: int, value: int) -> None:
self.hash_map[key] = value
def get(self, key: int) -> int:
return self.hash_map[key]
def remove(self, key: int) -> None:
self.hash_map[key] = -1
|
解法2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| class MyHashMap:
def __init__(self):
self.bucket_size = 1009
self.hash_map = [[] for _ in range(self.bucket_size)]
def get_bucket_index(self, key):
return key % self.bucket_size
def put(self, key: int, value: int) -> None:
bucket_index = self.get_bucket_index(key)
for existed_map in self.hash_map[bucket_index]:
if existed_map[0] == key:
existed_map[1] = value
return
self.hash_map[bucket_index].append([key, value])
def get(self, key: int) -> int:
bucket_index = self.get_bucket_index(key)
for existed_key, existed_val in self.hash_map[bucket_index]:
if existed_key == key:
return existed_val
return -1
def remove(self, key: int) -> None:
bucket_index = self.get_bucket_index(key)
for index, existed_map in enumerate(self.hash_map[bucket_index]):
if existed_map[0] == key:
self.hash_map[bucket_index].pop(index)
return
|