数据结构（邓俊辉）学习笔记】词典 01—— 散列

1. 从服务到电话

现在进入新的一章词典。将学习实现词典 adt 的重要技术，也就是散列。我们将看到散列实际上并不是一种简单的技术，从某种意义上讲，它甚至是一种思想，是的，散列是一种赖以高效组织数据并实现相关算法的重要思想。

接下来我们就会看到，在这种思想背后的原理是多么的直观和简单。

我们的故事要从服务电话说起。当你需要获得某个公司或者部门的服务，你应该如何通过电话来找到他们呢？查电话簿，没错，这是一种司空见惯的方法。不过如果你手头没有电话簿，或者电话簿太厚，以至于你没有足够的耐心去查阅，又当如何呢？

作为一个公司，应该明白有相当多的客户都是因为这种纠结而流失掉了。因此反过来一家优秀的公司应该为它的服务取一个更加便于记忆的电话号码。

对此，你有什么建议？

你或许会说，那不妨就取 8个8或者8个6或者12345678，这些解决方案，尽管也勉强可行，但是如果从突出公司和服务个性的角度来看，这一类方法都是不够的。

下面不妨来看更有经验的公司是如何巧妙地解决这个问题的。

比如你如果需要致电 IBM 公司，就它的服务或产品进行咨询，那么你就可以拨打这个电话1-800-IBM-4YOU。没错，就是这个电话或者这个电话1-888-SHOP-IBM。没错，就是这个和这个电话。

如果你是第一次在这些公司的首页上看到这类电话，你或许会有所质疑，因为它并不像你直观理解的那样给出了一个完全由数字组成的电话号码。但是我相信很快就会习惯并且喜欢这种方式，并且由此对这类公司留下深刻而友好的印象。

实际上，你只要掏出你的电话，留意一下键盘。或许在此之前，对于每一个键，你只留意了其中的阿拉伯数字，而实际上当下大部分的键盘都是这种形式（其中每个键上除了有一个阿拉伯数字，同时还拥有若干个英文字母）。

我们可以理解为这样的一个键既可能对应于一个数字，也可能同时对应于若干个字母，也就是说由数字和字母混搭构成的电话号码也是可行的。

请留意体会这种方式的巧妙之处。

2. 循值访问

这种巧妙体现两个方面。

1. 其一 通过这样一种形象生动而友好的方式，不仅可以使得你便捷地记住这个电话号码，同时更重要的是你能记住它是这家公司的电话号码。
2. 另一方面，只要你能够辨识26个英文字母，你就可以通过这种方式来进行拨号，而你的每一次拨打依然对应于一串数字。整个的电话服务系统除了需要引入一种扩充之后的键盘，无需做任何更多的改造。

比如当你按照这样的提示（1-855-LENOVO）去拨打时，你所拨打的电话号码实际上依然是由数字组成的(1-855-253-6686)。实际上在这样一种巧妙的变换技巧背后，是某种深刻的思想。

我不妨就访问数据的方式来做一对比。

你应该记得对于不同的数据结构，我们在此之前都根据其如何访问数据进行过分类。你应该还记得有循秩访问 call by rank，比如向量，再如寻位置访问 call by position， 这方面的典型例子是列表 list，而以 BST 为典型代表的这类数据结构都属于循关键码访问，也就是 call by key。

反观，我们这里对电话号码的访问，如果说我们这里访问的对象是公司的服务，那么刚才这种获取服务的方式又属于其中的哪种呢？首先这种方式既不是循秩，也不是循位置访问，这是因为所有的公司的各项服务之间并不存在某种线性次序。

那么它是循关键码访问吗？这里的确有关键码，也就是每一个服务所对应的那个电话号码。然而即便你是按照刚才的方式去拨打某个特定的电话，在整个过程中，在你的脑海里除了那个公司和服务的助记符号之外，完全可以不出现任何形式的数字电话号码，因此这也不属于询关键码访问的方式。

