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

下面来看另一个数据结构：集合。集合中包含的元素不能重复。

集合有多种类型，但本节只讨论基于数组的集合。这种集合和数组很相似，它们都是存储值的简单列表，二者的唯一区别在于，不能往集合中插入重复的值。

假设已知集合["a", "b", "c"]，而你想再添加一个"b"。因为"b"已经存在于集合中，所以计算机会拒绝这次操作。

当需要确保数据不重复时，集合非常有用。

比如你要做一个在线电话簿，你肯定不希望看到重复的电话号码。其实我这里的电话簿就有这种问题：除了我家以外，我家的电话号码还被记成了Zirkind家的号码。（这是真事。）我跟你说——我真的很讨厌接到找Zirkind的电话或是语音留言。我敢说Zirkind家肯定也很奇怪为什么没人给他们打电话。我给Zirkind家打电话告知此事时，打成了自家电话，结果接电话的是我妻子。（好吧，这段是编的。）要是那个电话簿程序使用的是集合该多好……

无论如何，基于数组的集合就是不允许有重复元素的数组。虽然这一点很有用，但这简单的限制会影响集合的某种主要操作的效率。

下面来分析读取、查找、插入以及删除在基于数组的集合上的效率。

集合的读取和数组的读取完全一致，即计算机检查特定索引处的值只需要1步。这是因为计算机能跳转到集合内的任意索引，而这只需简单地计算并跳转到其内存地址即可。

集合的查找也和数组的查找没什么区别，即查找集合中的值最多需要N步。集合和数组的删除操作也一模一样，即要删除一个值并移动其他数据来填空最多需要N步。

集合的插入和数组的插入则不同。先来看看在集合末尾插入值。这对数组来说只需要1步，是最好的情况。

但集合不同，计算机需要先判断这个值是否存在于集合中——因为集合的规则是不允许插入重复数据。

计算机要如何确保新数据不在集合中呢？记住，计算机一开始并不知道数组或者集合的格子中存储了什么值。因此，它必须先在集合中查找，才能知道要插入的值是否已经存在。只有集合中不存在这个新值的时候，计算机才能继续执行插入操作。

所以，所有的插入操作都需要先进行查找。

来看一个例子。假设之前提到的购物清单是用集合存储的。这个假设很合理，因为我们不想重复购物。假设集合目前是["apples", "bananas", "cucumbers", "dates", "elderberries"]，而我们想插入"figs"。计算机必须执行以查找"figs"为首的如下操作。

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

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

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

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

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

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

查找过整个集合后，我们确定其中没有"figs"。这时，就可以完成插入操作了。所以最后一步如下。

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

在集合末尾插入值是最好的情况，但对含有5个元素的集合来说仍然需要6步。换言之，必须查找其全部5个元素之后才能执行插入操作。

换种说法：对包含N个元素的集合来说，在集合末尾插入值最多需要N +1步。这是因为确定集合中不含该值需要N步，而实际的插入还需要1步。数组的相同操作则只需要1步。

向集合开头插入值是最坏的情况。为此，计算机需要先查找N个格子来确保该值不在集合中，然后再用N步来右移全部数据，最后再用1步来插入新值。全部加起来是2N +1步。数组的相同操作则只需要N +1步。

这是否意味着，仅仅因为在集合中插入元素比在数组中慢，就应该避免使用集合呢？当然不是。如果要确保数据不重复，那么集合对你来说就很重要。（希望有一天我这里的电话簿能修正过来。）但如果没有这种需求，那么数组可能更适合你，毕竟数组的插入效率更高。你必须分析自己的需求，然后再决定哪个数据结构更合适。