11.8 字典
字典表示一种非常复杂的数据结构，这种数据结构允许按照某个键来访问元素。字典也称为映射或散列表。字典的主要特性是能根据键快速查找值。也可以自由添加和删除元素，这有点像List<T>类，但没有在内存中移动后续元素的性能开销。
图11-5是字典的一个简化表示。其中employee-id(如B4711)是添加到字典中的键。键会转换为一个散列。利用散列创建一个数字，它将索引和值关联起来。然后索引包含一个到值的链接。该图做了简化处理，因为一个索引项可以关联多个值，索引可以存储为一个树型结构。
图11-5
.NET Framework提供了几个字典类。可以使用的最主要的类是Dictionary<TKey, TValue>。
11.8.1 字典初始化器
C# 6定义了一个新的语法，在声明时初始化字典。带有int键和string值的字典可以初始化如下：
var dict = new Dictionary<int, string>()
{
[3] = "three",
[7] = "seven"
};
这里把两个元素添加到字典中。第一个元素的键是3，字符串值是three；第二个元素的键是7，字符串值是seven。这个初始化语法易于阅读，使用的语法与访问字典中的元素相同。
11.8.2 键的类型
用作字典中键的类型必须重写Object类的GetHashCode()方法。只要字典类需要确定元素的位置，它就要调用GetHashCode()方法。GetHashCode()方法返回的int由字典用于计算在对应位置放置元素的索引。这里不介绍这个算法。我们只需要知道，它涉及素数，所以字典的容量是一个素数。
GetHashCode()方法的实现代码必须满足如下要求：
● 相同的对象应总是返回相同的值。
● 不同的对象可以返回相同的值。
● 它不能抛出异常。
● 它应至少使用一个实例字段。
● 散列代码最好在对象的生存期中不发生变化。
除了GetHashCode()方法的实现代码必须满足的要求之外，最好还满足如下要求：
● 它应执行得比较快，计算的开销不大。
● 散列代码值应平均分布在int可以存储的整个数字范围上。
注意：字典的性能取决于GetHashCode()方法的实现代码。
为什么要使散列代码值平均分布在整数的取值范围内？如果两个键返回的散列代码值会得到相同的索引，字典类就必须寻找最近的可用空闲位置来存储第二个数据项，这需要进行一定的搜索，以便以后检索这一项。显然这会降低性能，如果在排序时许多键都有相同的索引，这类冲突就更可能出现。根据Microsoft的算法的工作方式，当计算出来的散列代码值平均分布在int.MinValue和int.MaxValue之间时，这种风险会降低到最小。
除了实现GetHashCode()方法之外，键类型还必须实现IEquatable<T>.Equals()方法，或重写Object类的Equals()方法。因为不同的键对象可能返回相同的散列代码，所以字典使用Equals()方法来比较键。字典检查两个键A和B是否相等，并调用A.Equals(B)方法。这表示必须确保下述条件总是成立：
如果A.Equals(B)方法返回true，则A.GetHashCode()和B.GetHashCode()方法必须总是返回相同的散列代码。
这似乎有点奇怪，但它非常重要。如果设计出某种重写这些方法的方式，使上面的条件并不总是成立，那么把这个类的实例用作键的字典就不能正常工作，而是会发生有趣的事情。例如，把一个对象放在字典中后，就再也检索不到它，或者试图检索某项，却返回了错误的项。
注意：如果为Equals()方法提供了重写版本，但没有提供GetHashCode()方法的重写版本，C#编译器就会显示一个编译警告。
对于System.Object，这个条件为true，因为Equals()方法只是比较引用，GetHashCode()方法实际上返回一个仅基于对象地址的散列代码。这说明，如果散列表基于一个键，而该键没有重写这些方法，这个散列表就能正常工作。但是，这么做的问题是，只有对象完全相同，键才被认为是相等的。也就是说，把一个对象放在字典中时，必须将它与该键的引用关联起来。也不能在以后用相同的值实例化另一个键对象。如果没有重写Equals()方法和GetHashCode()方法，在字典中使用类型时就不太方便。
另外，System.String实现了IEquatable接口，并重载了GetHashCode()方法。Equals()方法提供了值的比较，GetHashCode()方法根据字符串的值返回一个散列代码。因此，在字典中把字符串用作键非常方便。
数字类型(如Int32)也实现IEquatable接口，并重载GetHashCode()方法。但是这些类型返回的散列代码只映射到值上。如果希望用作键的数字本身没有分布在可能的整数值范围内，把整数用作键就不能满足键值的平均分布规则，于是不能获得最佳的性能。Int32并不适合在字典中使用。
如果需要使用的键类型没有实现IEquatable接口，并根据存储在字典中的键值重载GetHashCode()方法，就可以创建一个实现IEqualityComparer<T>接口的比较器。IEquality-Comparer<T>接口定义了GetHashCode()和Equals()方法，并将传递的对象作为参数，因此可以提供与对象类型不同的实现方式。Dictionary<TKey, TValue>构造函数的一个重载版本允许传递一个实现了IEqualityComparer <T>接口的对象。如果把这个对象赋予字典，该类就用于生成散列代码并比较键。
11.8.3 字典示例
字典示例程序建立了一个员工字典。该字典用EmployeeId对象来索引，存储在字典中的每个数据项都是一个Employee对象，该对象存储员工的详细数据。
实现EmployeeId结构是为了定义在字典中使用的键，该结构的成员是表示员工的一个前缀字符和一个数字。这两个变量都是只读的，只能在构造函数中初始化。字典中的键不应改变，这是必须保证的。在构造函数中填充字段。重载ToString()方法是为了获得员工ID的字符串表示。与键类型的要求一样，EmployeeId结构也要实现IEquatable接口，并重载GetHashCode()方法(代码文件DictionarySample/EmployeeId.cs)。
public class EmployeeIdException : Exception
{
public EmployeeIdException(string message) : base(message) { }
}
public struct EmployeeId : IEquatable<EmployeeId>
{
private readonly char _prefix;
private readonly int _number;
public EmployeeId(string id)
{
Contract.Requires<ArgumentNullException>(id ! = null);
_prefix = (id.ToUpper())[0];
int numLength = id.Length -1;
try
{
_number = int.Parse(id.Substring(1, numLength > 6 ? 6 : numLength));
}
catch (FormatException)
{
throw new EmployeeIdException("Invalid EmployeeId format");
}
}
public override string ToString() => _prefix.ToString() + $"{number,6:000000}";
public override int GetHashCode() => (number ^ number << 16) * 0x15051505;
public bool Equals(EmployeeId other) =>
(prefix == other? .prefix && number == other? .number);
public override bool Equals(object obj) => Equals((EmployeeId)obj);
public static bool operator ==(EmployeeId left, EmployeeId right) =>
left.Equals(right);
public static bool operator ! =(EmployeeId left, EmployeeId right) =>
!(left == right);
}
由IEquatable<T>接口定义的Equals()方法比较两个EmployeeId对象的值，如果这两个值相同，它就返回true。除了实现IEquatable<T>接口中的Equals()方法之外，还可以重写Object类中的Equals()方法。
public bool Equals(EmployeeId other) =>
(prefix == other.prefix && number == other.number);
由于数字是可变的，因此员工可以取1～190000的一个值。这并没有填满整数取值范围。GetHashCode()方法使用的算法将数字向左移动16位，再与原来的数字进行异或操作，最后将结果乘以十六进制数15051505。散列代码在整数取值区域上的分布相当均匀：
public override int GetHashCode() => (number ^ number << 16) * 0x15051505;
注意：在Internet上，有许多更复杂的算法，它们能使散列代码在整数取值范围上更好地分布。也可以使用字符串的GetHashCode()方法来返回一个散列。
Employee类是一个简单的实体类，该实体类包含员工的姓名、薪水和ID。构造函数初始化所有值，ToString()方法返回一个实例的字符串表示。ToString()方法的实现代码使用格式化字符串创建字符串表示，以提高性能(代码文件DictionarySample/Employee.cs)。
public class Employee
{
private string _name;
private decimal _salary;
private readonly EmployeeId _id;
public Employee(EmployeeId id, string name, decimal salary)
{
_id = id;
_name = name;
_salary = salary;
}
public override string ToString() => $"{id.ToString()}: {name, -20} {salary:C}";
}
在示例应用程序的Main()方法中，创建一个新的Dictionary<TKey, TValue>实例，其中键是EmployeeId类型，值是Employee类型。构造函数指定了31个元素的容量。注意容量一般是素数。但如果指定了一个不是素数的值，也不需要担心。Dictionary<TKey, TValue>类会使用传递给构造函数的整数后面紧接着的一个素数来指定容量。创建员工对象和ID后，就使用新的字典初始化语法把它们添加到新建的字典中。当然，也可以调用字典的Add()方法添加对象(代码文件DictionarySample/Program.cs)：
public static void Main()
{
var employees = new Dictionary<EmployeeId, Employee>(31);
var idTony = new EmployeeId("C3755");
var tony = new Employee(idTony, "Tony Stewart", 379025.00m);
var idCarl = new EmployeeId("F3547");
var carl = new Employee(idCarl, "Carl Edwards", 403466.00m);
var idKevin = new EmployeeId("C3386");
var kevin = new Employee(idKevin, "Kevin Harwick", 415261.00m);
var idMatt = new EmployeeId("F3323");
var matt = new Employee(idMatt, "Matt Kenseth", 1589390.00m);
var idBrad = new EmployeeId("D3234");
var brad = new Employee(idBrad, "Brad Keselowski", 322295.00m);
var employees = new Dictionary<EmployeeId, Employee>(31)
{
[idTony] = tony,
[idCarl] = carl,
[idKevin] = kevin,
[idMatt] = matt,
[idBrad] = brad
};
foreach (var employee in employees.Values)
{
WriteLine(employee);
}
将数据项添加到字典中后，在while循环中读取字典中的员工。让用户输入一个员工号，把该号码存储在变量userInput中。用户输入X即可退出应用程序。如果输入的键在字典中，就使用Dictionary<TKey, TValue>类的TryGetValue()方法检查它。如果找到了该键，TryGetValue()方法就返回true；否则返回false。如果找到了与键关联的值，该值就存储在employee变量中，并把该值写入控制台。
注意：也可以使用Dictionary<TKey, TValue>类的索引器替代TryGetValue()方法，来访问存储在字典中的值。但是，如果没有找到键，索引器会抛出一个KeyNotFound-Exception类型的异常。
while (true)
{
Write("Enter employee id (X to exit)> ");
var userInput =ReadLine();
userInput = userInput.ToUpper();
if (userInput == "X") break;
EmployeeId id;
try
{
id = new EmployeeId(userInput);
Employee employee;
if (! employees.TryGetValue(id, out employee))
{
WriteLine($"Employee with id {id} does not exist");
}
else
{
WriteLine(employee);
}
}
catch (EmployeeIdException ex)
{
WriteLine(ex.Message);
}
}
运行应用程序，得到如下输出：
Enter employee id (X to exit)> C3386
C003386: Kevin Harwick $415,261.00
Enter employee id (X to exit)> F3547
F003547: Carl Edwards $403,466.00
Enter employee id (X to exit)> X
Press any key to continue . . .
11.8.4 Lookup类
Dictionary<TKey, TValue>类支持每个键关联一个值。Lookup<TKey, TElement>类非常类似于Dictionary<TKey, TValue>类，但把键映射到一个值集合上。这个类在程序集System.Core中实现，用System.Linq名称空间定义。
Lookup<TKey, TElement>类不能像一般的字典那样创建，而必须调用ToLookup()方法，该方法返回一个Lookup<TKey, TElement>对象。ToLookup()方法是一个扩展方法，它可以用于实现IEnumerable<T>接口的所有类。在下面的例子中，填充了一个Racer对象列表。因为List<T>类实现了IEnumerable<T>接口，所以可以在赛车手列表上调用ToLookup()方法。这个方法需要一个Func<TSource, TKey>类型的委托，Func<TSource, TKey>类型定义了键的选择器。这里使用lambda表达式r => r.Country，根据国家来选择赛车手。foreach循环只使用索引器访问来自澳大利亚的赛车手(代码文件LookupSample/Program.cs)。
var racers = new List<Racer>();
racers.Add(new Racer("Jacques", "Villeneuve", "Canada", 11));
racers.Add(new Racer("Alan", "Jones", "Australia", 12));
racers.Add(new Racer("Jackie", "Stewart", "United Kingdom", 27));
racers.Add(new Racer("James", "Hunt", "United Kingdom", 10));
racers.Add(new Racer("Jack", "Brabham", "Australia", 14));
var lookupRacers = racers.ToLookup(r => r.Country);
foreach (Racer r in lookupRacers["Australia"])
{
WriteLine(r);
}
注意：扩展方法详见第13章，lambda表达式参见第9章。
结果显示了来自澳大利亚的赛车手：
Alan Jones
Jack Brabham
11.8.5 有序字典
SortedDictionary<TKey, TValue>是一个二叉搜索树，其中的元素根据键来排序。该键类型必须实现IComparable<TKey>接口。如果键的类型不能排序，则还可以创建一个实现了IComparer <TKey>接口的比较器，将比较器用作有序字典的构造函数的一个参数。
SortedDictionary<TKey, TValue>和SortedList<TKey, TValue>的功能类似。但因为SortedList<TKey, TValue>实现为一个基于数组的列表，而SortedDictionary<TKey, TValue>类实现为一个字典，所以它们有不同的特征。
● SortedList<TKey, TValue>使用的内存比SortedDictionary<TKey, TValue>少。
● SortedDictionary<TKey, TValue>的元素插入和删除操作比较快。
● 在用已排好序的数据填充集合时，若不需要修改容量，SortedList<TKey, TValue>就比较快。
注意：SortedList使用的内存比SortedDictionary少，但SortedDictionary在插入和删除未排序的数据时比较快。