那么我们刚才实质访问的是什么呢？是的，也就是你所需要找到的那个对象本身，我们称之为 value 数值。因此我们不妨将新的这种访问方式就称作循数值访问，call by value。

我们刚才已经领略到了这种新的访问方式的威力。是的，若能加以充分利用这种访问方式，将使我们的计算效率进一步得以提高，而这样的一种典型的技巧就是所谓的 hashing。中文可以根据含义译作杂凑，也可以根据发音，译作哈希，在这里不妨采用一种折中的译法，也就是散列。那么具体什么是散列呢？

3. 数组

看这样的一个具体实例，假设我们现在要为某一所高校制作一本电话簿。也就是说对于这个学校的每一位老师、学生以及员工或者办公室都可以通过这个电话簿直接找到对应的电话号码。

现在我们在进一步的假设，还有反过来的需求，也就是像现在的任何一部智能手机那样，对于任何一个有记录的电话号码都可以及时的给出机主的信息，那么这样一种需求应当如何来满足呢？

我想略作思考之后，你很可能就会认为这个问题的难度其实并不高。是的，表面看来确实如此，甚至不需要10行代码就能完成这个任务。比如你首先想到的很有可能就是数组，这种方法的原理可以表示为这样一幅图（上右图），这里由上而下就是一个线性数组，而在此区间之内的每一个秩，都对应于某一个电话号码，而每一个元素就可以用来记录对应机主的信息，比如一种方法就是我们通过电话号码确定对应的秩，找到对应的单元，并根据对应单元所给的引用间接地找到对应的机主。

这个是这样，其他的以及每一个单元都是这样。你甚至会说，嗯，这种方法不仅简明，而且高效，因为正如我们所看到的，从任何一个电话号码找到对应的机主记录，只需常数的时间，难道还有比这更高的效率吗？

是的，就实际效率而言，的确如此，但是不要忘了同时还有另一个因素需要兼顾。对，空间。

我们不妨来算一个账，就以老师所在的清华大学为例，不妨只考察座机。于是从理论上来说，清华大学所在的北京市的任何一部座机都有可能属于清华。因此如果采用上述的数组方式，数组的规模将高达10的8次方，也就是100M。那么清华大学实际拥有的固定电话又有多少门呢？据十多年前所获得的不完全统计，大致是在2至3万门之间，不妨粗略的故作为25K，于是我们就可以大致的估算出空间效率，具体来说也就是我们所用的空间总量与其中真正有效的数据项之比。

所谓不比不知道，一比吓一跳，可以看到空间效率只有万分之几，如此低下的效率是我们万万不能接受的，这样的实例还很多。这类应用的公共特点是我们需要存储和组织的数据项可能来自于一个相当大的空间，比如对于一个城市而言，理论上讲的100M门固定电话。

而在任何一个常规的时刻，我们所真正需要存储和组织的数据只是其中非常小的一个子集，因此，即便我们能够开出如此之大的数组，其空间效率也注定是极低的。那么如何破解这一难题呢？

4. 原理

实际上，我们刚才介绍的数组方法并非一无是处，就原理而言，只需再向前略作改进，也就成为了散列。

为此需要首先统一一些名词，比如在这里数组中的每一个单元将被称作为桶 bucket，其中可能直接存放某一个词条，也可能存放的是一个词条的间接引用。

而以上所说的数组在这里将被称为是桶数组(bucket array)，或者直接的称之为散列表(hash table)。 我也统一地将散列表的长度记作 M。而这里的核心技巧恰恰就在于散列表长度的选取。

首先，散列表至少应该能够足以容纳所有的待存放元素，因此这个不等号也就必须满足，其次正如我们已经看到的，直接应用数组的方法，它的致命缺点在于所使用的空间远远过大，因此所谓的散列表也可以认为是对这个空间做了一个适当的压缩。

既然是散列表的长度关乎我们的空间效率，所以这种压缩必须是实质性的。也就说在数量级上 M 要实质的圆小于 R，尽管 M 必须大于 N，但是为了实现尽可能高的效率，M 还是应该与 N 尽可能的同阶。

