用鏈結法實作整數集合

題目敘述

社團要管理一份「已報名學號」的名單，需要能快速新增、刪除與查詢。請你用鏈結法（separate chaining）自己做一個整數集合：準備 M 個桶子，每個鍵依規則放進某一個桶，同一個桶裡的鍵用鏈結串列串起來。就算所有鍵都擠進同一個桶，答案依然正確，只是查起來比較慢；桶子數量只影響速度，不影響結果。

請提交 hashset.h 與 hashset.c，並實作以下介面：

typedef struct hashset hashset;

void hashset_init(hashset *s, int buckets); /* fixed bucket count for this test */
void hashset_insert(hashset *s, int key);
void hashset_erase(hashset *s, int key);
int hashset_contains(hashset *s, int key); /* 1 if present */
int hashset_size(hashset *s);
int hashset_empty(hashset *s);

桶的編號請用 ((key % M) + M) % M 計算，這樣負數的鍵也會落在 [0, M) 內。

輸入格式

評測用的 driver 會讀入下列內容並呼叫你的函式：

• 第 1 行：兩個整數 M 與 Q，分別是桶子數量與操作次數。
• 接下來 Q 行，每行是下列其中一種操作：insert x、erase x、contains x、size、empty。

輸出格式

insert 與 erase 不輸出。其餘每個操作各輸出一行：contains 在集合中有該鍵時輸出 1，否則輸出 0；size 輸出目前元素個數；empty 在集合為空時輸出 1，否則輸出 0。

限制

• 1 ≤ M ≤ 2 · 10⁵
• 1 ≤ Q ≤ 8 · 10⁵
• 鍵的範圍為 [−10⁹, 10⁹]

範例

範例 1

輸入

5 6
insert 3
insert 8
contains 3
contains 8
erase 3
contains 3

輸出

1
1
0

說明

M = 5 時，3 與 8 都落在桶 3（3 % 5 = 8 % 5 = 3），但鏈上仍分得出兩者：插入後兩次 contains 都是 1；erase 3 之後只剩 8，最後的 contains 3 為 0。

範例 2

輸入

3 4
insert -1
contains -1
contains 2
size

輸出

1
0
1

說明

鍵 −1 雖是負數，仍要對到合法桶號：M = 3 時 (((−1) % 3) + 3) % 3 = 2。contains 2 為 0，因為鍵 2 從沒被插入過，桶 2 裡放的是 −1。

範例 3

輸入

4 5
insert 7
insert 7
size
erase 100
empty

輸出

1
0

說明

同一個鍵插入兩次只算一個，所以 size 是 1。刪除不存在的 100 什麼事都不會發生，集合仍非空，empty 輸出 0。

範例 4

輸入

1 5
insert 10
insert 20
erase 10
size
empty

輸出

1
0

說明

M = 1 時所有鍵都在桶 0，這是鏈結法最極端的情形。刪掉 10 之後鏈上只剩 20，所以 size 為 1、empty 為 0。

範例 5

輸入

10007 3
insert 6679
contains 6679
size

輸出

1
1

說明

插入一個鍵後，contains 與 size 都是 1。

範例 6

輸入

10007 1
empty

輸出

1

說明

全新的集合是空的，所以 empty 輸出 1。

說明

• 對負數取 %，C 可能得到負的結果，直接當陣列索引會越界，所以要用上面的公式修正。
• 對已存在的鍵再 insert，或對不存在的鍵 erase，都不應改變集合，也不能改變 size。
• 測資包含所有鍵都落在同一個桶的情況，因此不能偷偷把每次操作寫成與 M 無關的 O(n) 掃描；仍然要依 key % M 分桶。
• 操作次數可達 8 · 10⁵，請用 scanf 之類的方式讀取，並讓每次操作的平均成本維持常數。