706 设计哈希映射

爱被打了一巴掌 2022-09-05 04:07 157阅读 0赞

**1. 问题描述：**

不使用任何内建的哈希表库设计一个哈希映射（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 。

**示例：**

输入：  
\["MyHashMap", "put", "put", "get", "get", "put", "get", "remove", "get"\]  
\[\[\], \[1, 1\], \[2, 2\], \[1\], \[3\], \[2, 1\], \[2\], \[2\], \[2\]\]  
输出：  
\[null, null, null, 1, -1, null, 1, null, -1\]

**解释：**

MyHashMap myHashMap = new MyHashMap();  
myHashMap.put(1, 1); // myHashMap 现在为 \[\[1,1\]\]  
myHashMap.put(2, 2); // myHashMap 现在为 \[\[1,1\], \[2,2\]\]  
myHashMap.get(1); // 返回 1 ，myHashMap 现在为 \[\[1,1\], \[2,2\]\]  
myHashMap.get(3); // 返回 -1（未找到），myHashMap 现在为 \[\[1,1\], \[2,2\]\]  
myHashMap.put(2, 1); // myHashMap 现在为 \[\[1,1\], \[2,1\]\]（更新已有的值）  
myHashMap.get(2); // 返回 1 ，myHashMap 现在为 \[\[1,1\], \[2,1\]\]  
myHashMap.remove(2); // 删除键为 2 的数据，myHashMap 现在为 \[\[1,1\]\]  
myHashMap.get(2); // 返回 -1（未找到），myHashMap 现在为 \[\[1,1\]\]

**提示：**

0 <= key, value <= 10 ^ 6  
最多调用 10 ^ 4 次 put、get 和 remove 方法  
进阶：你能否不使用内置的 HashMap 库解决此问题？  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/design-hashmap

**2. 思路分析：**

这道题目与力扣的[705][]题是类似的，我们只需要修改一下705题的代码即可解决，705题的二维列表中的第二维元素为int类型，因为这里需要插入的是键值对所以第二维的元素为包含键值对的列表类型，然后修改一下查询与删除键值对的方法即可。

**3. 代码如下：**

class MyHashMap:
        n = 0
        hash = None
    
        def __init__(self):
            # n为质数
            self.n = 19997
            self.hash = [list() for i in range(self.n)]
    
        def put(self, key: int, value: int) -> None:
            # 计算当前的键应该落入哪一个桶
            _key = key % self.n
            hash = self.hash
            # 对于当前的key查找哈希表中是否存在这样的键, hash[_key]表示当前的key对应的桶的编号, 每一个桶是一个包含键值对的二维列表
            for i in range(len(hash[_key])):
                # 0表示键, 1表示值, 存在当前的键值对则修改
                if hash[_key][i][0] == key:
                    hash[_key][i][1] = value
                    return
            # 不存在当前的键值对那么往当前的桶插入键值对
            hash[_key].append([key, value])
    
        def get(self, key: int) -> int:
            _key = key % self.n
            hash = self.hash
            for k, v in hash[_key]:
                if k == key: return v
            return -1
    
        def remove(self, key: int) -> None:
            _key = key % self.n
            hash = self.hash
            # 这里枚举下标是为了删除元素的时候比较方便删除列表中的键值对
            for i in range(len(hash[_key])):
                if hash[_key][i][0] == key:
                    hash[_key].pop(i)
                    return

[705]: https://blog.csdn.net/qq_39445165/article/details/119727475