C# 2.0实用开发 - Hashtable哈希表类和SortedList排序列表类

Hashtable类和SortedList类是两种被称为字典（dictionary）的集合。所谓字典，是指一种具有键值对的集合。

Hashtable类被称为哈希表，很多有关算法和数据结构的书都会讲到这种数据结构。Hashtable类在内部维护着一个内部哈希表，这个内部哈希表为高速检索数据提供了较好的性能。SortedList类是一种可以对“键值对”进行排序的字典集合。

 9.5.1  Hashtable
Hashtable类是一种键值对的集合，在内部，Hashtable维护着一个哈希表。内部哈希表为插入到Hashtable的每个键进行哈希编码，在后续的检索操作中，通过哈希代码，可以遍历所有元素。这种方法为搜寻操作提供了较佳的性能。

在.NET中，键和值可以是任何对象，例如字符串、自定义类等。在后台，当插入键值对到Hashtable中时，Hashtable使用每个键所引用对象的GetHashCode()方法，获取一个哈希编码，存入Hashtable中。

 9.5.2  构造普通哈希表
Hashtable类提供了15个重载的构造函数，本节将列举比较常用的构造函数，并进行举例说明，更多的信息可以查阅MSDN。

4种比较常用的Hashtable构造函数声明如下。

//使用默认的初始容量、加载因子、哈希代码提供程序和比较器来初始化 Hashtable类的实例

public Hashtable();

//使用指定容量、默认加载因子、默认哈希代码提供程序和比较器来初始化Hashtable类的实例

public Hashtable(int capacity);

//使用指定的容量，加载因子来初始化Hashtable类的实例

public Hashtable(int capacity, float loadFactor);

//通过将指定字典中的元素复制到新的 Hashtable 对象中，初始化 Hashtable 类的一个新实例。新 //Hashtable 对象的初始容量等于复制的元素数，并且使用默认的加载因子、哈希代码提供程序和比较器

public Hashtable(IDictionary d);

构造哈希表时，有一些新的概念需要先理解。

—     在哈希表中，键被转换为哈希代码，而值存储在存储桶（bucket）中。

—     初始容量指哈希表中元素的数目。加载因子是哈希表元素与存储桶的最大比率，当初始容量需要自动扩展前，确定值与存储桶之间的最大比率。值越小，出现冲突也越小。.NET默认加载因子为1.0。

下面的例子演示如何使用这4种方法构造哈希表。

        static void Main(string[] args) {

            //使用所有默认值构建哈希表实例

            Hashtable ht = new Hashtable();

            //指定哈希表实例的初始容量为20个元素

            Hashtable ht1 = new Hashtable(20);

            //指定初始容量为20个元素，加载因子为0.8的哈希表实例

            Hashtable ht2 = new Hashtable(20, 0.8f);

            //实例化一个SortedList

            SortedList sl = new SortedList();

            sl.Add("键一", "键值一");