语言中的符号为相互区分起见,它们的代码值都是不相同的。但是经过杂凑运算后,就有可能得到相同的杂凑值,对表长求余后散列位置的相同可能性更加增大。这种不同符号散列到同一表项位置的现象,我们称它为散列冲突。表长N若取一个素数可以解决部分由于"求余"操作所产生的冲突,但这不是解决冲突的根本方法。为根本解决冲突,需要采取第二次仍至更多次的散列。大多数编译程序中,解决冲突采用的多次散列方法如下。从冲突点位置向下寻找空表项,找到的第一个空表项即为发生冲突的符号所散列的位置。如若一直到表底,没有找到空表项,则循环从表头开始寻找空表项,如若一直到冲突点仍设有空表项,则说明该语言程序中的符号太多,符号表已不能容纳全部符号登入,这时编译程序将发出符号表溢出的系统出错消息。关于散列表的构造和它的查找算法更详细的可参阅"数据结构"书的有关部分。 杂凑函数的选取是构造散列表的关键。影响散列效果的因素除了选择杂凑函数之外,还受到符号构造的特征因素的影响。例如保留字或操作符的符号表,由于它们的符号代码是事先确定的,且对任何程序都是不变的,我们可选择各种杂凑函数进行试验,使之达到最好的散列效果。有人把这种符号表称为静态符号表。相应的变量符号的符号表被称为动态符号表。因为变量符号的选择是由语言程序的设计者进行的,变量符号的选择往往与程序所解决的应用范围有关,并且还常常与程序设计者的习惯,爱好和心理状态有关。这种动态符号表的杂凑函数很难从符号本身去发现提高散列效果的因素,往往是凭系统设计者的经验和爱好。 |