用哈希表搜索对象

.NET Framework中的大多数容器都是序列式容器（sequence containers）：它们按顺序存储对象。这种类型的容器功能很多——你可以以任何特殊的顺序来存储任意数量的对象。

然而，这种多功能性是以一定的性能为代价的。在一个序列中查找一个特殊的对象所需要的时间取决于容器中对象的数量。如果我们没有对容器中元素进行排序，那么随着元素数量的增加，你所需要的查找时间也就直线增加了：如果容器中元素的数量增加了一倍，那么你用来查找一个特殊元素的时间也就增加了一倍。然而，如果我们对容器中的元素进行了排序，那么查找时间就是随着元素数量的对数而增加的了：要使查找一个元素的时间增加一倍，你必须使集合中的元素数量增加四倍。如果你用一个key来搜索对象，你可以用比序列式容器更好的方法来存储你的对象。你可以用哈希表（hash table）。

哈希表根据一个叫做hash的数字关键字（key）将对象存储在buckets中。hash value是从对象中的值计算得来的一个数字。每个不同的hash value都会创建一个新的bucket。要查找一个对象，你只需要计算这个对象的hash value并搜索相应的bucket就行了。通过快速地找到相应的bucket，就可以减少你需要搜索的对象数量了。

例如，设想在一个数据结构中有一些客户记录，你想通过信用卡号来搜索那些记录。一个简单的哈希函数将运用信用卡号的后两位数字，这会形成100个buckets——从00到99的每个两位数的数字都会创建一个bucket。（同样，运用后三位数字会创建1000个buckets。）只需要查询一个bucket，你就可以找到任何记录了，而不需要查询所有的buckets。

然而，同任何事情一样，并不是一切都这么简单的。如果你用信用卡号创建了一个哈希函数，而你想通过姓名来查找客户，你就需要查询整个哈希表，这样会花很多时间。这是因为哈希表是用一个不同的字段作为key的。而且，如果你查询整个哈希表，那么元素就没有必要按你期望的顺序来排列了。元素是根据hash value来排列的，而不是根据keys排列的。

在本篇文章中，我将详述我在前面的文章中的样例，让你修改一条员工记录。假设有一个很大的公司，公司里有上千位员工，你想用最快的方法来找到一条记录。所有员工的一个哈希表可以使搜索在最短的时间完成。

一个哈希函数需要有一定的属性。对于初学者来说，哈希函数必须是不变的。这就是说相同的key必须生成相同的hash value，一旦创建了对象，hash value就不能改变了。如果hash value改变了，你在哈希表中就再也找不到相应的对象了。

哈希函数需要的第二个属性就是能够平均分配buckets。如果所有的对象都生成相同的hash value，那么就需要更多的时间来查找一个特殊的对象。

实际上，这两个原则是很容易遵循的。在.NET Framework中有178个类重载了GetHashCode()，从而更好地发挥它们的作用。所有的.NET FCL（Framework Class Library）中类的实现都确保了hash value的更好的分配，并遵循了唯一性的原则。你应该确定你自己的类和结构是否需要重载GetHashCode()方法。最简单的（通常也是最好的）方法就是在key中选取一个不变的成员，并运用那个成员所生成的hash value。

员工数据库的一个明显的hash key就是社会保险号（Social Security Number）。它不仅不会改变，而且九位数的这个号码也可以让你任意运用以得到你期望的性能。你可以下载样例，看看运用hash keys进行搜索和运用序列式容器进行搜索有什么不同。

要把员工添加到一个哈希表中，你可以创建一个九位数的号码并把它作为key：

int hash = 111223333;
for (int i = 0; i < 100; i++)
{
   string lastname = "Person" + i.ToString();
   e = new Employee ("Employee", lastname, (200-i)*200);
   members.Add(hash++, e);
}

社会保险号满足了一个好的hash key的要求：它不会改变，它可以合理地分配、value取决于号码而不是reference。（你需要运用基于value的hash key而不是基于reference的hash key以避免我以前提到过的问题。）

运用这个hash key来查找对象也很简单：

 int ssn = Int32.Parse(this.SSN.Text);
currentEmp = (Employee)members[ssn];
if (currentEmp != null)
{
  LastName.Text = currentEmp.LastName;
  FirstName.Text = 
    currentEmp.FirstName;
  Salary.Text = 
    currentEmp.Salary.ToString ();
} else
  LastName.Text = "Not Found";

在C#中，你可以用数组语法在哈希表中查找对象。该语法强调了恒定时间搜索的概念：你可以把数组访问看做是一个快速的操作，而不是一个代价很高的函数调用。

关于哈希表最后的一个重点是，同所有的集合一样，它们也存储引用（references）。你不需要任何额外的工作来更新哈希表中的对象。一旦你引用了哈希表中的一个对象，你可以随意修改它。记住，同样的原则不适用于keys。你可以编写代码来改变keys，但如果那个代码修改了hash value，你就会丢失你的集合中的对象。

哈希表是很有用的、有效的容器。但是，要有效地运用它们，你需要了解容器和容器中对象的状态之间的关系。当你可以用从对象计算得来的不变的value来搜索对象时，哈希表就很有用。如果你用不同的顺序（通过姓名、社会保险号、或年龄）在对象中搜索，那么哈希表就不那么有用了。

关于作者: