原題目網址:705. Design HashSet
題目描述
不用任何 built-in hash table libraries,自己設計一個 HashSet。
需要支援以下操作:
void add(key)
:插入 valuekey
到 HashSet 中bool contains(key)
:return 是否 HashSet 中包含 valuekey
void remove(key)
:把 valuekey
從 HashSet 中移除。如果key
不存在,就不做任何事情。
解題思路
這一題其實就是要自己刻一個 Hash Table。由於題目說最多會有 104 次操作( add
、 remove
跟 contains
)且 key 的範圍為 0 到 106 ,所以在設計這個 Hash Table 的時候我做了以下決定:
- Table size 應為接近 10000 的質數(Hash table 的長度最好是質數,詳情請參考資料結構書籍)(不過把 table size 寫死不是最好的做法,應該讓它動態增長)
- 使用 Chaining 處理 Overflow
- Hash function 使用 Division Method
以下為用 C 語言實作的程式碼:
#define TABLE_SIZE 10099
typedef struct _LinkedList {
int key;
struct _LinkedList *next;
} LinkedList;
typedef struct {
LinkedList *table[TABLE_SIZE];
} MyHashSet;
/** Initialize your data structure here. */
MyHashSet* myHashSetCreate() {
MyHashSet *hashSet = malloc(sizeof(MyHashSet));
for (int i = 0; i < TABLE_SIZE; i++) {
hashSet->table[i] = NULL;
}
return hashSet;
}
int _hash(int x) {
return x % TABLE_SIZE;
}
/** Returns true if this set contains the specified element */
bool myHashSetContains(MyHashSet* obj, int key) {
LinkedList *currentSlot = obj->table[_hash(key)];
while (currentSlot != NULL) {
if (currentSlot->key == key) {
return true;
}
currentSlot = currentSlot->next;
}
return false;
}
void myHashSetAdd(MyHashSet* obj, int key) {
LinkedList *firstSlot = obj->table[_hash(key)];
if (myHashSetContains(obj, key)) {
return;
}
LinkedList *newSlot = malloc(sizeof(LinkedList));
newSlot->key = key;
if (!firstSlot) {
newSlot->next = NULL;
} else {
newSlot->next = firstSlot;
}
obj->table[_hash(key)] = newSlot;
}
void myHashSetRemove(MyHashSet* obj, int key) {
LinkedList *currentSlot = obj->table[_hash(key)];
LinkedList *prevSlot = currentSlot;
while (currentSlot != NULL) {
if (currentSlot->key == key) {
// first slot
if (prevSlot == currentSlot) {
obj->table[_hash(key)] = currentSlot->next;
} else {
prevSlot->next = currentSlot->next;
}
free(currentSlot);
return;
}
prevSlot = currentSlot;
currentSlot = currentSlot->next;
}
}
void myHashSetFree(MyHashSet* obj) {
if (!obj) {
return;
}
for (int i = 0; i < TABLE_SIZE; i++) {
free(obj->table[i]);
}
free(obj);
}
/**
* Your MyHashSet struct will be instantiated and called as such:
* MyHashSet* obj = myHashSetCreate();
* myHashSetAdd(obj, key);
* myHashSetRemove(obj, key);
* bool param_3 = myHashSetContains(obj, key);
* myHashSetFree(obj);
*/