OOD - Design HashSet

info

HashSet 是指能 O(1) 时间内进行插入和删除，可以保存不重复元素的一种数据结构。

HashSet 是在 时间和空间 上做权衡的经典例子: 如果不考虑空间，我们可以直接设计一个超大的数组，使每个 key 都有单独的位置，则不存在冲突；如果不考虑时间，我们可以直接用一个无序的数组保存输入，每次查找的时候遍历一次数组。

为了时间和空间上的平衡，HashSet 基于数组实现，并通过 hash 方法求键 key 在数组中的位置，当 hash 后的位置存在冲突的时候，再解决冲突。

Leetcode 例题 705

设计 Hash 函数需要考虑两个问题:

• 通过 hash 方法把键 key 转成数组的索引: 设计合适的 hash 函数，一般都是对分桶数取模 %
• 处理碰撞冲突问题: 拉链法和线性探测法。

Constraints and assumptions

• For simplicity, are the keys integers only? Yes
• For collision resolution, can we use chaining? Yes
• Do we have to worry about load factors? No
• Can we assume inputs are valid or do we have to validate them? Assume they're valid
• Can we assume this fits memory? Yes

Solution

class MyHashSet:

    def __init__(self):
        self.buckets = 1009
        self.table = [[] * self.buckets for _ in range(self.buckets)]

    def hash(self, key: int) -> int:
        return key % self.buckets

    def add(self, key: int) -> None:
        hashkey = self.hash(key)
        if key in self.table[hashkey]:
            return
        self.table[hashkey].append(key)

    def remove(self, key: int) -> None:
        hashkey = self.hash(key)
        if key not in self.table[hashkey]:
            return
        self.table[hashkey].remove(key)


    def contains(self, key: int) -> bool:
        hashkey = self.hash(key)
        if key in self.table[hashkey]:
            return True
        return False


# Your MyHashSet object will be instantiated and called as such:
# obj = MyHashSet()
# obj.add(key)
# obj.remove(key)
# param_3 = obj.contains(key)