1.2 集合：一条规则决定性能

来看看另一种数据结构：集合。它是一种不允许元素重复的数据结构。

其实集合是有不同形式的，但现在我们只讨论基于数组的那种。这种集合跟数组差不多，都是一个普通的元素列表，唯一的区别在于，集合不允许插入重复的值。

要是你想往集合["a", "b", "c"]再插入一个"b"，计算机是不会允许的，因为集合中已经有"b"了。

集合就是用于确保数据不重复。

如果你要创建一个线上电话本，你应该不会希望相同的号码出现两次吧。事实上，现在我的本地电话本就有这种状况：我家的电话号码不单指向我这里，还错误地指向了一个叫Zirkind的家庭（这是真的）。接听那些要找Zirkind的电话或留言真的挺烦的。

不过，估计Zirkind一家也在纳闷为什么总是接不到电话。而当我想要打电话告诉Zirkind号码错了的时候，我妻子就会去接电话了，因为我拨的就是我家号码（好吧，这是开玩笑）。如果这个电话本程序用集合来处理，那就不会搞出这种麻烦了。

总之，集合就是一个带有“不允许重复”这种简单限制的数组。而该限制也导致它在4种基本操作中有1种与数组性能不同。

下面就来分析读取、查找、插入和删除在基于数组的集合上表现如何。

集合的读取跟数组的读取完全一样，计算机只要一步就能获取指定索引上的值。如之前解释的那样，这是因为计算机知道集合开头的内存地址，所以能够一步跳到集合的任意索引。

集合的查找也跟数组的查找无异，需要N步去检查某个值在不在集合当中。删除也是，总共需要N步去删除和左移填空。

但插入就不同了。先看看在集合末尾的插入。对于数组来说，末尾插入是最高效的，它只需要1步。

而对于集合，计算机得先确定要插入的值不存在于其中——因为这就是集合：不允许重复值。于是每次插入都要先来一次查找。

假设我们的购物清单是一个集合——用集合还是不错的，毕竟你不会想买重复的东西。如果当前集合是["apples", "bananas", "cucumbers", "dates", "elderberries"]，然后想插入"figs"，那么就需要做一次如下的查找。

第1步：检查索引0有没有"figs"。

没有，不过说不定其他索引会有。为了在真正插入前确保它不存在于任何索引上，我们继续。

第2步：检查索引1。

第3步：检查索引2。

第4步：检查索引3。

第5步：检查索引4。

直到检查完整个集合，才能确定插入"figs"是安全的。于是，到最后一步。

第6步：在集合末尾插入"figs"。

在集合的末尾插入也属于最好的情况，不过对于一个含有5个元素的集合，你仍然要花6步。因为，在最终插入的那一步之前，要把5个元素都检查一遍。

换句话说，在N个元素的集合中进行插入的最好情况需要N + 1步——N步去确认被插入的值不在集合中，加上最后插入的1步。

最坏的情况则是在集合的开头插入，这时计算机得检查N个格子以保证集合不包含那个值，然后用N步来把所有值右移，最后再用1步来插入新值。总共2N + 1步。

这是否意味着因为它的插入比一般的数组慢，所以就不要用了呢？当然不是。在需要保证数据不重复的场景中，集合是非常重要的（真希望有一天我的电话本能恢复正常）。但如果没有这种需求，那么选择插入比集合快的数组会更好一些。具体哪种数据结构更合适，当然要根据你的实际应用场景而定。