苹果|冲突越少，性能越强！苹果

文章图片

1、引言
大多数优秀的编程语言都提供了散列表的实现，所以无需知道是怎么实现它们的。虽然我们不用过多的考虑散列表的内部原理，但是依然要考虑性能。但是考虑散列表的性能，你还需要了解散列表的冲突是怎么回事。
2、冲突
前两节介绍过，散列函数通过用户输入输出数组索引，然后通过索引输出数组内容。实际上，应该不存在这样的散列函数。下面给出一个简单的例子：
假设我们需要将商品按照首字母的顺序存储到数组中，那么我们需要创建一个长度为26的数组，然后使用散列函数每当进来一个商品都区分一下它的首字母，假如是apple ，那么就把它存储到数组的头位置，如果是zoo（假设有这一种商品），那么我们应该将它存储到哪里呢？应该存储到数组的尾位置。但是这时又来了一个avocado（牛油果）那么我们应该存到哪里呢？按照散列函数设定，我们还是需要将它存到数组的头位置中，那么就会导致一个问题？因为头位置已经存储了apple ，这时如果还存在头位置中，势必会覆盖头位置的价格，当你查询apple 价格时，出来的却是avocado的价格。这样显然是不正确的。这种情况就叫做冲突（collision）。那么我们需要避免冲突，应该怎么办呢？最简单的办法正如：如果两个键都指向了同一个位置，那么就在这一个位置上加一个链表。（具体的冲突是有一套算法的，但是在入门阶段先暂时放放，到进阶学习时一并奉上）。

冲突的散列表
在上图的链表中，我们如果需要查询香蕉的价格，速度依然很快。但是我们需要查询苹果和牛油果的价格，速度会相对慢点，因为在第一个位置还要从链表中进行查找。上面只有两个商品查询速度依然很快，但如果把所有的a开头的商品都写进链表，那么此时的链表查询就非常糟糕。
【苹果|冲突越少，性能越强！】那么我们如何规避这种糟糕的情况呢：

一个好的散列函数是非常必要的。理想情况下，散列函数需要将键值均匀地映射到散列表的不同位置。
如果散列函数的选择的恰当，链表就不会很长。

3、性能
还记得在平均情况下，散列表执行操作的时间复杂度是多少呢？是O（1），它被称作常量时间，这意味着，无论散列表中包含一个元素还是10亿个元素，从其中获取数据所需的时间都是相同。但这个说的是散列表的平均情况，但在最糟糕的情况下，散列表各项操作的时间都为O（n）。

时间复杂度比较
如何避开这种糟糕情况呢，需要做到下面两点：

较低的填装因子；
良好的散列函数

3.1 填装因子
散列表的填装因子 = 数组中已经占用的位置数/数组长度
散列表使用数组来存储数据，因此需要先计算出数组中被占用的位置数，

填装因子
根据公式计算一下这个散列表的填装因子是多少？很容易算得天装因子为0.25 。假设你要在散列表中存储100种商品的价格，该散列表中包含100个位置，那么最好的情况下，每个商品都有自己的位置。在最满的情况下，散列表的填装因子为1 ，如果将散列表的位置减半，那么填装因子立马就为2了，显然散列表中不够存储，那么就需要调整散列表中的长度。原则上，散列表的填装因子越低，说明散列表越是均匀分布，发生冲突的可能性就会很小，散列表的性能越高。一个经验规则：一旦填装因子大于0.7 ，就调整散列表的长度。
3.2 好的散列函数
良好的散列函数取决于是否让数组中的值呈均匀分布。糟糕的散列函数就是每个位置都会存在一个链表，存在大量冲突的地方。那么什么的散列函数是良好的呢？推荐一个SHA函数，这个会在之后的学习中会学到，如果有兴趣，先去了解一下吧。