C#教程（四十六） 字典(1)

字典表示一种非常复杂的数据结构，这种数据结构允许按照某个键来访问元素，这个键可以是任意数据类型。字典还可以称为映射或散列表。在希望把对象保存为数组，但希望使用其他数据类型(不是数字类型)来给结构建立索引时，字典是非常适合的。也可以向字典自由添加和删除元素，这有点像ArrayList。但没有改变内存中后续数据项的性能开销。

下面介绍字典的使用场合，本节后面会举一个示例MortimerPhonesEmployees来说明。这个示例假定Mortimer Phones(这是第3章介绍的移动电话公司)用某个软件处理其员工的信息。为此需要一个数据结构，它有点像数组，其中包含员工的数据，假定每个Mortimer Phones员工都用一个员工ID来标识，这个员工ID是一组字符，例如B342 或 W435，存储在EmployeeID对象中，员工的信息则存储在EmployeeData对象中，本例只包含员工的ID、姓名和薪水。

假定有下述EmployeeID：

EmployeeID id = new EmployeeID("W435");

有一个变量employees，在语法上，我们可以把这个变量当作EmployeeData对象的一个数组。但在实际上，它并不是一个数组，而是一个字典，因此，可以使用上面声明的ID获得员工的信息，如下所示。

EmployeeData theEmployee = employees[id];

// Note that id is NOT a numeric type – it is an EmployeeID instance

这就是字典的功能。它看起来像一个数组(实际上比数组更强大，它更像一个ArrayList，因为可以动态设置它的容量，添加或删除其元素)，但不必用整数给它建立索引，而可以使用任意数据类型来建立索引。对于字典，这称为键，而不是索引。粗略地讲，在访问字典中的元素(在前面的例子中就是ID对象)时，字典就会使用这个键，还可以对这个键的值进行某些处理，这种处理会根据键的值返回一个整数，用于确定在“数组”中，元素应存储在什么地方，或从什么地方获取。使用字典来存储对象的其他场合有：

● 可以存储员工或其他人的信息，用他们的社会安全号作为索引。社会安全号码基本上是一个整数，但不能使用数组，并把社会安全号作为索引，因为US社会安全号在理论上的最大值是999999999。在32位系统上，不能在程序中给数组分配这么大的地址空间！数组的大部分元素都是空的。而使用字典，可以用社会安全号来为员工建立索引，且字典占据的空间较小。

● 可以存储地址，索引是邮政编码。在USA，邮政编码都是数字，但在加拿大和英国，邮政编码是包含字母和数字的字符串。

● 可以存储对象或人的任何数据，其索引是对象或人的名字。

尽管字典的作用是使客户机代码看起来更像一个动态的数组，有非常灵活的索引机制，但在后台要做许多工作才能实现这个功能。大体上，任何类的对象都可以用作字典的索引键，但在此之前，需要对类执行某些功能，通常要执行方法GetHashCode()，所有的类和结构都从System.Object继承了这个方法。本节将详细讨论字典，它的工作原理和GetHashCode()的调用方式。然后介绍MortimerPhonesEmployees示例，它说明了如何使用字典，以及如何建立一个类，把它用作一个键。

1. 现实生活中的字典
使用字典这个名称，是因为其数据结构非常类似于现实生活中的字典。在一本字典中，通常可以查找某个单词的含义(在外语字典中，则可以查找一个单词的汉译)；给出含义的几行文本(或翻译)就是我们感兴趣的数据。大的字典会有成千上万个条目，在查找单词的含义时，使用这样的字典肯定可以查到，因为我们是按照字母顺序查找的。此时，要查找的单词就相当于用于获取自己感兴趣的数据的键。我们对单词本身并不像与之相关的数据那样感兴趣。这个单词只提供了查找字典中条目的方式，因此，要建立一个字典，要做3件事：

● 要查找的数据

● 键

● 在字典中查找数据的算法

算法是字典的重要部分。只知道键是不够的，还需要一种方式，利用键来确定数据结构中条目的位置。在现实生活中的字典里，这种算法就是以字母顺序来排列单词。

2. .NET中的字典
在.NET中，基本的字典是由类Hashtable来表示的，它遵循现实生活中字典的规则，但假定键和条目都是Object类型。散列表可以存储各种数据结构，而现实生活中的字典只使用字符串作为它的键。

虽然Hashtable表示可以存储任何东西的一般字典，但也可以定义自己的更具体化的字典类。Microsoft提供了一个抽象基类DictionaryBase，它具有基本的字典功能，从中可以派生自己的字典类。还有一个已建立好的.NET基类System.Collections.Specialized.StringDictionary，如果键是字符串，就可以使用它来代替Hashtable。

