📄 ds9.4.4.htm
字号:
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312">
<meta name="GENERATOR" content="Microsoft FrontPage 4.0">
<meta name="ProgId" content="FrontPage.Editor.Document">
<title>数 据 结 构</title>
<meta name="Microsoft Theme" content="hounk 010">
</head>
<body background bgcolor="#000099" text="#CCCC99" link="#FF9900" vlink="#996600" alink="#FF3300">
<!--mstheme--><font face="宋体"><p:colorscheme
colors="#0000FF,#FFFFFF,#000000,#FFCC66,#00FFFF,#3366FF,#FF0033,#FFFF00"/>
<p align="left"><font size="5" color="#FFFFFF"><span style="mso-bidi-font-size: 10.0pt; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA"><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">9.4.4
</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></span></font></p>
<p class="MsoNormal"><b><font size="5" color="#FFFFFF"><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></font></b></p>
<p class="MsoNormal"><b><font size="5" color="#FFFFFF"><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></font></b></p>
<blockquote>
<p class="MsoNormal" style="margin-top: 0; margin-bottom: 0"><b><font size="5" color="#FFFFFF"><span lang="EN-US">1.
</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 style="mso-spacerun: yes"> </span></span></font></b></p>
<p class="MsoNormal" style="margin-top: 0; margin-bottom: 0"><b><font size="5" color="#FFFFFF"><span lang="EN-US">2.
</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 style="mso-spacerun: yes"> </span></span></font></b></p>
<p class="MsoNormal" style="margin-top: 0; margin-bottom: 0"><b><font size="5" color="#FFFFFF"><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></font></b></p>
</blockquote>
<p class="MsoNormal"><b><font size="5" color="#FFFFFF"><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></font></b></p>
<p class="MsoNormal"><b><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman""><font color="#FFFFFF" size="4">线性探测法的平均查找长度</font></span><font size="5" color="#FFFFFF"><span lang="EN-US">
ASL=(5</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">×</span><span lang="EN-US">1+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">2+1</span><span style="font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">×</span><span lang="EN-US">4)/9=5/3</span></font></b></p>
<p class="MsoNormal"><b><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman""><font color="#FFFFFF" size="4">二次探测法的平均查找长度</font></span><font size="5" color="#FFFFFF"><span lang="EN-US">
ASL=(5</span><span style="font-family:宋体;mso-ascii-font-family:"Times New Roman";
mso-hansi-font-family:"Times New Roman"">×</span><span lang="EN-US">1+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">2+1</span><span style="font-family:
宋体;mso-ascii-font-family:"Times New Roman";mso-hansi-font-family:"Times New Roman"">×</span><span lang="EN-US">2)/9=13/9</span></font></b></p>
<p class="MsoNormal" style="line-height: 100%; mso-line-height-rule: exactly; margin-top: 0; margin-bottom: 0"><b><span lang="EN-US" style="mso-bidi-font-size: 10.0pt"><font size="5" color="#FFFFFF"> </font></span><font size="5" color="#FFFFFF"><span style="mso-spacerun: yes; mso-bidi-font-size: 10.0pt" lang="EN-US"> </span><span style="mso-bidi-font-size: 10.0pt; mso-spacerun: yes" 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">填入表中的元素个数</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt"><o:p>
</o:p>
</span></font></b></p>
<p class="MsoNormal" style="line-height: 100%; mso-line-height-rule: exactly; margin-top: 0; margin-bottom: 0"><b><font size="5" color="#FFFFFF"><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman">哈希表的装填因子定义为：α</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt">=
</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">───────────</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt"><o:p>
</o:p>
</span></font></b></p>
<p class="MsoNormal" style="line-height: 100%; mso-line-height-rule: exactly; margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b><span style="mso-spacerun: yes; mso-bidi-font-size: 10.0pt" lang="EN-US">
</span></b><span lang="EN-US" style="mso-bidi-font-size: 10.0pt"><b><span style="mso-spacerun:
yes"> </span><span style="mso-spacerun: yes">
</span></b></span><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">哈希表的长度</span><span lang="EN-US" style="mso-bidi-font-size: 10.0pt"><o:p>
</o:p>
</span></b></font></p>
<p class="MsoNormal"><span lang="EN-US"><b><font size="5" color="#FFFFFF"> </font></b></span><b><font size="5" color="#FFFFFF"><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></font></b><span lang="EN-US"><b><font size="5" color="#FFFFFF"> <o:p>
</o:p>
</font></b></span></p>
<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"><font size="5" color="#FFFFFF">
实际上，哈希表的平均查找长度是装填因子α的函数，只是不同处理冲突的方法有不同的函数。以下给出几种不同处理冲突方法的平均查找长度：</font></span></b>
<p align="center"><img border="0" src="ds9.4.4.gif"></p>
<p align="left"> </p>
<p align="center"><b><font size="5"><a href="ds9.4.HTM"><font color="#FFFF00">返回</font></a></font></b></p>
<!--mstheme--></font>
</body>
</html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -