100165361.htm

来自「C#高级编程(第三版),顶死你们。。 。up」· HTM 代码 · 共 133 行 · 第 1/3 页

<p class="MsoNormal"><span style="FONT-FAMILY: 宋体">注意上图被简化了。每个键</span><span lang="EN-US">/</span><span style="FONT-FAMILY: 宋体">数据项对实际上并没有存储在字典结构的内部<span style="LETTER-SPACING: -1pt">&mdash;&mdash;</span></span><span style="LETTER-SPACING: -1pt"> </span><span style="FONT-FAMILY: 宋体">通常对于引用类型来说，存储的是对象引用，它们可以指定对象实际定位在堆的什么地方。</span></p>
<h4 style="FTEL: 21.45pt"><span lang="EN-US">3. </span><span style="FONT-FAMILY: 黑体">字典的工作情况</span></h4>
<p class="MsoNormal"><span style="FONT-FAMILY: 宋体">前面介绍了字典</span><span lang="EN-US">(</span><span style="FONT-FAMILY: 宋体">散列表</span><span lang="EN-US">)</span><span style="FONT-FAMILY: 宋体">使用起来非常方便，但这里有一个问题：</span><span lang="EN-US">Hashtable(</span><span style="FONT-FAMILY: 宋体">和其他字典类</span><span lang="EN-US">)</span><span style="FONT-FAMILY: 宋体">使用某种算法，根据键来确定每个对象的位置，实际上，该算法并不完全是由</span><span lang="EN-US">Hashtable</span><span style="FONT-FAMILY: 宋体">类提供的。它有两个部分，其中一个部分的代码必须由</span><span lang="EN-US">key</span><span style="FONT-FAMILY: 宋体">类来提供。如果使用一个</span><span lang="EN-US">Microsoft</span><span style="FONT-FAMILY: 宋体">提供的类，并把这个类用作键</span><span lang="EN-US">(</span><span style="FONT-FAMILY: 宋体">例如字符串</span><span lang="EN-US">)</span><span style="FONT-FAMILY: 宋体">，就不会有任何问题</span><span lang="EN-US">(Microsoft</span><span style="FONT-FAMILY: 宋体">已经编写了所有的代码</span><span lang="EN-US">)</span><span style="FONT-FAMILY: 宋体">，但如果</span><span lang="EN-US">key</span><span style="FONT-FAMILY: 宋体">类是自己编写的，就必须自己编写这部分算法。</span></p>
<p class="MsoNormal"><span style="FONT-FAMILY: 宋体">在计算机中，由</span><span lang="EN-US">key</span><span style="FONT-FAMILY: 宋体">类执行的部分算法称为散列</span><span lang="EN-US">(</span><span style="FONT-FAMILY: 宋体">因此字典也称为散列表</span><span lang="EN-US">)</span><span style="FONT-FAMILY: 宋体">，</span><span lang="EN-US">Hashtable</span><span style="FONT-FAMILY: 宋体">在散列算法中有非常特殊的地位：对象的</span><span lang="EN-US">GetHashCode()</span><span style="FONT-FAMILY: 宋体">方法，继承于</span><span lang="EN-US">System.Object</span><span style="FONT-FAMILY: 宋体">。只要字典类需要定位数据项的位置，就会调用键对象的</span><span lang="EN-US">GetHashCode()</span><span style="FONT-FAMILY: 宋体">方法。因此，在讨论</span><span lang="EN-US">System.Object()</span><span style="FONT-FAMILY: 宋体">时，我们强调如果重写了</span><span lang="EN-US">GetHashCode()</span><span style="FONT-FAMILY: 宋体">方法，就会对如何编写该重写方法有许多苛刻的要求。其原因是该重写方法必须以某种方式确保字典类能正常工作</span><span lang="EN-US">(</span><span style="FONT-FAMILY: 宋体">显然，如果在字典中，不把类当作键来使用，就不需要重写</span><span lang="EN-US">GetHashCode()</span><span style="FONT-FAMILY: 宋体">方法</span><span lang="EN-US">)</span><span style="FONT-FAMILY: 宋体">。</span></p>
<p class="MsoNormal"><span style="FONT-FAMILY: 宋体">其工作方式是</span><span lang="EN-US">GetHashCode()</span><span style="FONT-FAMILY: 宋体">返回一个</span><span lang="EN-US">int</span><span style="FONT-FAMILY: 宋体">类型的数据，它应使用这个键的值来生成该</span><span lang="EN-US">int</span><span style="FONT-FAMILY: 宋体">类型的数据。</span><span lang="EN-US">Hashtable</span><span style="FONT-FAMILY: 宋体">获取这个值，并对它进行其他一些操作，其中涉及到一些复杂的数学计算，最后返回一个索引，表示带有给定散列的数据项在字典中存储的位置。我们不详细介绍这部分算法，</span><span lang="EN-US">Microsoft</span><span style="FONT-FAMILY: 宋体">已经为这部分算法编写好了代码，所以不需要详细了解，但该算法使用素数，而且这就是散列表容量为什么应是一个素数的原因。</span></p>
<p class="MsoNormal"><a ftel="GetHashCode3"><span style="FONT-FAMILY: 宋体">为了使</span><span lang="EN-US">GetHashCode()</span></a><span style="FONT-FAMILY: 宋体">重写方法正常工作，有一些相当严格的要求。这些要求听起来相当抽象，难以理解，但不必太担心，</span><span lang="EN-US">MortimerPhonesEmployees</span><span style="FONT-FAMILY: 宋体">示例会对此进行说明，编写一个满足这些要求的</span><span lang="EN-US">key</span><span style="FONT-FAMILY: 宋体">类也不是那么困难：</span></p>
<p class="1" style="MARGIN-LEFT: 37.55pt; FTEL: -16.1pt"><span lang="EN-US">●<span style="FONT: 7pt &quot;Times New Roman&quot;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span></span><span style="FONT-FAMILY: 宋体">该方法应比较快</span><span lang="EN-US">(</span><span style="FONT-FAMILY: 宋体">因为在字典中放置或获取数据项要求比较快</span><span lang="EN-US">)</span><span style="FONT-FAMILY: 宋体">。</span></p>
<p class="1" style="MARGIN-LEFT: 37.55pt; FTEL: -16.1pt"><span lang="EN-US">●<span style="FONT: 7pt &quot;Times New Roman&quot;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span></span><span style="FONT-FAMILY: 宋体">该方法应比较一致，如果两个键表示相同的值，那么它们必须为散列提供相同的值。</span></p>
<p class="1" style="MARGIN-LEFT: 37.55pt; FTEL: -16.1pt"><span lang="EN-US">●<span style="FONT: 7pt &quot;Times New Roman&quot;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span></span><span style="FONT-FAMILY: 宋体">该方法给出的值最好能平均分布在</span><span lang="EN-US">int</span><span style="FONT-FAMILY: 宋体">可以存储的数字的整个范围内。</span></p>
<p class="MsoNormal"><span style="FONT-FAMILY: 宋体">最后一个条件的原因是有一个潜在的问题：如果在字典中，两个数据项的散列有相同的索引，该怎么办？</span></p>
<p class="MsoNormal"><span style="FONT-FAMILY: 宋体">如果发生这种情况，字典类就必须寻找最近的可利用的自由单元来存储第二个数据项，必须进行一定的搜索，以便以后获取这个条目。这显然这会降低性能，如果许多键都有相同的索引，就有可能出现崩溃。根据</span><span lang="EN-US">Microsoft</span><span style="FONT-FAMILY: 宋体">的部分算法的工作方式，在计算出来的散列值平均分布在</span><span lang="EN-US">int.MinValue</span><span style="FONT-FAMILY: 宋体">和</span><span lang="EN-US"> int.MaxValue</span><span style="FONT-FAMILY: 宋体">之间时，这种崩溃的危险会降低到最小。</span></p>
<p class="MsoNormal"><span style="FONT-FAMILY: 宋体">字典的元素越多，键之间的崩溃危险也越大，所以最好确保字典的容量大于其中的元素个数。因此，在字典被填满前，</span><span lang="EN-US">Hashtable</span><span style="FONT-FAMILY: 宋体">会自动重新分配内存，增大其容量。表被填满的比例称为负载</span><span lang="EN-US">(load)</span><span style="FONT-FAMILY: 宋体">，可以为这个负载设置一个最大值，在另一个</span><span lang="EN-US">Hashtable</span><span style="FONT-FAMILY: 宋体">构造函数中给</span><span lang="EN-US">Hashtable</span><span style="FONT-FAMILY: 宋体">重新分配内存前，该负载会达到这个最大值：</span></p>
<p class="2" style="MARGIN-TOP: 8.15pt; MARGIN-LEFT: 21.45pt; MARGIN-RIGHT: 0cm; FTEL: 18.45pt"><span lang="EN-US">// capacity =50, Max Load = 0.5</span></p>
<p class="2" style="MARGIN-LEFT: 21.45pt; FTEL: 18.45pt"><span lang="EN-US">&nbsp;</span></p>
<p class="2" style="MARGIN-TOP: 0cm; MARGIN-LEFT: 21.45pt; MARGIN-RIGHT: 0cm; FTEL: 18.45pt"><span lang="EN-US">Hashtable employees = new Hashtable(50, 0.5);</span></p>
<p class="MsoNormal"><span style="FONT-FAMILY: 宋体">负载的最大值越小，散列表的工作效率就越高，但它占据的内存也越大。当散列表为了增大其容量而重新分配内存时，总会选择一个素数作为其新容量。</span></p>
<p class="MsoNormal"><span style="FONT-FAMILY: 宋体">上面列出的另一个要点是，散列算法必须一致。如果两个对象包含相同的数据，它们就必须给出相同的散列值，这就是重写</span><span lang="EN-US">System.Object</span><span style="FONT-FAMILY: 宋体">的</span><span lang="EN-US">Equals()</span><span style="FONT-FAMILY: 宋体">和</span><span lang="EN-US"> GetHashCode()</span><span style="FONT-FAMILY: 宋体">方法时必须考虑的重要限制，</span><span lang="EN-US">Hashtable</span><span style="FONT-FAMILY: 宋体">确定两个键</span><span lang="EN-US">A</span><span style="FONT-FAMILY: 宋体">和</span><span lang="EN-US">B</span><span style="FONT-FAMILY: 宋体">是否相等的方式是调用</span><span lang="EN-US">A.Equals(B)</span><span style="FONT-FAMILY: 宋体">，即必须确保下述条件：</span></p>
<p class="a1" style="MARGIN-TOP: 8.15pt; MARGIN-LEFT: 0cm; MARGIN-RIGHT: 0cm; FTEL: 21.45pt"><span style="FONT-FAMILY: 楷体_GB2312">如果</span><span lang="EN-US">A.Equals(B)</span><span style="FONT-FAMILY: 楷体_GB2312">是</span><span lang="EN-US">true</span><span style="FONT-FAMILY: 楷体_GB2312">，则</span><span lang="EN-US">A.GetHashCode()</span><span style="FONT-FAMILY: 楷体_GB2312">和</span><span lang="EN-US">B.GetHashCode()</span><span style="FONT-FAMILY: 楷体_GB2312">必须返回相同的散列。</span></p>
<p class="MsoNormal"><span style="FONT-FAMILY: 宋体">这看起来可能非常微妙，但非常重要。如果重写这些方法的方式不能保证上述语句为</span><span lang="EN-US">true</span><span style="FONT-FAMILY: 宋体">，用这个类实例作为键的散列表就不能正常工作。例如，把一个对象放在散列表中，但从来没有获取过它，或者试图获取一个数据项，但会返回错误的数据项。</span></p>
<p class="a3" style="MARGIN-TOP: 8.15pt; FTEL: 21.45pt"><span style="FONT-FAMILY: 黑体">注意：</span></p>
<p class="a1" style="FTEL: 21.45pt"><span style="FONT-FAMILY: 楷体_GB2312">因此，如果为</span><span lang="EN-US">Equals()</span><span style="FONT-FAMILY: 楷体_GB2312">提供了一个重写方法，但没有为</span><span lang="EN-US">GetHashCode()</span><span style="FONT-FAMILY: 楷体_GB2312">提供重写方法，</span><span lang="EN-US">C#</span><span style="FONT-FAMILY: 楷体_GB2312">编译器就会显示一个编译警告。</span></p>
<p class="MsoNormal"><span style="FONT-FAMILY: 宋体">对于</span><span lang="EN-US">System.Object</span><span style="FONT-FAMILY: 宋体">，这个条件是</span><span lang="EN-US">true</span><span style="FONT-FAMILY: 宋体">，因为</span><span lang="EN-US">Equals()</span><span style="FONT-FAMILY: 宋体">仅比较引用，</span><span lang="EN-US">GetHashCode()</span><span style="FONT-FAMILY: 宋体">会根据对象的地址返回一个散列，则基于键的散列表没有重写这些方法，将正常工作。但是，这种方式也有问题，只有键是相同的对象时，才是相等的。当把一个对象放在字典中时，就必须挂起键的引用。以后也不能实例化另一个有相同值的键对象，因为相同的值被定义为表示相同的实例。如果没有重写</span><span lang="EN-US">Equals() </span><span style="FONT-FAMILY: 宋体">和</span><span lang="EN-US"> GetHashCode()</span><span style="FONT-FAMILY: 宋体">的</span><span lang="EN-US">Object</span><span style="FONT-FAMILY: 宋体">版本，类就不能在散列表中方便地使用。因此，应根据键的值来执行</span><span lang="EN-US">GetHashCode()</span><span style="FONT-FAMILY: 宋体">，生成一个散列，而不是根据内存中的地址来执行该方法，这就是必须为要用作键的类重写</span><span lang="EN-US">Equals() </span><span style="FONT-FAMILY: 宋体">和</span><span lang="EN-US"> GetHashCode()</span><span style="FONT-FAMILY: 宋体">的原因。</span></p>
<p class="MsoNormal"><span lang="EN-US">System.String</span><span style="FONT-FAMILY: 宋体">有</span><span lang="EN-US">3</span><span style="FONT-FAMILY: 宋体">个重载方法，重载</span><span lang="EN-US">Equals()</span><span style="FONT-FAMILY: 宋体">提供了值的比较，</span><span lang="EN-US">GetHashCode()</span><span style="FONT-FAMILY: 宋体">也被相应地重载，根据字符串的值返回一个散列。因此，字典中把字符串用作键是非常方便的。</span></p></div>
                <!-- page -->
                <div class="page" style="text-align: center">
                    <a href="100165360.htm">上一页</a>&nbsp;&nbsp;&nbsp;<a href="index.html">首页</a>&nbsp;&nbsp;&nbsp;<a href="100165362.htm">下一页</a>
                </div>
                <div style="margin: 0px auto; width: 700px; border: solid 1px #0b5f98;">
                    <div style="float: left; width: 16px; background-color: #0b5f98; color: White; padding: 1px;">
                        图书导读
                    </div>
                    <div style="float: right; width: 670px; text-align: left; line-height: 16pt; padding-left: 2px">
                        <!--导读-->
                        <h1 id="divCurrentNode2" style="color: #b83507; width: 100%; text-align: left; font-size: 12px; padding-left: 2px">当前章节:<a href='100165361.htm'><font color='red'>9.1.3  字典(1)</font></a></h1>
                        <div id="divRealteNod2" style="padding-left: 2px">
                        <div style='float:left;width:49%'>·<a href='100165358.htm'>9.1  对象组</a></div><div style='float:right;width:49%'>·<a href='100165359.htm'>9.1.1  数组列表</a></div><div style='float:left;width:49%'>·<a href='100165360.htm'>9.1.2  集合</a></div><div style='float:right;width:49%'>·<a href='100165362.htm'>9.1.3  字典(2)</a></div><div style='float:left;width:49%'>·<a href='100165363.htm'>9.2  小结</a></div><div style='float:right;width:49%'>·<a href='100165364.htm'>10.1  定制特性</a></div></div>
                    </div>
                </div>
                </div>
        </div>
</body>
</html>