与StringBuilder和 ArrayList一样，在创建Hashtable对象时，可以指定它的原始容量：

Hashtable employees = new Hashtable(53);

与往常一样，Hashtable有许多其他的构造函数，但这是最常用的一个，注意在此选择了一个不太常见的最初容量53，其原因是在字典中使用内部算法时，如果容量是一个素数，它们的工作效率最高。

给Hashtable添加一个对象，要使用方法Add()，但Hashtable.Add()带有两个参数，它们都是对象引用。第一个参数是对键的引用，第二个参数是对数据的引用。在后面的示例中，对EmployeeID和 EmployeeData类执行这个方法，如下所示：

EmployeeID id;

EmployeeData data;



// initialize id and data to refer to some employee

// assume employees is a Hashtable instance

//that contains EmployeeData references



employees.Add(id, data);

为了获取一个数据项中的数据，需要提供键。Hashtable执行一个索引符，这样才能获取数据，这就是前面介绍的获取数组的语法：

EmployeeData data = employees[id];

还可以从字典中删除数据项，这也要提供被删除的对象的键：

employees.Remove(id);

使用Count属性，可以确定在散列表中有多少个条目：

int nEmployees = employees.Count;

但要注意，字典中没有Insert()方法。我们还没有介绍字典的内部工作情况，但添加数据和插入数据没有什么区别。与数组和ArrayList不同，在结构的开头没有一个大的数据块，在其尾部，也没有空的数据块。而在字典中，没有标记的的部分都是空的，如图9-1所示。



图 9-1

当添加一个数据项时，该数据项会放在字典的任何位置。在使用字典时，不需要知道如何根据键来确定这个位置。重要的是，用于确定数据项的位置的算法应非常可靠，只要记住键是什么，就可以把这个键传送给Hashtable对象，该对象就可以使用这个键快速确定数据项的位置，并获取该数据项。本节的后面会介绍这个算法的工作方式。现在只要知道它使用了键的GetHashCode()方法即可。

注意上图被简化了。每个键/数据项对实际上并没有存储在字典结构的内部—— 通常对于引用类型来说，存储的是对象引用，它们可以指定对象实际定位在堆的什么地方。

3. 字典的工作情况
前面介绍了字典(散列表)使用起来非常方便，但这里有一个问题：Hashtable(和其他字典类)使用某种算法，根据键来确定每个对象的位置，实际上，该算法并不完全是由Hashtable类提供的。它有两个部分，其中一个部分的代码必须由key类来提供。如果使用一个Microsoft提供的类，并把这个类用作键(例如字符串)，就不会有任何问题(Microsoft已经编写了所有的代码)，但如果key类是自己编写的，就必须自己编写这部分算法。

在计算机中，由key类执行的部分算法称为散列(因此字典也称为散列表)，Hashtable在散列算法中有非常特殊的地位：对象的GetHashCode()方法，继承于System.Object。只要字典类需要定位数据项的位置，就会调用键对象的GetHashCode()方法。因此，在讨论System.Object()时，我们强调如果重写了GetHashCode()方法，就会对如何编写该重写方法有许多苛刻的要求。其原因是该重写方法必须以某种方式确保字典类能正常工作(显然，如果在字典中，不把类当作键来使用，就不需要重写GetHashCode()方法)。

其工作方式是GetHashCode()返回一个int类型的数据，它应使用这个键的值来生成该int类型的数据。Hashtable获取这个值，并对它进行其他一些操作，其中涉及到一些复杂的数学计算，最后返回一个索引，表示带有给定散列的数据项在字典中存储的位置。我们不详细介绍这部分算法，Microsoft已经为这部分算法编写好了代码，所以不需要详细了解，但该算法使用素数，而且这就是散列表容量为什么应是一个素数的原因。

为了使GetHashCode()重写方法正常工作，有一些相当严格的要求。这些要求听起来相当抽象，难以理解，但不必太担心，MortimerPhonesEmployees示例会对此进行说明，编写一个满足这些要求的key类也不是那么困难：

● 该方法应比较快(因为在字典中放置或获取数据项要求比较快)。

● 该方法应比较一致，如果两个键表示相同的值，那么它们必须为散列提供相同的值。

● 该方法给出的值最好能平均分布在int可以存储的数字的整个范围内。

最后一个条件的原因是有一个潜在的问题：如果在字典中，两个数据项的散列有相同的索引，该怎么办？

如果发生这种情况，字典类就必须寻找最近的可利用的自由单元来存储第二个数据项，必须进行一定的搜索，以便以后获取这个条目。这显然这会降低性能，如果许多键都有相同的索引，就有可能出现崩溃。根据Microsoft的部分算法的工作方式，在计算出来的散列值平均分布在int.MinValue和 int.MaxValue之间时，这种崩溃的危险会降低到最小。

