📄 6.6.3b.htm
字号:
<html>
<head>
<title>编译原理</title>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312">
<link type="text/css" rel="stylesheet" href="../css/specification.css">
</head>
<body>
<table align=right width=300>
<tr>
<td><img src="../images/previous.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='6.6.3.htm'"></td>
<td><img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='6.6.3c.htm'"></img></td>
</tr>
</table>
<br><br>
<table><tr><td>    </td>
<td class="content">
<P>
根据实际经验可知，如果在大小为m的散列表中有n个名字，那么平均每个链表有n/m个记录。通过选择m可使得n/m小于一个小常数，譬如2，那么访问一个表项的时间基本上是一个常数。
</p>
</td></tr></table>
<table><tr><td>    </td>
<td class="content">
<P>
符号表所占的空间包括散列表的m个字和n个表项的kn个字，其中k是每一个表项占用的字数。即，散列表的空间仅依赖m，表项占用的空间仅依赖于表项的个数。对于m的选择依赖于对符号表的应用。如果把m选为几百，那么即使对于中等大小的程序来说，查表所用的时间相对于编译程序的总开销而言是可以忽略不计的。
</p>
</td></tr></table>
<table><tr><td>    </td>
<td class="content">
<P>
人们把很大的注意力倾注于如何设计一个散列函数，使它可以用来易于对符号串进行计算并且把所有字符串均匀地分配到m个链表中去。
</p>
</td></tr></table>
<table><tr><td>    </td>
<td class="content">
<P>
一个适于计算散列函数的步骤如下：
</p>
</td></tr></table>
<table><tr><td>    </td>
<td class="content">
<P>
1．从字符串s之中的所有字符c<sub>1</sub>，c<sub>2</sub>,...,c<sub>k</sub>确定一个正整数h。具体方法将在下面给以介绍。
</p>
</td></tr></table>
<table><tr><td>    </td>
<td class="content">
<P>
2.把上面确定的整数h转换成链表的编号，即，从0到m—1的一个整数。最简单的方法是用m除以h，把余数作为链表的编号。采用余数法在m是素数时效果更好。
</p>
</td></tr></table>
<table><tr><td>    </td>
<td class="content">
<P>
具体说来，为实现上述第一步骤，首先需要知道符号串s 中的c<sub>1</sub>，c<sub>2</sub>,...,c<sub>k</sub>等每个字符到整数的对应。单个字符到整数的对应往往是由实现语言提供的。例如，Pascal语言提供一个函数ord来实现这一目的；又如，在C语言中若对字符实行算术运算，则将自动地把字符转换成整数。在此基础上，下面给出计算h的一些方法。一个计算h的简单方法是将字符串中所有字符对应的整数值加在一起。更好的办法是在加入下一个字符的值以前将老的h值乘以一个常数a。即，令h<sub>0</sub>=0，h<sub>i</sub>=a(h<sub>i-1</sub>)＋c<sub>i</sub> ，1≤i≤k且令h＝h<sub>k</sub>，k是符号串的长度，式中的c<sub>i</sub>理解作c<sub>i</sub>对应的整数。上面提到的简单地将每个字符对应的整数相加就是a=1的情况。一个类似的策略是让a(h<sub>i-1</sub>)与c<sub>i</sub> 做模2相加（即位式按位加）运算。
</p>
</td></tr></table>
<table><tr><td>    </td>
<td class="content">
<P>
对于32位的整数，我们可以考虑一个接近2<sup>16</sup>的素数作为a，例如a=65599。在计算ah<sub>i-1</sub>的过程中很快就会出现溢出现象，一般可以忽略溢出，仅保留低序的32位即可。
</p>
</td></tr></table>
<br>
<table align=right width=300>
<tr>
<td><img src="../images/previous.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='6.6.3.htm'"></td>
<td><img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='6.6.3c.htm'"></img></td>
</tr>
</table>
</BODY>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -