[leetcode] 706. Design HashMap

[leetcode] 706. Design HashMap

Description

Design a HashMap without using any built-in hash table libraries.

To be specific, your design should include these functions:

put(key, value) : Insert a (key, value) pair into the HashMap. If the value already exists in the HashMap, update the value.get(key): Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key.remove(key) : Remove the mapping for the value key if this map contains the mapping for the key.

Example:

MyHashMap hashMap = new MyHashMap();hashMap.put(1, 1); hashMap.put(2, 2); hashMap.get(1); // returns 1hashMap.get(3); // returns -1 (not found)hashMap.put(2, 1); // update the existing valuehashMap.get(2); // returns 1 hashMap.remove(2); // remove the mapping for 2hashMap.get(2); // returns -1 (not found)

Note:

All keys and values will be in the range of [0, 1000000].The number of operations will be in the range of [1, 10000].Please do not use the built-in HashMap library.

分析

题目的意思是：实现散列表法。这道题我参考了一下别人的python实现，首先设置一个质数prime，作为哈希的取模的数，hash数组存放取模后的键值对。put的时候做哈希，存放数据；get的时候也是做哈希，取值；remove的时候，先根据key找到目标键值对，最后删除该键值对就行了。

代码

class MyHashMap: def __init__(self): """ Initialize your data structure here. """ self.prime=20011 self.hash=[[] for _ in range(self.prime)] def put(self, key: int, value: int) -> None: """ value will always be non-negative. """ t=key%self.prime for item in self.hash[t]: if(item[0]==key): item[1]=value return self.hash[t].append([key,value]) def get(self, key: int) -> int: """ Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key """ t=key%self.prime for item in self.hash[t]: if(item[0]==key): return item[1] return -1 def remove(self, key: int) -> None: """ Removes the mapping of the specified value key if this map contains a mapping for the key """ t=key%self.prime delete=[] for item in self.hash[t]: if(item[0]==key): delete=item if(delete): self.hash[t].remove(delete) # Your MyHashMap object will be instantiated and called as such:# obj = MyHashMap()# obj.put(key,value)# param_2 = obj.get(key)# obj.remove(key)

参考文献

​​Python3 详细题解，拉链法实现！​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。