数据结构为什么如此重要？( 四 ) _数据结构

要是你想往集合["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 步。
这是否意味着因为它的插入比一般的数组慢，所以就不要用了呢？当然不是。在需要保证数据不重复的场景中，集合是非常重要的（真希望有一天我的电话本能恢复正常）。但如果没有这种需求，那么选择插入比集合快的数组会更好一些。具体哪种数据结构更合适，当然要根据你的实际应用场景而定。
总结理解数据结构的性能，关键在于分析操作所需的步数。采取哪种数据结构将决定你的程序是能够承受住压力，还是崩溃。本文特别讲解了如何通过步数分析来判断某种应用该选择数组还是集合。
不同的数据结构有不同的时间复杂度，类似地，不同的算法（即使是用在同一种数据结构上）也有不同的时间复杂度。既然我们已经学会了时间复杂度的分析方法，那么现在就可以用它来对比各种算法，找出能够发挥代码极限性能的那个吧。这也正是《数据结构与算法图解》的第2章中所要讲的。