100165361.htm

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

            <div id="main">
                <div id="text"> <link href="css.css" rel="stylesheet" type="text/css" /><h3 style="MARGIN-TOP: 8.15pt; MARGIN-LEFT: 0cm; MARGIN-RIGHT: 0cm; FTEL: 8.15pt"><span lang="EN-US">9.1.3&nbsp; </span><span style="FONT-FAMILY: 黑体">字典</span></h3>
<p class="MsoNormal" style="LINE-HEIGHT: 15pt"><a ftel="dictionaries"><span style="FONT-FAMILY: 宋体">字典表示一种非常复杂的数据结构，这种数据结构允许按照某个键来访问元素，这个键可以是任意数据类型。字典还可以称为映射或散列表。在希望把对象保存为数组，但希望使用其他数据类型</span><span lang="EN-US">(</span></a><span style="FONT-FAMILY: 宋体">不是数字类型</span><span lang="EN-US">)</span><span style="FONT-FAMILY: 宋体">来给结构建立索引时，字典是非常适合的。也可以向字典自由添加和删除元素，这有点像</span><span lang="EN-US">ArrayList</span><span style="FONT-FAMILY: 宋体">。但没有改变内存中后续数据项的性能开销。</span></p>
<p class="MsoNormal" style="LINE-HEIGHT: 15pt"><span style="FONT-FAMILY: 宋体">下面介绍字典的使用场合，本节后面会举一个示例</span><span lang="EN-US">MortimerPhonesEmployees</span><span style="FONT-FAMILY: 宋体">来说明。这个示例假定</span><span lang="EN-US">Mortimer Phones(</span><span style="FONT-FAMILY: 宋体">这是第</span><span lang="EN-US">3</span><span style="FONT-FAMILY: 宋体">章介绍的移动电话公司</span><span lang="EN-US">)</span><span style="FONT-FAMILY: 宋体">用某个软件处理其员工的信息。为此需要一个数据结构，它有点像数组，其中包含员工的数据，假定每个</span><span lang="EN-US">Mortimer Phones</span><span style="FONT-FAMILY: 宋体">员工都用一个员工</span><span lang="EN-US">ID</span><span style="FONT-FAMILY: 宋体">来标识，这个员工</span><span lang="EN-US">ID</span><span style="FONT-FAMILY: 宋体">是一组字符，例如</span><span lang="EN-US">B342 </span><span style="FONT-FAMILY: 宋体">或</span><span lang="EN-US"> W435</span><span style="FONT-FAMILY: 宋体">，存储在</span><span lang="EN-US">EmployeeID</span><span style="FONT-FAMILY: 宋体">对象中，员工的信息则存储在</span><span lang="EN-US">EmployeeData</span><span style="FONT-FAMILY: 宋体">对象中，本例只包含员工的</span><span lang="EN-US">ID</span><span style="FONT-FAMILY: 宋体">、姓名和薪水。</span></p>
<p class="MsoNormal" style="LINE-HEIGHT: 15pt"><span style="FONT-FAMILY: 宋体">假定有下述</span><span lang="EN-US">EmployeeID</span><span style="FONT-FAMILY: 宋体">：</span></p>
<p class="2" style="MARGIN-TOP: 6.5pt; MARGIN-LEFT: 21.45pt; MARGIN-RIGHT: 0cm; FTEL: 18.45pt"><span lang="EN-US">EmployeeID id = new EmployeeID(&quot;W435&quot;);</span></p>
<p class="MsoNormal"><span style="FONT-FAMILY: 宋体">有一个变量</span><span lang="EN-US">employees</span><span style="FONT-FAMILY: 宋体">，在语法上，我们可以把这个变量当作</span><span lang="EN-US">EmployeeData</span><span style="FONT-FAMILY: 宋体">对象的一个数组。但在实际上，它并不是一个数组，而是一个字典，因此，可以使用上面声明的</span><span lang="EN-US">ID</span><span style="FONT-FAMILY: 宋体">获得员工的信息，如下所示。</span></p>
<p class="2" style="MARGIN-TOP: 6.5pt; MARGIN-LEFT: 21.45pt; MARGIN-RIGHT: 0cm; FTEL: 18.45pt"><span lang="EN-US">EmployeeData theEmployee = employees[id];</span></p>
<p class="2" style="MARGIN-TOP: 0cm; MARGIN-LEFT: 21.45pt; MARGIN-RIGHT: 0cm; FTEL: 18.45pt"><span lang="EN-US">&nbsp;&nbsp; // Note that id is NOT a numeric type &ndash; it is an EmployeeID instance</span></p>
<p class="MsoNormal" style="LINE-HEIGHT: 15pt"><span style="FONT-FAMILY: 宋体">这就是字典的功能。它看起来像一个数组</span><span lang="EN-US">(</span><span style="FONT-FAMILY: 宋体">实际上比数组更强大，它更像一个</span><span lang="EN-US">ArrayList</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">ID</span><span style="FONT-FAMILY: 宋体">对象</span><span lang="EN-US">)</span><span style="FONT-FAMILY: 宋体">时，字典就会使用这个键，还可以对这个键的值进行某些处理，这种处理会根据键的值返回一个整数，用于确定在&ldquo;数组&rdquo;中，元素应存储在什么地方，或从什么地方获取。使用字典来存储对象的其他场合有：</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">US</span><span style="FONT-FAMILY: 宋体">社会安全号在理论上的最大值是</span><span lang="EN-US">999999999</span><span style="FONT-FAMILY: 宋体">。在</span><span lang="EN-US">32</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">USA</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="MsoNormal" style="LINE-HEIGHT: 15pt"><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">MortimerPhonesEmployees</span><span style="FONT-FAMILY: 宋体">示例，它说明了如何使用字典，以及如何建立一个类，把它用作一个键。</span></p>
<h4 style="FTEL: 21.45pt"><span lang="EN-US">1. </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">(</span><span style="FONT-FAMILY: 宋体">或翻译</span><span lang="EN-US">)</span><span style="FONT-FAMILY: 宋体">就是我们感兴趣的数据。大的字典会有成千上万个条目，在查找单词的含义时，使用这样的字典肯定可以查到，因为我们是按照字母顺序查找的。此时，要查找的单词就相当于用于获取自己感兴趣的数据的键。我们对单词本身并不像与之相关的数据那样感兴趣。这个单词只提供了查找字典中条目的方式，因此，要建立一个字典，要做</span><span lang="EN-US">3</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></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="MsoNormal"><span style="FONT-FAMILY: 宋体">算法是字典的重要部分。只知道键是不够的，还需要一种方式，利用键来确定数据结构中条目的位置。在现实生活中的字典里，这种算法就是以字母顺序来排列单词。</span></p>
<h4 style="FTEL: 21.45pt"><span lang="EN-US">2. .NET</span><span style="FONT-FAMILY: 黑体">中的字典</span></h4>
<p class="MsoNormal"><a ftel="Hashtable1"><span style="FONT-FAMILY: 宋体">在</span><span lang="EN-US">.NET</span></a><span style="FONT-FAMILY: 宋体">中，基本的字典是由类</span><span lang="EN-US">Hashtable</span><span style="FONT-FAMILY: 宋体">来表示的，它遵循现实生活中字典的规则，但假定键和条目都是</span><span lang="EN-US">Object</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">Microsoft</span><span style="FONT-FAMILY: 宋体">提供了一个抽象基类</span><span lang="EN-US">DictionaryBase</span><span style="FONT-FAMILY: 宋体">，它具有基本的字典功能，从中可以派生自己的字典类。还有一个已建立好的</span><span lang="EN-US">.NET</span><span style="FONT-FAMILY: 宋体">基类</span><span lang="EN-US">System.Collections.Specialized.StringDictionary</span><span style="FONT-FAMILY: 宋体">，如果键是字符串，就可以使用它来代替</span><span lang="EN-US">Hashtable</span><span style="FONT-FAMILY: 宋体">。</span></p>
<p class="MsoNormal"><span style="FONT-FAMILY: 宋体">与</span><span lang="EN-US">StringBuilder</span><span style="FONT-FAMILY: 宋体">和</span><span lang="EN-US"> ArrayList</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">Hashtable employees = new Hashtable(53);</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">53</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">Add()</span><span style="FONT-FAMILY: 宋体">，但</span><span lang="EN-US">Hashtable.Add()</span><span style="FONT-FAMILY: 宋体">带有两个参数，它们都是对象引用。第一个参数是对键的引用，第二个参数是对数据的引用。在后面的示例中，对</span><span lang="EN-US">EmployeeID</span><span style="FONT-FAMILY: 宋体">和</span><span lang="EN-US"> EmployeeData</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">EmployeeID id; </span></p>
<p class="2" style="MARGIN-LEFT: 21.45pt; FTEL: 18.45pt"><span lang="EN-US">EmployeeData data;</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-LEFT: 21.45pt; FTEL: 18.45pt"><span lang="EN-US">// initialize id and data to refer to some employee</span></p>
<p class="2" style="MARGIN-LEFT: 21.45pt; FTEL: 18.45pt"><span lang="EN-US">// assume employees is a Hashtable instance </span></p>
<p class="2" style="MARGIN-LEFT: 21.45pt; FTEL: 18.45pt"><span lang="EN-US">//that contains EmployeeData references </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">employees.Add(id, data);</span></p>
<p class="MsoNormal"><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">EmployeeData data = employees[id];</span></p>
<p class="MsoNormal"><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">employees.Remove(id);</span></p>
<p class="MsoNormal"><span style="FONT-FAMILY: 宋体">使用</span><span lang="EN-US">Count</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">int nEmployees = employees.Count;</span></p>
<p class="MsoNormal"><span style="FONT-FAMILY: 宋体">但要注意，字典中没有</span><span lang="EN-US">Insert()</span><span style="FONT-FAMILY: 宋体">方法。我们还没有介绍字典的内部工作情况，但添加数据和插入数据没有什么区别。与数组和</span><span lang="EN-US">ArrayList</span><span style="FONT-FAMILY: 宋体">不同，在结构的开头没有一个大的数据块，在其尾部，也没有空的数据块。而在字典中，没有标记的的部分都是空的，如图</span><span lang="EN-US">9-1</span><span style="FONT-FAMILY: 宋体">所示。</span></p>
<p align="center"><span lang="EN-US"><img height="192" src="09/image001.gif" width="146" alt="" /></span></p>
<p style="FTEL: 8.15pt" align="center"><span style="FONT-FAMILY: 宋体">图</span><span lang="EN-US">&nbsp; 9-1</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">GetHashCode()</span><span style="FONT-FAMILY: 宋体">方法即可。</span></p>