[LeetCode 解題筆記] Design HashSet

原題目網址：705. Design HashSet

題目描述

不用任何 built-in hash table libraries，自己設計一個 HashSet。

需要支援以下操作：

1. void add(key) ：插入 value key 到 HashSet 中
2. bool contains(key) ：return 是否 HashSet 中包含 value key
3. void remove(key) ：把 value key 從 HashSet 中移除。如果 key 不存在，就不做任何事情。

解題思路

這一題其實就是要自己刻一個 Hash Table。由於題目說最多會有 10⁴ 次操作（ add 、 remove 跟 contains ）且 key 的範圍為 0 到 10⁶ ，所以在設計這個 Hash Table 的時候我做了以下決定：

1. Table size 應為接近 10000 的質數（Hash table 的長度最好是質數，詳情請參考資料結構書籍）（不過把 table size 寫死不是最好的做法，應該讓它動態增長）
2. 使用 Chaining 處理 Overflow
3. 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);
*/