题目：

不使用任何内建的哈希表库设计一个哈希集合（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] * 1000001


    def add(self, key):
        """
        :type key: int
        :rtype: None
        """
        self.hashset[key] = True


    def remove(self, key):
        """
        :type key: int
        :rtype: None
        """
        self.hashset[key] = False


    def contains(self, key):
        """
        :type key: int
        :rtype: bool
        """
        return self.hashset[key]

提交通过：

 

正经做法：哈希函数+链地址法

设置一个长度为volume的数组hash，由volume个空列表组成。哈希函数为index=key%volume。那么对于任意值key，用哈希函数计算得到key所在的列表的位置，然后在列表中进行add、remove、contains操作。

由于 0<= key <= 10^6，所以取volume值为10^3，代码如下：

class MyHashSet(object):

    def __init__(self):
        self.volume = 1000
        self.hashset = [[] for _ in range(self.volume)]


    def _hash(self, key):
        return key % self.volume    # 哈希函数


    def add(self, key):
        """
        :type key: int
        :rtype: None
        """
        index = self._hash(key)
        if key not in self.hashset[index]:
            self.hashset[index].append(key)


    def remove(self, key):
        """
        :type key: int
        :rtype: None
        """
        index = self._hash(key)
        if key in self.hashset[index]:
            self.hashset[index].remove(key)


    def contains(self, key):
        """
        :type key: int
        :rtype: bool
        """
        index = self._hash(key)
        if key in self.hashset[index]:
            return True
        return False

提交通过：