白话算法(6) 散列表(Hash Table)从理论到实用（上）


		处理实际问题的一般数学方法是，首先提炼出问题的本质元素，然后把它看作一个比现实无限宽广的可能性系统，这个系统中的实质关系可以通过一般化的推理来论证理解，并可归纳成一般公式，而这个一般公式适用于任何特殊情况。
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　——R.A. Fisher
　　在一个解决方案的复杂性之中，理论或者概念的部分通常只占有限的一小部分。理论无法做实际的工作——否则它也不成其为理论了。从理论到实用，需要经过一系列的发明。从实用到更加实用、更加通用，往往需要增加更多的复杂性。有时，这一过程远远超越科学的范畴，成为艺术家的乐园。有时，这一过程引入了过多不必要的复杂性，只是因为人类的自私、愚蠢和目光短浅。
　　科学不会也不能处理奇迹。科学只能处理重复的事件，艺术却不同。艺术是“就是如此”。在一个创作诞生以前，它是 Nothing——它没有来由、毫无征兆；诞生之后，它就是存在，是合理，是自然和美。我们所谈论的算法，作为一门实用的科学，既有科学的一面，也有艺术的一面。作为科学，它的结构可以分析，它的行为可以预测，它的属性可以量化，它的正确性可以证明。作为艺术，在一个算法诞生之后，有时我们只能说“它能工作”，仅此而已；对于它是如何来到这个世界上的，我们一无所知——这里没有“因为……所以……”，也不是简单的从一般到特殊。创造，似乎和生命一般神秘。我们可以给造物穿上漂亮的科学外衣，欣赏它内在的一致性，但是，最让人着迷的创造性的那一部分，却完全无法加以描述。
　　所以，当我们进行散列表的从理论到实用之旅时，如果你察觉到一些没有解释的跨越，请不要见怪吧。如果没有这些跨越，我们就完全可以设计一个程序发明这些算法，我们所要学习的算法也就完全会是另外一个样子了。
O(n) 查找和 O(1) 查找，两个模型
　　如果想知道在《伊利亚随笔选》这本书里是否有一个“囿”字，该怎么做呢？我们只有从第一页的第一行开始，一个字一个字地向后看去，直到找到这个字为止。如果直到最后一页的最后一个字都没有找到它，我们就知道这本书里根本没有这个字。所以，这项工作的复杂度是 O(n)。
　　再假设有这样一本《会计专用字帖》，它只有9页，每一页上有一个大写的数字：

 
当会计想要练习“柒”字时，只要她事先知道页码和内容的对应关系，就可以直接翻到第7页，实现 O(1) 复杂度的查找。通过这个模型我们知道，要想达成 O(1) 复杂度的查找，必须满足3个条件：
　　1. 存储单元（例如一页纸）中存储的内容（例如大写数字）与存储单元的地址（例如页码）必须是一一对应的。
　　2. 这种一一对应的关系（例如大写数字“柒”在第7页）必须是可以预先知道的。
　　3. 存储单元是可以随机读取的。这里“随机读取”的意思是可以以任意的顺序读取每个存储单元，并且每次读取所需时间都是相同的。与此相对的，读取磁带里的一首歌就不是随机的——想听第5首歌就不如听第一首歌来得那么方便。
在计算机上实现 O(1) 查找
　　先来看计算机的硬件设备。计算机的内存支持随机存取，从它的名字 RAM(random-access memory) 可以看得出对于这一点它还真有一点引以为傲呢。
　　既然硬件支持，我们就可以准备在计算机上模拟会计专业字帖了。第一项任务是向操作系统申请9个存储单元。这里有个小问题，我们得到的存储单元的地址很可能并不是从1到9，而是从134456开始的。好在我们并不需要直接跟操作系统打交道，高级语言会为我们搞定这些琐事。当我们使用高级语言创建一个数组时，相当于申请了一块连续的存储空间，数组的下标是每个存储单元（抽象）的地址。这样我们第一个 O(1) 复杂度的容器 SingleIntSet 很容易就可以完成了，它只能存储 0～9 这10个数字：
view sourceprint?01 public class SingleIntSet  
02 {  
03     private object[] _values = new object[10];  
04    
05     public void Add(int item)  
06     {  
07         _values[item] = item;  
08     }  
09     public void Remove(int item)  
10     {  
11         _values[item] = null;  
12     }  
13     public bool Contains(int item)  
14     {  
15         if (_values[item] == null)  
16             return false;  
17         else 
18             return (int)_values[item] == item;  
19     }  
20 } 
测试一下：
view sourceprint?1 static void Main(string[] args)  
2 {  
3     SingleIntSet set = new SingleIntSet();  
4     set.Add(3);  
5     set.Add(7);  
6     Console.WriteLine(set.Contains(3)); // 输出 true  
7     Console.WriteLine(set.Contains(5)); // 输出 false  
8 } 
新术语：使用高级语言创建了一个整型数组时（例如 int[] values = new int[10]），我们不再把 values[7] 称为“一个存储单元”，因为存储单元的大小是一个字节，在32位操作系统上，values[7] 的大小是4字节，所以我们要使用一个新术语，把 values[7] 称为 values 数组的一个槽(slot)。
SingleIntSet2（说实话我真不喜欢这个名字，谁会喜欢？！）
　　新需求！同样只需要保存10个数字，只不过这次不是保存0～9，而是需要保存10～19，怎么办？很简单，实现一个槽里的值与地址的映射函数 H() 即可：
view sourceprint?01 public class SingleIntSet2  
02 {  
03     private object[] _values = new object[10];  
04    
05     private int H(int value)  
06     {  
07         return value - 10;  
08     }  
09    
10     public void Add(int item)  
11     {  
12         _values[H(item)] = item;  
13     }  
14     public void Remove(int item)  
15     {  
16         _values[H(item)] = null;  
17     }  
18     public bool Contains(int item)  
19     {  
20         if (_values[H(item)] == null)  
21             return false;  
22         else 
23             return (int)_values[H(item)] == item;  
24     }  
25 } 
测试的时候，使用10～19范围内的数字：
view sourceprint?1 static void Main(string[] args)  
2 {  
3     SingleIntSet2 set = new SingleIntSet2();  
4     set.Add(13);  
5     set.Add(17);  
6     Console.WriteLine(set.Contains(13)); // 输出 true  
7     Console.WriteLine(set.Contains(15)); // 输出 false  
8 } 

房子不够住，难道睡马路？
　　这次，还是存储10个数字，只不过数字的范围是0～19。如何把20个数字存放到10个槽里？还能怎么办，2人住1间咯。略微修改一下 H() 函数，其它代码不变：
view sourceprint?01 public class SingleIntSet3  
02 {  
03     private object[] _values = new object[10];  
04    
05     private int H(int value)  
06     {

补充：综合编程 , 其他综合 ,