📄 ds9.4.3.htm
字号:
</span>Hash(key)=key mod 11</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></b></font><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="#FFFFFF">二次探测法</font></span></b><font size="5" color="#FFFFFF"><b><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></b></font></p>
<div align="center">
<center><!--mstheme--></font>
<table border="1" width="388" height="61" bordercolorlight="#3366CC" bordercolordark="#000000">
<tr>
<td width="32" 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="40" 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="33" height="30" valign="middle" align="center"><!--mstheme--><font face="宋体"><font size="5" color="#FFFFFF"><b>6</b></font><!--mstheme--></font></td>
<td width="37" 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="32" height="31" valign="middle" align="center"><!--mstheme--><font face="宋体"><b><font size="5" color="#FFFFFF">11</font></b><!--mstheme--></font></td>
<td width="40" 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="宋体"><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">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="33" height="31" valign="middle" align="center"><!--mstheme--><font face="宋体"><!--mstheme--></font></td>
<td width="37" 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 class="MsoNormal"><span lang="EN-US" style="font-family:黑体"><b><font size="5" color="#FFFF00">3.
双哈希函数探测法<o:p>
</o:p>
</font></b></span></p>
<p class="MsoNormal"><font color="#FFFFFF" size="5"><b><span lang="EN-US"><span style="mso-spacerun: yes"> </span><span style="letter-spacing:.1pt">H<sub>i</sub>=(</span></span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt; letter-spacing: .1pt">Hash(key)+i*ReHash(key)</span><span lang="EN-US" style="letter-spacing:
.1pt">) mod m<span style="mso-spacerun: yes"> </span>(i=1</span><span style="font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman; letter-spacing: .1pt">,</span><span lang="EN-US" style="letter-spacing:.1pt">2</span><span style="font-family:宋体;mso-ascii-font-family:
"Times New Roman";mso-hansi-font-family:"Times New Roman";letter-spacing:.1pt">,…</span><span style="font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman; letter-spacing: .1pt">,</span><span lang="EN-US" style="letter-spacing:.1pt">m-1)<o:p>
</o:p>
</span></b></font></p>
<p class="MsoNormal"><span style="mso-spacerun: yes" lang="EN-US"><font size="5"><b><font color="#FFFFFF"> </font></b></font></span><font size="5"><b><font color="#FFFFFF"><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 color="#FFFFFF" size="5"><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><span lang="EN-US">ReHash(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 class="MsoNormal"><font color="#FFFFFF" size="5"><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></b></font></p>
</blockquote>
<p class="MsoNormal"><font color="#FFFFFF" size="5"><b><span style="mso-spacerun: yes" lang="EN-US">
</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">双哈希函数探测法，先用第一个函数</span><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><span lang="EN-US">ReHash(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 class="MsoNormal"><font color="#FFFFFF" size="5"><b><span style="mso-spacerun: yes" lang="EN-US">
</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">比如，</span><span lang="EN-US">Hash(key)=a</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">时产生地址冲突，就计算</span><span lang="EN-US">ReHash(key)=b</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:
"Times New Roman"">，则探测的地址序列为</span></b></font></p>
<blockquote>
<p style="margin-top: 0; margin-bottom: 0"><font color="#FFFFFF" size="5"><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">H<sub>1</sub>=(a+b)
mod m</span></b></font>
<p style="margin-top: 0; margin-bottom: 0"><font color="#FFFFFF" size="5"><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">H<sub>2</sub>=(a+2b)
mod m</span></b></font></p>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -