題目:
Design a HashSet without using any built-in hash table libraries.
Implement MyHashSet class:
1.void add(key) Inserts the value key into the HashSet.
2.bool contains(key) Returns whether the value key exists in the HashSet or not.
3.void remove(key) Removes the value key in the HashSet. If key does not exist in the HashSet, do nothing.
原本的版本(Beats: 20.41% Memory: 21.6MB):
| class MyHashSet: def __init__(self): self.hash = [] def add(self, key: int) -> None: if key not in self.hash: self.hash.append(key) def remove(self, key: int) -> None: if key in self.hash: self.hash.remove(key) def contains(self, key: int) -> bool: if key in self.hash: return True else: return False |
用了 collection.defaultdict的版本(Beats: 86.88% Memory: 21.9MB):
| from collections import defaultdict class MyHashSet: def __init__(self): self.mp=defaultdict(int) def add(self, key: int) -> None: self.mp[key]=True def remove(self, key: int) -> None: self.mp[key]=False def contains(self, key: int) -> bool: return self.mp[key] |
後來查了一下defaultdict的用法，其實也是挺酷的，看來未來會很常用到它
這題真的不難，但需要知道甚麼要怎麼用
!!!!!!補充補充!!!!!!
感謝狗喵哥提醒，題目有明確表示不能用內建的hash
因此我第一個根本不是hash的定義
第二個是用內建的
hash的定義為:
感謝狗喵哥提醒，題目有明確表示不能用內建的hash
因此我第一個根本不是hash的定義
第二個是用內建的
hash的定義為:
1.唯一性：HashSet中不允許重複的元素。當嘗試將重複的元素加入HashSet時，將會被忽略。
2.快速查詢：由於HashSet使用了哈希表，查詢元素是否存在於HashSet中的操作非常高效。它通過計算元素的哈希碼，直接定位到對應的位置，而不需要逐個比較元素。
3. 無序性：HashSet中的元素沒有特定的順序，插入的順序不會被保留。
4. 可變性：HashSet的大小可以根據需要動態增長或縮小。
因此實際上要設計一個HashSet要根據上述條件:
| class MyHashSet: def __init__(self): self.size = 1000 self.hash = [[] for _ in range(self.size)] def __hash__(self, key:int) -> int: return key % self.size def add(self, key: int) -> None: index = self.__hash__(key) if key not in self.hash[index]: self.hash[index].append(key) def remove(self, key: int) -> None: index = self.__hash__(key) if key in self.hash[index]: self.hash[index].remove(key) def contains(self, key: int) -> bool: index = self.__hash__(key) return key in self.hash[index] |
