705. 设计哈希集合

题目描述

不使用任何内建的哈希表库设计一个哈希集合（HashSet）。

实现 MyHashSet 类：

• void add(key) 向哈希集合中插入值 key 。
• bool contains(key) 返回哈希集合中是否存在这个值 key 。
• void remove(key) 将给定值 key 从哈希集合中删除。如果哈希集合中没有这个值，什么也不做。

思路

哈希表最重要的是怎样处理冲突，这里 key 的上限是 $10^6$，很容易想到实现一个大数组或者利用位运算去处理，其他方式等待日后再整理吧，这里只实现简单的位运算版本：

class MyHashSet:
 
    def __init__(self):
        self.bucket = [0 for _ in range(40000)]
 
    def add(self, key: int) -> None:
        idx = key//32
        loc = key % 32
        self.bucket[idx] |= (1 << loc)
 
    def remove(self, key: int) -> None:
        idx = key//32
        loc = key % 32
        self.bucket[idx] &= ~(1 << loc)
 
    def contains(self, key: int) -> bool:
        idx = key//32
        loc = key % 32
        return (self.bucket[idx] >> loc) & 1 == 1

想得太多