leetcode链表之设计哈希集合
2022-04-01 本文已影响0人
小奚有话说
705、设计哈希集合
题目:
不使用任何内建的哈希表库设计一个哈希集合(HashSet)。
实现 MyHashSet 类:
- void add(key) 向哈希集合中插入值 key 。
- bool contains(key) 返回哈希集合中是否存在这个值 key 。
- void remove(key) 将给定值 key 从哈希集合中删除。如果哈希集合中没有这个值,什么也不做。
思路:
使用拉链数组的方式
class MyHashSet:
# 通过base计算hash值,需要开辟其大小的数组,数字越大,消耗的空间越多,数字越小,哈希碰撞的可能性越到
# 一般采取质数
__base = 769
def __init__(self):
# 开辟空间
self._data = [[] for _ in range(self.__base)]
def hash(self, key):
return key % self.__base
def add(self, key: int) -> None:
h = self.hash(key)
# 当key已存在时直接返回,不存在向数组后面添加
if key in self._data[h]:
return
self._data[h].append(key)
def remove(self, key: int) -> None:
h = self.hash(key)
# 先判断数组是否存在,存在则删除
if key not in self._data[h]:
return
self._data[h].remove(key)
def contains(self, key: int) -> bool:
h = self.hash(key)
return key in self._data[h]
706、设计哈希映射
题目:
不使用任何内建的哈希表库设计一个哈希映射(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 。
思路:
和设计哈希集合一样,使用拉链数组的方式实现。
class MyHashMap:
__base = 769
def __init__(self):
# 数组内部存储以[key,value]存储数据
self._data = [[] for _ in range(self.__base)]
def hash(self, key):
return key % self.__base
def put(self, key: int, value: int) -> None:
h = self.hash(key)
for item in self._data[h]:
# 当出现重复添加的情况,更新value值
if item[0] == key:
item[1] = value
return
self._data[h].append([key, value])
def get(self, key: int) -> int:
h = self.hash(key)
for item in self._data[h]:
if item[0] == key:
return item[1]
return -1
def remove(self, key: int) -> None:
h = self.hash(key)
index = -1
# 先找到对应key的下标进行删除
for i, item in enumerate(self._data[h]):
if item[0] == key:
index = i
break
if index < 0: return
self._data[h].pop(index)