太原市给企业做网站,wordpress头像被墙,一键安装网站运行环境,江山企业自适应网站建设首选题目#xff1a;
不使用任何内建的哈希表库设计一个哈希映射#xff08;HashMap#xff09;。
实现 MyHashMap 类#xff1a;
MyHashMap() 用空映射初始化对象void put(int key, int value) 向 HashMap 插入一个键值对 (key, value) 。如果 key 已经存在于映射中#x…题目
不使用任何内建的哈希表库设计一个哈希映射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 。
提示
0 key, value 106最多调用 104 次 put、get 和 remove 方法
思考
超大数组
第一眼这题不是跟昨天的705题差不多吗......然后用超大数组的写法写了也通过了
class MyHashMap(object):def __init__(self):self.hash [-1] * 1000001def put(self, key, value)::type key: int:type value: int:rtype: Noneself.hash[key] valuedef get(self, key)::type key: int:rtype: intreturn self.hash[key]def remove(self, key)::type key: int:rtype: Noneself.hash[key] -1
提交通过 那么用正经哈希函数写呢
哈希函数链地址法定长数组
即用二维数组的索引代表key值数值代表value值。设置行数volume为1000同时也是哈希函数中的除数。哈希函数即
1. addresskey所在的行 key % volume可见address的范围为[0, 999]。
2. address_ key所在的列 key // self.volume可见address_的范围为[0, 1000]。所以设置数组的列数为1001。
代码如下
class MyHashMap(object):def __init__(self):# key的范围[0, 1000000]self.volume 1000 # 1000行代表除数为1000也代表余数从0到999self.hashmap [[-1]*1001 for _ in range(self.volume)]# 1001列代表整除商从0到1000def _hash(self, key):address key % self.volume # 第一层位置行address_ key // self.volume # 第二层位置列return address, address_def put(self, key, value)::type key: int:type value: int:rtype: Noneaddress, address_ self._hash(key)self.hashmap[address][address_] valuedef get(self, key)::type key: int:rtype: intaddress, address_ self._hash(key)return self.hashmap[address][address_]def remove(self, key)::type key: int:rtype: Noneaddress, address_ self._hash(key)self.hashmap[address][address_] -1
提交通过 【最优】哈希函数链地址法变长列表 思路跟昨天的题一模一样只不过向列表中插入的不再是key值而是[key, value]小数组。代码如下
class MyHashMap(object):def __init__(self):self.volume 1000self.hashset [[] for _ in range(self.volume)]def _hash(self, key):return key % self.volume # 哈希函数def put(self, key, value)::type key: int:type value: int:rtype: Noneindex self._hash(key)for item in self.hashset[index]:if item[0] key: # 如果key已经存在于映射中则更新其对应的值 valueitem[1] valuereturnself.hashset[index].append([key, value]) # 若key还不存在则插入[key, value]def get(self, key)::type key: int:rtype: intindex self._hash(key)for item in self.hashset[index]:if item[0] key:return item[1]return -1 def remove(self, key)::type key: int:rtype: Noneindex self._hash(key)for i, item in enumerate(self.hashset[index]):if item[0] key: del self.hashset[index][i]
提交通过
