(1) 直接寻址的缺点

我们可以看出，直接寻址技术有几个明显的缺点：如果全域U很大，那么表T 将要申请一段非常长的空间，很可能会申请失败；对于全域较大，但是元素却十分稀疏的情况，使用这种存储方式将浪费大量的存储空间。

(2) 散列函数

为了克服直接寻址技术的缺点，而又保持其快速字典操作的优势，我们可以利用散列函数（hash function）

h：U→｛0，1，2，…，m-1｝

来计算关键字k所在的的位置，简单的讲，散列函数h(k)的作用是将范围较大的关键字映射到一个范围较小的集合中。这时我们可以说，一个具有关键字k的元素被散列到槽h(k)上，或者说h(k)是关键字k的散列值。

示意图如下：

这时会产生一个问题：两个关键字可能映射到同一槽中（我们称之为冲突（collision）），并且不管你如何优化h(k)函数，这种情况都会发生（因为|U|>m）。

因此我们现在面临两个问题，一是遇到冲突时如何解决；二是要找出一个的函数h(k)能够尽量的减少冲突；

(3) 通过链表法解决冲突

我们先来解决第一个问题。

解决办法就是，我们把同时散列到同一槽中的元素以链表的形式“串联”起来，而该槽中保存的是指向该链表的指针。如下图所示：

采用该解决办法后，我们可以通过如下的操作方式来进行字典操作：

下面我们来分析上图各操作的性能。

首先是插入操作，很明显时间为O(1)。

然后分析删除操作，其花费的时间相当于从链表中删除一个元素的时间：如果链表T[h(k)]是双链表，花费的时间为O(1)；如果链表T[h(k)]是单链表，则花费的时间和查找操作的渐进运行时间相同。

下面我们重点分析查找运行时间：

首先，我们假定任何一个给定元素都等可能地散列在散列表T的任何一个槽位中，且与其他元素被散列在T的哪个位置无关。我们称这个假设为简单均匀散列（simple uniform hashing）。

不失一般性，我们设散列表T的m个槽位散列了n个元素，则平均每个槽位散列了α = n/m个元素，我们称α为T的装载因子（load factor）。我们记位于槽位j的链表为T[j]（j=1，2，…，m-1），而nj表示链表T[j]的长度，于是有

n = n0+n1+…+nm-1，

且E[nj] = α = n / m。

现在我们分查找成功和查找不成功两种情况讨论。

① 查找不成功

在查找不成功的情况下，我们需要遍历链表T[j]的每一个元素，而链表T[j]的长度是α，因此需要时间O(α)，加上索引到T(j)的时间O(1)，总时间为θ(1 + α)。

② 查找成功

在查找成功的情况下，我们无法准确知道遍历到链表T[j]的何处停止，因此我们只能讨论平均情况。

我们设xi是散列表T的第i个元素（假设我们按插入顺序对散列表T中的n个元素进行了1~n的编号），ki表示xi.key，其中i = 1，2，…，n，再定义随机变量Xij=I｛h(ki)=h(kj)｝，即：

在简单均匀散列的假设下有

P｛h(ki)=h(kj)｝ = 1 / m，

E[Xij] = 1 / m。

则所需检查的元素的数目的期望是：

因此，一次成功的检查所需要的时间是O(2 + α / 2 –α / 2n) = θ(1 + α)。

综合上面的分析，在平均下，全部的字典操作都可以在O(1)时间下完成。

注：凡属于本公众号内容，未经允许不得私自转载，否则将依法追究侵权责任。