What kind of data structures are suitable for Set ?

今天請假在家休息，複習了一下Foundations of Computer Science中關於Set的原理與實作。順手整理一下幾種常見的實作方式以及優缺點。

假設兩個Set的大小分別為m個元素與n個元素：

1. unsorted list：求union、intersection、difference的需要O(m*n)，效率不好，但在很多情況下，輸入就僅是unsorted list，沒得選。算法很直覺，可參考Foundations of Computer Science第五章。
2. sorted list：當m與n很接近時，先將list排序可大幅將Set的三種基本運算降至O(n*logn)。
3. characteristic vector(bitmap)：當元素範圍是在某個固定範圍，並且數量不會多到不易儲存時(bitmap需要初始化，所以數量必須事先確定，不然反覆copy至更大容量的空間會非常沒效率)，用bitmap可以將Set運算降到O(m+n)。
4. hash table：妥善設計的hash table，可以同時獲得bitmap的效能以及sorted list的彈性，但必須將hash function以及collision的處理設計的有效率，而這需要依據應用進行實驗。

除了用到的資料結構以外，作者還逐步擴展Set的概念，為relational model奠定基礎。