📄 6.6.3.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.2.htm'"></td>
<td><img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='6.6.3b.htm'"></img></td>
</tr>
</table>
<br><br>
<font class="title2"><b>6.6.3 散列表</b></font>
<table><tr><td>    </td>
<td class="content">
<P>
各种各样的散列技术在编译程序的实现中得到了广泛的应用。这里我们考虑一种简单的散列技术称为<b>开放散列</b>（open hashing），这里的“开放”是指对于表中表项的个数不加以限制。这种方法可以使得对于我们选择的任意常数m，在表中插入n个名字和在n个名字上进行e次查找所需的总的时间与n(n+e)/m成正比。由于m可以变得很大，直到n,所以这种方法比线性表有效的多，是在许多情况下经常采用的。由于数据结构所占用的空间随m的加大而增大，这说明此方法用空间换取了时间。
</p>
</td></tr></table>
<table><tr><td>    </td>
<td class="content">
<P>
基本的散列模式如图6.28所示，其数据结构包括两部分：
</p>
</td></tr></table>
<table><tr><td>    </td>
<td class="content">
<P>
1．由一个固定的数组组成的一个散列表（hash table），数组的m个元素是m个指向表项的指针。
</p>
</td></tr></table>
<table><tr><td>    </td>
<td class="content">
<P>
2．表项被组织到m个分开的链表中，这些链表称为散列表元或存储桶（bucket），其中有些散列表元可能是空的。符号表中的每一个表项恰好出现在这些链表之中的某一个。
</p>
</td></tr></table>
<table><tr><td>    </td>
<td class="content">
<P>
为了确定在符号表中是否有关于名字s(或说串s)的表项，我们对s使用一个<b>散列函数</b>h(s)，使得h(s)返回一个在0和m－1之间的一个整数。如果s在符号表中，那么它就在编号为h(s)的链表中。如果s尚不在符号表中，那么就为s创建一个记录连到编号为h(s)的链表的前端。
<p>
</p>
</td></tr></table>
<center><img src="6_28.gif" width="583" height="338"></center>
<p align=center>图6.28 一个散列表</p>
<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.2.htm'"></td>
<td><img src="../images/next.gif" onmouseover="javascript:style.cursor='hand'" onclick="vbscript:window.location.href='6.6.3b.htm'"></img></td>
</tr>
</table>
</BODY>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -