学生心理健康网站建设论文,php开源内容管理系统,做视频链接网站,网站制作呼和浩特题目#xff1a;
不使用任何内建的哈希表库设计一个哈希集合#xff08;HashSet#xff09;。
实现 MyHashSet 类#xff1a;
void add(key) 向哈希集合中插入值 key 。bool contains(key) 返回哈希集合中是否存在这个值 key 。void remove(key) 将给定值 key 从哈希集合…题目
不使用任何内建的哈希表库设计一个哈希集合HashSet。
实现 MyHashSet 类
void add(key) 向哈希集合中插入值 key 。bool contains(key) 返回哈希集合中是否存在这个值 key 。void remove(key) 将给定值 key 从哈希集合中删除。如果哈希集合中没有这个值什么也不做。
提示
0 key 10^6最多调用 104 次 add、remove 和 contains
思考
偷懒做法超大数组
因为 0 key 10^6所以可以建立一个长度为 10^6 1 的超大数组数组的索引代表key值数组的值True / False代表是否存在key值。代码如下
class MyHashSet(object):def __init__(self):self.hashset [False] * 1000001def add(self, key)::type key: int:rtype: Noneself.hashset[key] Truedef remove(self, key)::type key: int:rtype: Noneself.hashset[key] Falsedef contains(self, key)::type key: int:rtype: boolreturn self.hashset[key]
提交通过 正经做法哈希函数链地址法
设置一个长度为volume的数组hash由volume个空列表组成。哈希函数为indexkey%volume。那么对于任意值key用哈希函数计算得到key所在的列表的位置然后在列表中进行add、remove、contains操作。
由于 0 key 10^6所以取volume值为10^3代码如下
class MyHashSet(object):def __init__(self):self.volume 1000self.hashset [[] for _ in range(self.volume)]def _hash(self, key):return key % self.volume # 哈希函数def add(self, key)::type key: int:rtype: Noneindex self._hash(key)if key not in self.hashset[index]:self.hashset[index].append(key)def remove(self, key)::type key: int:rtype: Noneindex self._hash(key)if key in self.hashset[index]:self.hashset[index].remove(key)def contains(self, key)::type key: int:rtype: boolindex self._hash(key)if key in self.hashset[index]:return Truereturn False
提交通过