这样我们实际所花费的空间量就能够控制在线性的范围以内，那么这种思路如何兑现呢？应该记得在此前那种朴素的数组方法中，对于任何一个关键码，我们都可以在 O(1) 的时间内直接得到对应的记录或者它的间接引用。

而在做过空间压缩之后的现在，这个功能又当如何实现呢？如果将这种确定目标词条位置的功能，称作为定址，那么具体的定址方法也就是我们所说的散列hashing。为了完成散列定制，我们需要在事先确定一个散列函数，借助这个函数可以将任意关键码转换为对应的词条或它的入口。

在这个原理图中，原先一蹴而就的过程被分解为了两步，也就是当任意给定的关键码通过 hash function 转换为散列表中的某一个桶单元并且进而通过这个桶单元找到目标词条。

尽管整个过程多了一些曲折，但是正如我们最终将要看到的，只要散列函数设计已实现得当，我们就可以将整个过程所需要的时间控制在期望的常数范围以内。

那么这里的散列表应当如何压缩并得到呢？相应的散列函数又当如何设计呢？

5. 散列

再次回到清华大学电话簿的那个实例，假设这就是所使用的散列表，可以看到散列表的长度在这里取做90,001，这一取值的确符合我们的设计原理，也就是一方面要在数量级上远远的小于10的8次方，同时相对于我们实际需要存放的记录数，也就是大致25K， 表长既能够足够大，同时又在数量级上保持同阶。

经过这样的压缩，空间利用率将上升至少为1/4。再来看散列函数，对于任何一个关键码，该散列函数都将它映射为它相对于表长 M 的整数模余。也就说任何一个8位的电话号码都将经过相对于90,001的整除被映射至相应的余数。

我们看几个具体的实例，不妨先掏出计算器，已备待会的验算之需，首先来看中间这个电话号码，根据它在经过对90001的整数取模就可以得到反列表中的一个桶，而这个桶则正确地指向了机主所对应的词条。下面这个电话号码也是如此，根据它经过对90001的取模，同样可以找到桶单元，而根据这个桶单元也同样可以找到机主所对应的词条记录。事实上，只要这个电话号码的确属于清华大学，按照这样的一个算法，的确都可以获得相应的机主信息。

至此，我们已经基本上圆满地实现了这个应用需求，难道不是吗？从每一个电话号码到对应的机主信息，只需要常数的时间。而空间效率呢？按照刚才的估算，也足以令人满意。特别的，对于散列表而言，其空间效率主要取决于 N 与 M 的比值，这一比值也称作装填因子（load factor）。 通常也简记作$\lambda$。是的，就目前而言，我们的解决方法的确几乎完美。然而，这里的故事依然没有结束。

6. 冲突

再次回到刚才电话号码簿的实例，散列表的长度依然，散列函数也保持不变。于是刚才的三个电话号码也将保持同样的映射。

现在假设还同时需要存放第四个电话号码。如果你的计算器在手边，不妨将它关于90001做一个整除取模的运算，你会发现什么呢？是的，这个电话号码居然也会被映射到51304这个位置。

这个情况也称作散列冲突 hash collision。也就是说两个不同的关键码有可能会被映射到同一个桶单元。一山要容两虎，这是很难做到的。当然，适当的将装贴因子降低或者等效地说将散列表取得更长，的确能够在一定程度上降低这种情况发生的概率，但是很遗憾，这类冲突几乎是不能杜绝的。

对散列函数稍加观察，就不难发现这背后的原因。因为所谓的散列函数可以理解为是将来自于更大的一个定义域R中的元素映射到相对而言远远更小的一个取值域。形象地说，我们有很多很多的鸽子，但是只有寥寥无几的笼子。根据鸽巢原理，这种冲突必然是无法彻底避免。

当然，好消息就是，只要策略和方法得当，我们完全可以将此类冲突的概率控制在一个足够低的范围。为此我们既要研究散列函数的设计方法，更要研究在冲突依然发生时，如何有效的排解。