当前位置：首页 > article >正文

Leetcode 706. 设计哈希映射

article 2024/11/16 7:30:09

1.题目基本信息

1.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 。

1.2.题目地址

https://leetcode.cn/problems/design-hashmap/description

2.解题方法

2.1.解题思路

链地址法

2.2.解题步骤

第一步，定义哈希函数的取余的基数和存储数组表data。

第二步，定义哈希函数，本题采用的最简单的除余函数。

第三步，定义插入函数，首先求key的哈希值h，并找到data中h位置的链表，如果key已经在该链表中，则将value进行更新，否则将key、value加入到该链表中。

第四步，定义查找函数，首先求key的哈希值h，并找到data中h位置的链表，如果key已经在该链表中，则返回对应的值，如果不存在，则返回-1。

第五步，定义删除函数，首先求key的哈希值h，并找到data中h位置的链表，如果key已经在该链表中，则删除对应项并返回。

3.解题代码

Python代码

# 链地址法
# 第一步，定义哈希函数的取余的基数和存储数组表data。第二步，定义哈希函数，本题采用的最简单的除余函数。第三步，定义插入函数，首先求key的哈希值h，并找到data中h位置的链表，如果key已经在该链表中，则将value进行更新，否则将key、value加入到该链表中。第四步，定义查找函数，首先求key的哈希值h，并找到data中h位置的链表，如果key已经在该链表中，则返回对应的值，如果不存在，则返回-1。第五步，定义删除函数，首先求key的哈希值h，并找到data中h位置的链表，如果key已经在该链表中，则删除对应项并返回。
class MyHashMap:
    def __init__(self):
        self.base=999
        self.data=[[] for _ in range(self.base)]
    
    def hash(self,key:int):
        return key%self.base

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

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

    def remove(self, key: int) -> None:
        hashVal=self.hash(key)
        for index,item in enumerate(self.data[hashVal]):
            if item[0]==key:
                self.data[hashVal].pop(index)
                return