字典的元素越多，键之间的崩溃危险也越大，所以最好确保字典的容量大于其中的元素个数。因此，在字典被填满前，Hashtable会自动重新分配内存，增大其容量。表被填满的比例称为负载(load)，可以为这个负载设置一个最大值，在另一个Hashtable构造函数中给Hashtable重新分配内存前，该负载会达到这个最大值：

// capacity =50, Max Load = 0.5



Hashtable employees = new Hashtable(50, 0.5);

负载的最大值越小，散列表的工作效率就越高，但它占据的内存也越大。当散列表为了增大其容量而重新分配内存时，总会选择一个素数作为其新容量。

上面列出的另一个要点是，散列算法必须一致。如果两个对象包含相同的数据，它们就必须给出相同的散列值，这就是重写System.Object的Equals()和 GetHashCode()方法时必须考虑的重要限制，Hashtable确定两个键A和B是否相等的方式是调用A.Equals(B)，即必须确保下述条件：

如果A.Equals(B)是true，则A.GetHashCode()和B.GetHashCode()必须返回相同的散列。

这看起来可能非常微妙，但非常重要。如果重写这些方法的方式不能保证上述语句为true，用这个类实例作为键的散列表就不能正常工作。例如，把一个对象放在散列表中，但从来没有获取过它，或者试图获取一个数据项，但会返回错误的数据项。

注意：

因此，如果为Equals()提供了一个重写方法，但没有为GetHashCode()提供重写方法，C#编译器就会显示一个编译警告。

对于System.Object，这个条件是true，因为Equals()仅比较引用，GetHashCode()会根据对象的地址返回一个散列，则基于键的散列表没有重写这些方法，将正常工作。但是，这种方式也有问题，只有键是相同的对象时，才是相等的。当把一个对象放在字典中时，就必须挂起键的引用。以后也不能实例化另一个有相同值的键对象，因为相同的值被定义为表示相同的实例。如果没有重写Equals() 和 GetHashCode()的Object版本，类就不能在散列表中方便地使用。因此，应根据键的值来执行GetHashCode()，生成一个散列，而不是根据内存中的地址来执行该方法，这就是必须为要用作键的类重写Equals() 和 GetHashCode()的原因。

System.String有3个重载方法，重载Equals()提供了值的比较，GetHashCode()也被相应地重载，根据字符串的值返回一个散列。因此，字典中把字符串用作键是非常方便的。

C#教程（四十五） 集合

集合表示一组可以通过遍历每个元素来访问的一组对象，特别是可以使用foreach循环来访问它们。换言之，编写下面的代码时，假定变量MessageSet是一个集合：

foreach (string nextMessage in messageSet)

{

DoSomething(nextMessage);

}

使用foreach循环是集合的主要目的，集合没有提供其他特性。

下面将详细介绍集合，并把前面开发的Vector示例转换为一个集合。集合的概念很广，实际上它并不是.NET的新增内容，而是COM的一部分，在Visual Basic 6中得到使用，其语法是For…Each，非常方便。Java也有一个foreach循环，其底层的结构非常类似于.NET集合。

1. 集合的概念
对象如果可以提供相关对象的引用，就是一个集合，称为枚举，它可以遍历集合中的数据项。更专业的说法是集合必须实现接口System.Collections.IEnumerable。IEnumerable只定义了一个方法，如下所示。

interface IEnumerable

{

IEnumerator GetEnumerator();

}

GetEnumerator()的目的是返回枚举对象。从上面的代码可以看出，该枚举对象实现接口System.Collections.IEnumerator。

注意：

还有一个集合接口ICollection，它派生于IEnumerable。更复杂的集合也实现这个接口。除了GetEnumerator()外，它还有一个属性，可以返回集合中的元素个数。它还可以把集合复制到数组中，并提供信息，说明它是否是线程安全的。但是，这里只考虑较简单的集合接口IEnumerable。

IEnumerator如下所示。

interface IEnumerator

{

object Current { get; }

bool MoveNext();

void Reset();

}

IEnumerator的工作方式如下：实现该接口的对象应与一个集合相关联，这个对象在第一次初始化时，还没有指向集合中的任何元素，必须调用MoveNext()，移动枚举，才能使它指向集合中的第一个元素。接着用Current属性获取该元素，Current属性返回一个对象引用，所以必须把它的数据类型转换为要在集合中查找的对象类型。可以对该对象进行任何操作，之后再次调用MoveNext()方法，移动到集合的下一个元素上。重复这个过程，直到集合中没有元素为止，当Current属性返回null时，就表示到达了集合的末尾。如果要返回到集合的开头，可以随时调用Reset()方法。注意Reset()方法实际上返回到集合开头前面的位置，如果要调用这个方法，就需要接着调用MoveNext()，指向第一个元素。

