📄 ds9.4.3.htm
字号:
<table border="1" width="388" height="61" bordercolorlight="#3366CC" bordercolordark="#000000">
<tr>
<td width="36" height="30" valign="middle" align="center"><!--mstheme--><font face="宋体">
<p align="center"><font size="5" color="#FFFFFF"><b>0</b></font><!--mstheme--></font></td>
<td width="36" height="30" valign="middle" align="center"><!--mstheme--><font face="宋体"><font size="5" color="#FFFFFF"><b>1</b></font><!--mstheme--></font></td>
<td width="36" height="30" valign="middle" align="center"><!--mstheme--><font face="宋体"><font size="5" color="#FFFFFF"><b>2</b></font><!--mstheme--></font></td>
<td width="35" height="30" valign="middle" align="center"><!--mstheme--><font face="宋体"><font size="5" color="#FFFFFF"><b>3</b></font><!--mstheme--></font></td>
<td width="35" height="30" valign="middle" align="center"><!--mstheme--><font face="宋体"><font size="5" color="#FFFFFF"><b>4</b></font><!--mstheme--></font></td>
<td width="35" height="30" valign="middle" align="center"><!--mstheme--><font face="宋体"><font size="5" color="#FFFFFF"><b>5</b></font><!--mstheme--></font></td>
<td width="35" height="30" valign="middle" align="center"><!--mstheme--><font face="宋体"><font size="5" color="#FFFFFF"><b>6</b></font><!--mstheme--></font></td>
<td width="35" height="30" valign="middle" align="center"><!--mstheme--><font face="宋体"><font size="5" color="#FFFFFF"><b>7</b></font><!--mstheme--></font></td>
<td width="35" height="30" valign="middle" align="center"><!--mstheme--><font face="宋体"><font size="5" color="#FFFFFF"><b>8</b></font><!--mstheme--></font></td>
<td width="35" height="30" valign="middle" align="center"><!--mstheme--><font face="宋体"><font size="5" color="#FFFFFF"><b>9</b></font><!--mstheme--></font></td>
<td width="35" height="30" valign="middle" align="center"><!--mstheme--><font face="宋体"><font size="5" color="#FFFFFF"><b>10</b></font><!--mstheme--></font></td>
</tr>
<tr>
<td width="36" height="31" valign="middle" align="center"><!--mstheme--><font face="宋体"><b><font size="5" color="#FFFFFF">11</font></b><!--mstheme--></font></td>
<td width="36" height="31" valign="middle" align="center"><!--mstheme--><font face="宋体"><font size="5" color="#FFFFFF"><b>22</b></font><!--mstheme--></font></td>
<td width="36" height="31" valign="middle" align="center"><!--mstheme--><font face="宋体"><!--mstheme--></font></td>
<td width="35" height="31" valign="middle" align="center"><!--mstheme--><font face="宋体"><b><font size="5" color="#FFFFFF">47</font></b><!--mstheme--></font></td>
<td width="35" height="31" valign="middle" align="center"><!--mstheme--><font face="宋体"><font size="5" color="#FFFFFF"><b>92</b></font><!--mstheme--></font></td>
<td width="35" height="31" valign="middle" align="center"><!--mstheme--><font face="宋体"><b><font size="5" color="#FFFFFF">16</font></b><!--mstheme--></font></td>
<td width="35" height="31" valign="middle" align="center"><!--mstheme--><font face="宋体"><font size="5" color="#FFFFFF"><b>3</b></font><!--mstheme--></font></td>
<td width="35" height="31" valign="middle" align="center"><!--mstheme--><font face="宋体"><b><font size="5" color="#FFFFFF">7</font></b><!--mstheme--></font></td>
<td width="35" height="31" valign="middle" align="center"><!--mstheme--><font face="宋体"><b><font size="5" color="#FFFFFF">29</font></b><!--mstheme--></font></td>
<td width="35" height="31" valign="middle" align="center"><!--mstheme--><font face="宋体"><font size="5" color="#FFFFFF"><b>8</b></font><!--mstheme--></font></td>
<td width="35" height="31" valign="middle" align="center"><!--mstheme--><font face="宋体"><!--mstheme--></font></td>
</tr>
</table>
<!--mstheme--><font face="宋体"></center>
</div>
<p style="margin-top: 0; margin-bottom: 0"><b><font size="5" color="#FFFFFF"><span style="mso-spacerun: yes; mso-bidi-font-size: 10.0pt; font-family: Times New Roman; mso-fareast-font-family: 宋体; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA" lang="EN-US"> </span><span style="mso-bidi-font-size: 10.0pt; font-family: Times New Roman; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA; mso-spacerun: yes; mso-fareast-font-family: 宋体" lang="EN-US"> </span></font></b>
<p style="margin-top: 0"><b><font size="5" color="#FFFFFF"><span style="mso-bidi-font-size: 10.0pt; font-family: Times New Roman; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA; mso-spacerun: yes; mso-fareast-font-family: 宋体" lang="EN-US">
</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman; mso-bidi-font-family: Times New Roman; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">线性探测法可能使第</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt; font-family: Times New Roman; mso-fareast-font-family: 宋体; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">i</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman; mso-bidi-font-family: Times New Roman; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">个哈希地址的同义词存入第</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt; font-family: Times New Roman; mso-fareast-font-family: 宋体; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">i+1</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman; mso-bidi-font-family: Times New Roman; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">个哈希地址，这样本应存入第</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt; font-family: Times New Roman; mso-fareast-font-family: 宋体; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">i+1</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman; mso-bidi-font-family: Times New Roman; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">个哈希地址的元素变成了第</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt; font-family: Times New Roman; mso-fareast-font-family: 宋体; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">i+2</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman; mso-bidi-font-family: Times New Roman; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">个哈希地址的同义词，……，因此，可能出现很多元素在相邻的哈希地址上“堆积”起来，大大降低了查找效率。为此，可采用二次探测法，或双哈希函数探测法，以改善“堆积”问题。</span></font></b></p>
<p align="left"><b><span style="mso-bidi-font-size: 10.0pt; font-family: 黑体; mso-hansi-font-family: Times New Roman; mso-bidi-font-family: Times New Roman; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA" lang="EN-US"><font size="5" color="#FFFF00"><span style="mso-spacerun: yes; mso-bidi-font-size: 10.0pt; font-family: 黑体; mso-hansi-font-family: Times New Roman; mso-bidi-font-family: Times New Roman; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA"> </span>2.
二次探测法</font></span></b></p>
<p class="MsoNormal"><font size="5" color="#FFFFFF"><b><span lang="EN-US"><span style="mso-spacerun: yes">
</span>H<sub>i</sub>=(Hash(key)</span><span style="font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman"">±</span><span lang="EN-US">d<sub>i</sub>)
mod m</span></b></font></p>
<p class="MsoNormal"><font color="#FFFFFF"><b><font size="5"><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">其中：</span></font></b></font></p>
<blockquote>
<p class="MsoNormal"><font size="5" color="#FFFFFF"><b><span lang="EN-US">Hash(key)</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">为哈希函数</span></b></font></p>
<p align="left"><font size="5" color="#FFFFFF"><b><span lang="EN-US">m</span><span style="font-family:宋体;
mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">为哈希表长度，</span><span lang="EN-US">m</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">要求是某个</span><span lang="EN-US">4k+3</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">的质数</span><span lang="EN-US">(k</span><span style="font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">是整数</span><span lang="EN-US">)</span></b></font></p>
<p align="left"><font size="5" color="#FFFFFF"><b><span lang="EN-US" style="mso-bidi-font-size: 10.0pt; font-family: Times New Roman; mso-fareast-font-family: 宋体; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">d<sub>i</sub>
</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman; mso-bidi-font-family: Times New Roman; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">为增量序列</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt; font-family: Times New Roman; mso-fareast-font-family: 宋体; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">
1<sup>2</sup></span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman; mso-bidi-font-family: Times New Roman">,</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt; font-family: Times New Roman; mso-fareast-font-family: 宋体; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">-1<sup>2</sup></span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman; mso-bidi-font-family: Times New Roman; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">,</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt; font-family: Times New Roman; mso-fareast-font-family: 宋体; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">2<sup>2</sup></span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman; mso-bidi-font-family: Times New Roman">,</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt; font-family: Times New Roman; mso-fareast-font-family: 宋体; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">-2<sup>2</sup></span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman; mso-bidi-font-family: Times New Roman; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">,…,</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt; font-family: Times New Roman; mso-fareast-font-family: 宋体; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">q<sup>2</sup></span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman; mso-bidi-font-family: Times New Roman">,</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt; font-family: Times New Roman; mso-fareast-font-family: 宋体; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">-q<sup>2</sup></span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman; mso-bidi-font-family: Times New Roman; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">且</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt; font-family: Times New Roman; mso-fareast-font-family: 宋体; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">q</span><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman; mso-bidi-font-family: Times New Roman; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">≤<span lang="EN-US" style="mso-bidi-font-size: 10.0pt; font-family: Times New Roman; mso-fareast-font-family: 宋体; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA"><img border="0" src="ds9.4.21.gif" align="middle" width="23" height="28">(m-1)</span></span></b></font></p>
</blockquote>
<p align="left"><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman""><font color="#FFFFFF"><b><font size="5">【例</font></b></font></span><font color="#FFFFFF"><b><font size="5"><span lang="EN-US">9.12</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">】关键码集为</span><span lang="EN-US"> {47</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">，</span><span lang="EN-US">7</span><span style="font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">，</span><span lang="EN-US">29</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">，</span><span lang="EN-US">11</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">，</span><span lang="EN-US">16</span><span style="font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">，</span><span lang="EN-US">92</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">，</span><span lang="EN-US">22</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">，</span><span lang="EN-US">8</span><span style="font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">，</span><span lang="EN-US">3}</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">，哈希表表长为</span><span lang="EN-US">11</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">，</span></font></b></font><font size="5" color="#FFFFFF"><b><span lang="EN-US" style="mso-bidi-font-size: 10.0pt; font-family: Times New Roman; mso-fareast-font-family: 宋体; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA"><span style="mso-spacerun: yes">
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -