1.8　集合：差之毫厘，“慢”之千里

下面來看另一個(gè)數(shù)據(jù)結(jié)構(gòu)：集合。集合中包含的元素不能重復(fù)。

集合有多種類型，但本節(jié)只討論基于數(shù)組的集合。這種集合和數(shù)組很相似，它們都是存儲(chǔ)值的簡(jiǎn)單列表，二者的唯一區(qū)別在于，不能往集合中插入重復(fù)的值。

假設(shè)已知集合["a", "b", "c"]，而你想再添加一個(gè)"b"。因?yàn)?code>"b"已經(jīng)存在于集合中，所以計(jì)算機(jī)會(huì)拒絕這次操作。

當(dāng)需要確保數(shù)據(jù)不重復(fù)時(shí)，集合非常有用。

比如你要做一個(gè)在線電話簿，你肯定不希望看到重復(fù)的電話號(hào)碼。其實(shí)我這里的電話簿就有這種問題：除了我家以外，我家的電話號(hào)碼還被記成了Zirkind家的號(hào)碼。（這是真事。）我跟你說——我真的很討厭接到找Zirkind的電話或是語音留言。我敢說Zirkind家肯定也很奇怪為什么沒人給他們打電話。我給Zirkind家打電話告知此事時(shí)，打成了自家電話，結(jié)果接電話的是我妻子。（好吧，這段是編的。）要是那個(gè)電話簿程序使用的是集合該多好……

無論如何，基于數(shù)組的集合就是不允許有重復(fù)元素的數(shù)組。雖然這一點(diǎn)很有用，但這簡(jiǎn)單的限制會(huì)影響集合的某種主要操作的效率。

下面來分析讀取、查找、插入以及刪除在基于數(shù)組的集合上的效率。

集合的讀取和數(shù)組的讀取完全一致，即計(jì)算機(jī)檢查特定索引處的值只需要1步。這是因?yàn)橛?jì)算機(jī)能跳轉(zhuǎn)到集合內(nèi)的任意索引，而這只需簡(jiǎn)單地計(jì)算并跳轉(zhuǎn)到其內(nèi)存地址即可。

集合的查找也和數(shù)組的查找沒什么區(qū)別，即查找集合中的值最多需要N步。集合和數(shù)組的刪除操作也一模一樣，即要?jiǎng)h除一個(gè)值并移動(dòng)其他數(shù)據(jù)來填空最多需要N步。

集合的插入和數(shù)組的插入則不同。先來看看在集合末尾插入值。這對(duì)數(shù)組來說只需要1步，是最好的情況。

但集合不同，計(jì)算機(jī)需要先判斷這個(gè)值是否存在于集合中——因?yàn)榧系囊?guī)則是不允許插入重復(fù)數(shù)據(jù)。

計(jì)算機(jī)要如何確保新數(shù)據(jù)不在集合中呢？記住，計(jì)算機(jī)一開始并不知道數(shù)組或者集合的格子中存儲(chǔ)了什么值。因此，它必須先在集合中查找，才能知道要插入的值是否已經(jīng)存在。只有集合中不存在這個(gè)新值的時(shí)候，計(jì)算機(jī)才能繼續(xù)執(zhí)行插入操作。

所以，所有的插入操作都需要先進(jìn)行查找。

來看一個(gè)例子。假設(shè)之前提到的購(gòu)物清單是用集合存儲(chǔ)的。這個(gè)假設(shè)很合理，因?yàn)槲覀儾幌胫貜?fù)購(gòu)物。假設(shè)集合目前是["apples", "bananas", "cucumbers", "dates", "elderberries"]，而我們想插入"figs"。計(jì)算機(jī)必須執(zhí)行以查找"figs"為首的如下操作。

第1步：在索引0處查找"figs"，如下圖所示。

"figs"不在索引0處，但可能在集合中的其他位置。在插入之前，需要確保"figs"也不在這些位置。

第2步：查找索引1，如下圖所示。

第3步：查找索引2，如下圖所示。

第4步：查找索引3，如下圖所示。

第5步：查找索引4，如下圖所示。

查找過整個(gè)集合后，我們確定其中沒有"figs"。這時(shí)，就可以完成插入操作了。所以最后一步如下。

第6步：在集合末尾插入"figs"，如下圖所示。

在集合末尾插入值是最好的情況，但對(duì)含有5個(gè)元素的集合來說仍然需要6步。換言之，必須查找其全部5個(gè)元素之后才能執(zhí)行插入操作。

換種說法：對(duì)包含N個(gè)元素的集合來說，在集合末尾插入值最多需要N +1步。這是因?yàn)榇_定集合中不含該值需要N步，而實(shí)際的插入還需要1步。數(shù)組的相同操作則只需要1步。

向集合開頭插入值是最壞的情況。為此，計(jì)算機(jī)需要先查找N個(gè)格子來確保該值不在集合中，然后再用N步來右移全部數(shù)據(jù)，最后再用1步來插入新值。全部加起來是2N +1步。數(shù)組的相同操作則只需要N +1步。

這是否意味著，僅僅因?yàn)樵诩现胁迦朐乇仍跀?shù)組中慢，就應(yīng)該避免使用集合呢？當(dāng)然不是。如果要確保數(shù)據(jù)不重復(fù)，那么集合對(duì)你來說就很重要。（希望有一天我這里的電話簿能修正過來。）但如果沒有這種需求，那么數(shù)組可能更適合你，畢竟數(shù)組的插入效率更高。你必須分析自己的需求，然后再?zèng)Q定哪個(gè)數(shù)據(jù)結(jié)構(gòu)更合適。