0706. 设计哈希映射

0706. 设计哈希映射 #

  • 标签:哈希表
  • 难度:简单

题目大意 #

要求不使用任何内建的哈希表库设计一个哈希映射(HashMap)。

满足以下操作:

  • 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 。

解题思路 #

0705. 设计哈希集合 类似。同样利用「数组+链表」的方式实现哈希集合,只不过之前的存储元素变为了 key:value。

定义一个一维长度为 buckets 的二维数组 table。第一维度用于计算哈希函数,为 key 分桶。第二个维度用于寻找 key 存放的具体位置。第二维度的数组会根据 key 值动态增长,模拟真正的链表。

代码 #

 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
31
32
33
34
class MyHashMap:

    def __init__(self):
        self.buckets = 1003
        self.table = [[] for _ in range(self.buckets)]


    def hash(self, key):
        return key % self.buckets


    def put(self, key: int, value: int) -> None:
        hash_key = self.hash(key)
        for item in self.table[hash_key]:
            if key == item[0]:
                item[1] = value
                return
        self.table[hash_key].append([key, value])


    def get(self, key: int) -> int:
        hash_key = self.hash(key)
        for item in self.table[hash_key]:
            if key == item[0]:
                return item[1]
        return -1


    def remove(self, key: int) -> None:
        hash_key = self.hash(key)
        for i, item in enumerate(self.table[hash_key]):
            if key == item[0]:
                self.table[hash_key].pop(i)
                return
本站总访问量  次  |  您是本站第  位访问者