effective hierarchy（一）之 从array说起（4）

回顾：上一节中，我们看到了数组列表、队列与栈，从边界上突破了数组的局限。下面继续来看实用的哈希表。

 

MSDN:c#2.0

 

HashTable：

1.基础

（1）表示一系列（collection）的键－值（key-value）对，由键的哈希代码（hash code）来组织。它的语法为

        [SerializableAttribute]
        [ComVisibleAttribute(true)]
        public class Hashtable : IDictionary, ICollection, IEnumerable, ISerializable, IDeserializationCallback, ICloneable

 

 （2）Hashtable的每个元素都是以DictionaryEntry对象储存的键值对；

 （3）值可以为空引用，但键不能是空引用；

 （4）在Hashtable中，作为键的键对象不能被修改（immutable）；

 （5）通过Add()方法添加元素时，基于键的哈希码，元素被置于带柄的桶（bucket）中；随后对该键的查找，是使用该键的哈希码只在特定的桶中搜索（search），将大大减少为查找一个元素所需要的键比较的次数；

 （6）Hashtable的每个键对象，必须提供可通过GetHash访问调用的自有哈希函数（hash function）；但是，任意实现了IHashCodeProvider的对象都可以传递到Hashtable构建器，该函数可用于表（table）中的所有对象；

（7）Hashtable的容量是它所能支持的元素数量；增加容量的时候，容量会重新分配，自动增加；

（8）因为键可以被继承，从而改变行为，所以使用Equals方法进行的比较并不能保证（guarante）键的绝对唯一性（absolute uniqueness）。

 

2.遍历

（1）使用foreach时，对集合中每个元素的类型提出要求；因为Hashtable的每个元素都是键值对，所以它的类型不是键对象的类型也不是值的类型。这是一个DictionaryEntry结构（struct）；如foreach (DictionaryEntry de in myHashtable) {...};

（2）foreach语句是枚举器（enumerator）的包装者（wrapper），只允许从集合读出而不允许写入；

（3）因为对一个枚举器进行序列化（serializing）和解除序列化（deserializing）会导致元素被记录（recordded），必须使用Reset方法来使枚举继续进行。

 

3.载入因子

（1）元素放到桶中的最大比率（maximum ratio）是由Hashtable的载入因子（load factor）决定；

（2）载入因子越小，平均查找时间越短，同时更消耗内存；

（3）缺省的载入因子是1.0，一般地，该值在速度和大小之间能够保持最好的平衡；创建哈希表时，可指另外的载入因子；

（4）元素加到Hashtable时，实际的载入因子会增加（increase），当实际载入因子达到指定的载入因子时，哈希表桶的数量自动增加，增加到大于哈希表当前桶数的两倍的最小质数（prime number）；

 

4.方法重写

（1）作为Hashtable键的对象，需要重写（override）对象类的Obejct.GetHashCode()方法（或IHashCodeProvider接口）以及Object.Equals()方法（或IComparer接口）；

（2）无论是重写方法还是接口，都必须以相同的方式控制大小写敏感性（handle case sentivity），否则，可能导致Hashtable错误地行为（behave）；如，在创建Hashtable的时候，必须同CaseInsensitiveComparer类（或任意大小写不敏感的IComparer实现）一起使用CaseInsensitiveHashCodeProvider类（或任意大小写不敏感的IHashCodeProvider实现）；

（3）另外，当键存在（exist）于Hashtable时，这些方法调用相同的参数必须产生相同的结果；一种可行的替代方式是使用IEqualityComparer参数的构建器；如果键相等性（equality）仅仅是引用相等性（reference equality），继承下来的Object.GetHashCode()和Object.Equals()方法就足够了；

 

//主要用途示例

using System;
using System.Collections;

class Example
{
    public static void Main()
    {
        // Create a new hash table.
        //
        Hashtable openWith = new Hashtable();

        // Add some elements to the hash table. There are no 
        // duplicate keys, but some of the values are duplicates.
        openWith.Add("txt", "notepad.exe");
        openWith.Add("bmp", "paint.exe");
        openWith.Add("dib", "paint.exe");
        openWith.Add("rtf", "wordpad.exe");

        // The Add method throws an exception if the new key is 
        // already in the hash table.
        try
        {
            openWith.Add("txt", "winword.exe");
        }
        catch
        {
            Console.WriteLine("An element with Key = \"txt\" already exists.");
        }

        // The Item property is the default property, so you 
        // can omit its name when accessing elements. 
        Console.WriteLine("For key = \"rtf\", value = {0}.", openWith["rtf"]);

        // The default Item property can be used to change the value
        // associated with a key.
        openWith["rtf"] = "winword.exe";
        Console.WriteLine("For key = \"rtf\", value = {0}.", openWith["rtf"]);

        // If a key does not exist, setting the default Item property
        // for that key adds a new key/value pair.
        openWith["doc"] = "winword.exe";

        // ContainsKey can be used to test keys before inserting 
        // them.
        if (!openWith.ContainsKey("ht"))
        {
            openWith.Add("ht", "hypertrm.exe");
            Console.WriteLine("Value added for key = \"ht\": {0}", openWith["ht"]);
        }

        // When you use foreach to enumerate hash table elements,
        // the elements are retrieved as KeyValuePair objects.
        Console.WriteLine();
        foreach( DictionaryEntry de in openWith )
        {
            Console.WriteLine("Key = {0}, Value = {1}", de.Key, de.Value);
        }

        // To get the values alone, use the Values property.
        ICollection valueColl = openWith.Values;

        // The elements of the ValueCollection are strongly typed
        // with the type that was specified for hash table values.
        Console.WriteLine();
        foreach( string s in valueColl )
        {
            Console.WriteLine("Value = {0}", s);
        }

        // To get the keys alone, use the Keys property.
        ICollection keyColl = openWith.Keys;

        // The elements of the KeyCollection are strongly typed
        // with the type that was specified for hash table keys.
        Console.WriteLine();
        foreach( string s in keyColl )
        {
            Console.WriteLine("Key = {0}", s);
        }

        // Use the Remove method to remove a key/value pair.
        Console.WriteLine("\nRemove(\"doc\")");
        openWith.Remove("doc");

        if (!openWith.ContainsKey("doc"))
        {
            Console.WriteLine("Key \"doc\" is not found.");
        }
    }
}

/* This code example produces the following output:

An element with Key = "txt" already exists.
For key = "rtf", value = wordpad.exe.
For key = "rtf", value = winword.exe.
Value added for key = "ht": hypertrm.exe

Key = dib, Value = paint.exe
Key = txt, Value = notepad.exe
Key = ht, Value = hypertrm.exe
Key = bmp, Value = paint.exe
Key = rtf, Value = winword.exe
Key = doc, Value = winword.exe

Value = paint.exe
Value = notepad.exe
Value = hypertrm.exe
Value = paint.exe
Value = winword.exe
Value = winword.exe

Key = dib
Key = txt
Key = ht
Key = bmp
Key = rtf
Key = doc

Remove("doc")
Key "doc" is not found.
 */

 

-------------------------------------------------------------------------------------------------------------------- 

小结：从本节，我们看到一个基于数组特征的集大成者。在实际使用中，应根据情况对待数组相关的不同概念。