编译原理与实践：杂凑法及填表过程

由于符号表的管理频繁涉及查表和填表操作，如何提高这两方面的效率就成为非常重要的问题。线性表填表快，查表慢；对折法填表慢，查表快；而这里将要探讨的杂凑法（又称散列法、Hash法）是一种查表、填表两方面工作都能高速进行的统一技术。

杂凑法的具体内容是：假定有一个足够大的区域，在该区域中可以填写—张含N项的符号表。现构造一个地址函数（也称为杂凑函数）H，使其对于任何名字sym，H（sym）的值处于0～N-1之间。即，不论对sym查表或填表，都能够从H（sym）获得它在表中的位置。例如，用无符号整数作为项名，令N=17，把H（sym）定义为sym/N的余数，于是，名字‘09’将被置于表中的第9项，‘34’将被置于表中的第0项，而‘171’则将被置于表中的第1项，如此类推。对于地址函数H有两点要求：一是函数的计算要简单、高效；二是函数值能够比较均匀地分布在0～N-1之间。比如，取N为质数，把H（sym）定义为sym/N的余数就是一个十分常见的做法。

由于用户使用的标识符是随机的，而且标识符的个数也是无限的（尽管对于一个给定的源程序来说是有限的），因此，虽然构造函数H的方法很多，但要构造一个一一对应的函数则是相当困难的。此时，除了希望函数值的分布比较均匀之外，还应设法解决“地址冲突”的问题。

我们举一个例子来说明什么是“地址冲突”。假设N=17，H（sym）取为sym/N的余数，由于H（‘05’）=H（‘22’）=5，因此，表格的第5项将要放置两个项名，从而产生地址冲突问题。

解决上述问题的方法是：使用一张杂凑表（Hash Table），把所有相同杂凑值的符号名连成一串，从而通过间接的方式查填符号表。杂凑表可定义为一个容纳N个指示器值的一维数组，数组元素的初值全为null。符号表除了通常包含的栏目外，还增设一个链接栏，通过它把所有持相同杂凑值的符号名连接成一条链。例如，假定H（syml）=H（sym2）=H（sym3）=h，于是，这三个项在符号表中的情形如图7-8所示。(www.xing528.com)

图7-8　杂凑法

关于名字sym的填表过程可描述为：首先，计算出H（sym）的值h，置p：=HASHTABLE[h]，若未曾有杂凑值为h的项名填入过，则p=null；然后，置HASHTABLE[h]=available，并把sym及其链接指示器的值p填进available所指的符号表表项，并累增available的值，使它指向下一个空表项。

若要在符号表中查找sym，则需先计算出H（sym）的值h，然后根据指示器HASHTABLE[h]所指的项链逐一按序查找，显然，这是一个线性查找的过程。