首页 > 程序开发 > 综合编程 > 其他综合 >

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

2011-04-19

处理实际问题的一般数学方法是,首先提炼出问题的本质元素,然后把它看作一个比现实无限宽广的可能性系统,这个系统中的实质关系可以通过一般化的推理来论证理解,并可归纳成一般公式,而这个一般公式适用于任何特殊情况。       

处理实际问题的一般数学方法是,首先提炼出问题的本质元素,然后把它看作一个比现实无限宽广的可能性系统,这个系统中的实质关系可以通过一般化的推理来论证理解,并可归纳成一般公式,而这个一般公式适用于任何特殊情况。
                                        ——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 {

相关文章
最新文章
热点推荐