9.5  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("键一", "键值一");

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

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

            //传入实现了IDictionary接口的参数创建哈希表

            Hashtable ht3 = new Hashtable(sl);

}

创建好哈希表后，可以使用Hashtable提供的方法和属性来操作哈希表对象。下面示例程序演示操作哈希表的基本方法。

class Program

{

    static void Main(string[] args)

    {

        //初始化哈希表

        Hashtable hl = new Hashtable();

        //使用Add方法向哈希表添加元素

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

        hl.Add("键二", "键值二");

        hl.Add("键三", "键值三");

        hl.Add("键四", "键值四");

        hl.Add("键五", "键值五");

        hl.Add("键六", "键值六");

        hl.Add("键七", "键值七");

        DisplayResult(hl);

        Console.WriteLine("通过键获取键值："+ hl["键一"]);

        Console.WriteLine("移除哈希表中的元素");

        hl.Remove("键二");

        Console.WriteLine("哈希表中的元数总数是：" + hl.Count);

        DisplayResult(hl);

        Console.ReadLine();

    }

    static void DisplayResult(Hashtable tl)

    {

        foreach (DictionaryEntry de in tl)

        {

            Console.WriteLine("哈希表中的键：{0},对应的值{1}",de.Key,de.Value);

        }

    }

}

程序代码的输出结果如图9.14所示。

图9.14  哈希表的操作

从输出结果可以发现，哈希表内部的排列是无序的，而且哈希表没有提供类似数组中的Sort方法，如果需要使用排序集合，可以考虑使用SortedList类。

 9.5.3  SortedList

SortedList对象是可以排序的字典对象。与哈希表不同的是，SortedList内部管理值和相应键的各一个数组。这些数组有初始容量，并可自动扩容，SortedList根据它们的键保持排序状态，这种特性要求为SortedList中指定的键实现IComparable接口。

为了构建SortedList的一个新实例，可以调用SortedList类的6种构造函数之一。比较常用的构造函数如下代码所示。

//使用默认初始容量，使用由键对象实现的IComparable来实现排序

public SortedList();

//使用指定的IComparer对键排序

public SortedList(IComparer comparer);

//根据IDictionary对象实例初始化SortedList

public SortedList(IDictionary d);

//指定初始容量

public SortedList(int initialCapacity);

下面的代码示例4种构造SortedList方法。

static void Main(string[] args)

{

    //默认值构建

    SortedList sl=new SortedList();

    //指定键的比较器

    SortedList s2=new SortedList(new CaseInsensitiveComparer());

    //指定初始容量

    SortedList temp=new SortedList(2);

    temp.Add("1","1");

    temp.Add("2","2");

    //使用IDictionary来初始化

    SortedList s3=new SortedList(temp);           

}

下面的示例代码将演示如何操作和使用这种类型的数据结构。

static void Main(string[] args)

{

    //默认值构建

    SortedList sl=new SortedList();

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

    sl.Add("键2", "键值二");

    sl.Add("键3", "键值三");

    sl.Add("键4", "键值四");

    sl.Add("键5", "键值六");

    sl.Add("键6", "键值七");

    Console.WriteLine("排序字典最初的初始化列表为：");

    DisplayResult(sl);

    sl.Remove("键5");

    Console.WriteLine("键6的键值是：{0}", sl["键6"]);           

    Console.ReadLine();

}

static void DisplayResult(SortedList sl)

{

    foreach (DictionaryEntry de in sl)

    {

        Console.WriteLine("键：{0},键值为：{1}", de.Key, de.Value);

    }

}

示例代码的输出结果如图9.15所示。

图9.15  对SortedList的操作

从图9.15中可以看到，SortedList在增、删时自动对键进行了排序。

 9.5.4  搜索排序哈希表

前面讲过，Hashtable类并没有提供可供排序的方法，但是可以通过它的两个属性Keys和Values，使用一种变通的方法来实现排序。下面的示例演示了通过keys属性排序哈希表的方法。这个方法并没有对哈希表中排列的元素顺序进行排列，这里只是采用了一种变通的方法以实现排序。代码示例如下。

static void Main(string[] args)

{

    Hashtable ht = new Hashtable();

    ht.Add("key1", "this is value1");

    ht.Add("key3", "this is vlaue3");

    ht.Add("key2", "this is value2");

    ht.Add("key4", "this is value4");

    Console.WriteLine("排序前的哈希键值顺序为：");

    foreach (DictionaryEntry de in ht)

    {

        Console.WriteLine("键{0}，值{1}", de.Key, de.Value);

    }

    //获取键的集合

    ICollection keys = ht.Keys;

    //将键集合转换为ArrayList类

    ArrayList al = new ArrayList(keys);

    //使用ArrayList进行排序

    al.Sort();

    Console.WriteLine("排序后的哈希键值顺序为：");

    foreach (object key in al)

    {

        Console.WriteLine("键{0}，值{1}", key, ht[key]);

    }

    Console.ReadLine();

}

示例代码的运行结果如图9.16所示。上面示例中，使用ArrayList作为Keys属性返回结果的包装，调用ArrayList类实例的Sort方法实现排序。同样的，也可以使用ArrayList类实例的搜索功能进行哈希表搜索。下面的示例代码演示如何搜索哈希表。

Hashtable ht = new Hashtable();

ht.Add("key1", "this is value1");

ht.Add("key3", "this is vlaue3");

ht.Add("key2", "this is value2");

ht.Add("key4", "this is value4");

ICollection keys = ht.Keys;

ArrayList al = new ArrayList(keys);

al.Sort();

//在这里使用ArrayList的BinarySearch搜索指定键值的值

int searchResult = al.BinarySearch("key3");

if (searchResult > 0)

{

    Console.WriteLine("搜索到的结果为：键{0}，值{1}",al[searchResult],ht[al [searchResult]]);

}

else

{

    Console.WriteLine("没有搜索到有效的结果值");

}

Console.ReadLine();

程序的结果如图9.17所示。

  

图9.16  哈希表排序结果                            图9.17  哈希表的搜索