706. 设计哈希映射

题目描述

不使用任何内建的哈希表库设计一个哈希映射（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. 设计哈希集合那样简单地用位来表示某个键值是否存在，而是需要参考一下实现哈希函数的关键问题：

• 哈希函数：能够将集合中任意可能的元素映射到一个固定范围的整数值，并将该元素存储到整数值对应的地址上。
• 冲突处理：由于不同元素可能映射到相同的整数值，因此需要在整数值出现「冲突」时，需要进行冲突处理。总的来说，有以下几种策略解决冲突：
  • 链地址法：为每个哈希值维护一个链表，并将具有相同哈希值的元素都放入这一链表当中。
  • 开放地址法：当发现哈希值 hhh 处产生冲突时，根据某种策略，从 hhh 出发找到下一个不冲突的位置。例如，一种最简单的策略是，不断地检查 $h+1,h+2,h+3,\dots$ 这些整数对应的位置。
  • 再哈希法：当发现哈希冲突后，使用另一个哈希函数产生一个新的地址。
• 扩容：当哈希表元素过多时，冲突的概率将越来越大，而在哈希表中查询一个元素的效率也会越来越低。因此，需要开辟一块更大的空间，来缓解哈希表中发生的冲突。

这里我们选用链地址法。它本质上是一个二维数组。我们选取一个质数作为 base，这里可以是 769。那么一些操作：

• put：向对应的桶添加；
  • 因为之后要更新 key，我们需要 push 一个可写的 pair
• remove：从对应的桶中删除；
• get：从对应的桶中查找。

最终代码：

class MyHashMap:
 
    def __init__(self):
        self.bucket = [[] for _ in range(769)]
 
    def put(self, key: int, value: int) -> None:
        idx = key % 769
        for kv in self.bucket[idx]:
            if kv[0] == key:
                kv[1] = value
                return
        self.bucket[idx].append([key, value])
 
    def get(self, key: int) -> int:
        idx = key % 769
        for k, v in self.bucket[idx]:
            if k == key:
                return v
        return -1
 
    def remove(self, key: int) -> None:
        idx = key % 769
        for i, (k, _) in enumerate(self.bucket[idx]):
            if k == key:
                self.bucket[idx].pop(i)

想得太多