C# 用哈希表搜索对象

核心提示： .NET Framework中的大多数容器都是序列式容器（sequence containers）：它们按顺序存储对象，这种类型的容器功能很多——你可以以任何特殊的顺序来存储任意数量的对象，C# 用哈希表搜索对象，然而，这种多功能性是以一定的性能为代价的，那么元素就没有必要按你期望的顺

.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排列的。