从这个例子可以看出，当不想提供下标时，集合是遍历元素的另一种方式。可以根据集合本身来选择元素返回的顺序，这通常意味着只要可以查看所有的元素，就不需要考虑获得元素的顺序。但在一些情况下，集合要按一定的顺序返回元素。此时，集合就是一种基本类型的对象组，因为它不允许向该组添加或删除元素，而只能按照集合所确定的顺序获得元素，并查看它们。甚至不能替换或修改集合中的元素，因为Current属性是只读的。这种集合主要是为foreach循环提供更方便的语法。

很明显，数组也是集合，因为foreach命令可以用于数组。对于数组这种特殊情况，System.Array类提供的枚举可以按照下标从0开始的升序来遍历其中的元素。

在C#中，foreach循环只是一种语法上的简写方式：

{

IEnumerator enumerator = MessageSet.GetEnumerator();

string nextMessage;

enumerator.MoveNext();

while ( (nextMessage = enumerator.Current) != null)

{

DoSomething(nextMessage); // NB. We only have read access

// toNextMessage

enumerator.MoveNext();

}

}

注意上述代码段中的闭合花括号。提供它们的原因是为了确保这段代码的作用与前面的foreach循环的作用一样。如果没有使用闭合花括号，这段代码就会有所不同，nextMessage 和 enumerator变量在循环结束时应保留在内存中。

集合的一个重要方面是枚举作为一个单独的对象返回。它不应是与集合相同的对象，原因是多个枚举可以同时应用到同一个集合上。

2. 给Vector 结构添加集合支持
下面对第3章的Vector结构进行另一个集合支持扩展。

在Vector结构中，Vector实例包含3个元素x、y和z，第3章已定义了一个索引符，因此可以把Vector实例当作数组，使用SomeVector[0] 访问x元素，使用SomeVector[1]访问y元素，使用SomeVector[2] 访问z元素。

下面把Vector结构扩展为一个新代码示例VectorAsCollection项目，编写如下代码，迭代 Vector中的元素：

foreach (double component in someVector)

Console.WriteLine("Component is " + component);

首先让Vector实现IEnumerable接口，把它标记为一个集合。第一步是修改Vector结构的声明：

struct Vector : IFormattable, IEnumerable

{

public double x, y, z;

注意出现了IFormattable接口，因为我们在前面为它添加了字符串格式说明符。下面需要实现IEnumerable接口。

public IEnumerator GetEnumerator()

{

return new VectorEnumerator(this);

}

GetEnumerator()的实现比较复杂，但它取决于一个新类VectorEnumerator，这个类需要定义。因为VectorEnumerator不是外部代码需要直接看到的类，所以可以把它声明为Vector结构中的私有类，其定义如下所示：

private class VectorEnumerator : IEnumerator

{

Vector theVector; // Vector object that this enumerato refers to

int location; // which element of theVector the enumerator is

// currently referring to

public VectorEnumerator(Vector theVector)

{

this.theVector = theVector;

location =–1;

}

public bool MoveNext()

{

++location;

return (location > 2) ? false : true;

}

public object Current

{

get

{

if (location < 0 || location > 2)

throw new InvalidOperationException(

"The enumerator is either before the first element or " +

"after the last element of the Vector");

return theVector[(uint)location];

}

}

public void Reset()

private class VectorEnumerator : IEnumerator

{

location = -1;

}

}

因为需要一个枚举，所以VectorEnumerator实现IEnumerator接口。它还包含两个成员字段theVector和location。TheVector是与这个枚举相关的Vector(集合)引用，而location是一个int类型的变量，表示枚举在集合中的什么地方引用，换言之，就是Current属性是否应获取矢量的x, y 或 z元素。

在本例中，要把location当作一个下标，在内部实现enumerator，把Vector当作一个数组来访问。此时，有效的下标是0、1和2。这里可以使用–1，表示枚举在集合开头的前面，使用3表示到达了集合的末尾。因此，在VectorEnumerator构造函数中把这个字段初始化为–1：

public VectorEnumerator(Vector theVector)

{

this.theVector = theVector;

location =–1;

}

注意构造函数也带有要枚举的Vector实例的引用—— 这是在Vector.GetEnumerator()方法中提供的：

public IEnumerator GetEnumerator()

{

return new VectorEnumerator(this);

}