本篇推文共計2000個字，閱讀時間約3分鐘。

01

題目描述

題目描述：

不使用任何內(nèi)建的哈希表庫設(shè)計一個

哈希集合(HashSet)。

實(shí)現(xiàn) MyHashSet 類：
void add(key) 
向哈希集合中插入值 key 。

bool contains(key) 
返回哈希集合中是否存在這個值 key 。

void remove(key) 
將給定值 key 從哈希集合中刪除。
如果哈希集合中沒有這個值，什么也不做。

如下面的示例：

輸入：
["MyHashSet", "add", "add", "contains", "contains", "add", 
"contains", "remove", "contains"]
[[], [1], [2], [1], [3], [2], [2], [2], [2]]
輸出：
[null, null, null, true, false, null, true, null, false]

解釋：
MyHashSet myHashSet = new MyHashSet();
myHashSet.add(1); // set = [1]
myHashSet.add(2); // set = [1, 2]
myHashSet.contains(1); // 返回 True
myHashSet.contains(3); // 返回 False ，（未找到）
myHashSet.add(2); // set = [1, 2]
myHashSet.contains(2); // 返回 True
myHashSet.remove(2); // set = [1]
myHashSet.contains(2); // 返回 False ，（已移除）

提示：

1. 0 <= key <= 10^6

2. 最多調(diào)用10^4次add、remove 和 contains。

02

方法和思路

首先我們來科普一下哈希集合的概念。

哈希集合是指能O(1)時間內(nèi)進(jìn)行插入和刪除，可以保存不重復(fù)元素的一種數(shù)據(jù)結(jié)構(gòu)。

由于題目給出了0 <= key <= 10^6的數(shù)據(jù)范圍，

同時限定了key只能是int。

我們可以暴力求解，創(chuàng)建一個10^6 +1

長度大小的數(shù)組。

題目還強(qiáng)調(diào)

只需要關(guān)注輸入的 key 是否存在，

因此，我們把數(shù)組的元素統(tǒng)一設(shè)計成 bool 型的，
當(dāng)某個 key 的對應(yīng)的數(shù)組中的位置取值為 true，說明該 key 存在，
當(dāng)某個 key 的對應(yīng)的數(shù)組中的位置取值為 false，說明該 key 不存在。

Python提供了bool類型來表示真(對)或假(錯)

比如：
1.常見的10 > 3比較算式，這個是正確的，在程序里稱為真,即我們眼中的對，
Python 使用 True 來代表；

2.常見的1 > 10比較算式，這個是錯誤的，在程序世界里稱之為假，即我們眼中的錯，
Python 使用 False 來代表。

但是這種方法:

優(yōu)點(diǎn)：查找和刪除的性能非常快，只用訪問 1 次數(shù)組，即時間復(fù)雜度為O(1)；
缺點(diǎn)：使用了過大的空間，如果存儲的元素較少時，性價比較低，會占用較多緩存

我們用代碼表示此題的解法如下：

class MyHashSet:
    def __init__(self):
        self.boolnodes=[False]*1000001

    def add(self, key):
        self.boolnodes[key]=True

    def remove(self, key):
        self.boolnodes[key]=False

    def contains(self, key):
        return self.boolnodes[key]