705.Design HashSet === ###### tags: `Easy`,`Design`,`Array`,`Hash Table`,`Linked List` [705. Design HashSet](https://leetcode.com/problems/design-hashset/) ### 題目描述 Design a HashSet without using any built-in hash table libraries. Implement `MyHashSet` class: * `void add(key)` Inserts the value `key` into the HashSet. * `bool contains(key)` Returns whether the value `key` exists in the HashSet or not. * `void remove(key)` Removes the value `key` in the HashSet. If `key` does not exist in the HashSet, do nothing. ### 範例 **Example 1:** ``` Input ["MyHashSet", "add", "add", "contains", "contains", "add", "contains", "remove", "contains"] [[], [1], [2], [1], [3], [2], [2], [2], [2]] Output [null, null, null, true, false, null, true, null, false] Explanation MyHashSet myHashSet = new MyHashSet(); myHashSet.add(1); // set = [1] myHashSet.add(2); // set = [1, 2] myHashSet.contains(1); // return True myHashSet.contains(3); // return False, (not found) myHashSet.add(2); // set = [1, 2] myHashSet.contains(2); // return True myHashSet.remove(2); // set = [1] myHashSet.contains(2); // return False, (already removed) ``` **Constraints**: * 0 <= `key` <= 10^6^ * At most 10^4^ calls will be made to `add`, `remove`, and `contains`. ### 解答 #### C# ```csharp= public class MyHashSet { const int Size = 1 << 10; const int Mask = Size - 1; List<int>[] set = new List<int>[Size]; public MyHashSet() { } private List<int> this[int key] => set[key & Mask] ??= new List<int>(); public void Add(int key) { var slot = this[key]; if (!slot.Contains(key)) { slot.Add(key); } } public void Remove(int key) { var slot = this[key]; if (slot.Contains(key)) { slot.Remove(key); } } public bool Contains(int key) => this[key].Contains(key); } ``` >[name=Jim][time=May 30, 2023] #### Python ```python= class MyHashSet: def __init__(self): self.hashset = set() def add(self, key: int) -> None: self.hashset.add(key) def remove(self, key: int) -> None: if self.contains(key): self.hashset.remove(key) def contains(self, key: int) -> bool: return key in self.hashset ``` > [name=Ron Chen][time=Tue, May 30, 2023] ### Reference [回到題目列表](https://hackmd.io/@Marsgoat/leetcode_every_day)