C# - 字典的工作原理

在C#中,我們可能經常用到使用非常方便的Hashtable,不知大家是否知道它的 另外一個名字:散列表.事實上Hashtable使用了某種算法,通過鍵(key)來確定每 個對象的位置,實際上,該算法並不完全是Hashtable類提供的.它有兩個部分,其 中的一部分的代碼是有key類來完成.我們平常在使用Hashtable的時候,key我們 一般使用string類(部分算法string已經提供,Microsoft已經替我們做了),所以 不會有任何的問題,但是如果key類是用戶自己編寫的,就必須自己編寫這部分算 法了.

下面我們用EmployeeID類作為key類,來講解如何編寫自己的算法.

在計算機中.由key類執行的部分算法成為散列,Hashtable在散列算法 中有特殊的地位,它提供了對象的GetHashCode()方法,該方法繼承於 Sysetm.Object.只要字典需要確定數據項的位置,就會條用key對象的 GetHashCode()方法.所以我們如果要是我們的key類起作用的話,就必須重寫 GetHashCode()方法.

GetHashCode()方法的工作方式是:返回一個int型的 數據,它使用這個鍵的值來生成int類型的數據.Hashtable獲取這個值,並對它進 行其他的一些操作,其中涉及一些非常復雜的計算,最後返回一個索引,表示帶有 指定散列的數據項在字典中的位置.這部分算法呢據說很復雜,非我輩能力所及, 就不介紹了.免得招來拍磚無數.

重載GetHashCode()方法就可以了嗎?答 案是否頂的!比如:如果再字典中,兩個數據項的散列有相同的索引,該怎麼辦?所 以要確保字典的容量大於其中元素的個數.而且,如果兩個對象包含相同的數據, 他們就必須給出相同的散列值.所以重寫System.Object的Equals()和 GetHashCode()方法時,必須考慮這個.

下面我們通過具體的例子進行講解 :

比如A公司建立了一個員工字典,該字典用EmployeeID對象做索引,存儲 的數據都是一個EmployeeData對象(員工的詳細數據).我們的實例創建一個字典, 添加了兩個員工,通過員工的id,獲取相應的信息.

首先我們看下我 EmployeeID類和EmployeeData類. EmployeeID類是關鍵,散列的部分算法就在 EmployeeID類中實現.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Web;
/**//// <summary>
/// Summary description for EmployeeID
/// </summary>
public class EmployeeID
{
　　public EmployeeID()
　　{
　　　 　//
　　　　// TODO: Add constructor logic here
　　　 　//
　　}
　　public EmployeeID(string id)
　　{
　　　　Id = id;
　　}
　　private string Id { get; set; }
　　//
　　public override string ToString()
　　{
　　　　return base.ToString();
　　}
　　//必須重寫,否則 EmployeeID類,不能作為key類,
　　public override int GetHashCode ()
　　{
　　　　return ToString().GetHashCode();
　 　}
　　//重載Equals方法,確保兩個相同的對象,返回相同的散列值
　　public override bool Equals(object obj)
　　{
　　　　 EmployeeID employeeID = obj as EmployeeID;
　　　　if (employeeID == null) return false;
　　　　if (this.Id == employeeID.Id) return true;
　　　　return false;
　　}
}

上面的代碼 ,我們重點看下GetHashCode()方法,我們前面講了, 如果要實現散列算法,必須滿足很多苛刻的要求.但是我們知道string類可以直接 作為Hashtable的key類,說明Microsoft已經為string類提供了很有效的散列算法 .所以我們直接應用string.GetHashCode()去重寫我們的EmployeeID類的 GetHashCode()方法.當然性能可能會有損失,因為EmployeeID類轉換為string的 時候會損失性能.

EmployeeData類就沒有什麼特別的啦,就一些數據

EmployeeData類

using System;
using System.Collections.Generic;
using System.Linq;
using System.Web;
/**//// <summary>
/// Summary description for EmployeeData
/// </summary>
public class EmployeeData
{
　　public EmployeeData()
　　{
　 　　　//
　　　　// TODO: Add constructor logic here
　　　 　//
　　}
　　public EmployeeData(string name,string age,string gender)
　　{
　　　　this.Name = name;
　　 　　this.Age = age;
　　　　this.Gender = gender;
　　}
　　public string Name { get; set; }
　　public string Age { get; set; }
　　public string Gender { get; set; }
}

Main 測試代碼

using System;
using System.Collections.Generic;
using System.Text;
using System.Collections;
namespace HashTableTest
{
　　class Program
　　{
　　　　static void Main(string[] args)
　　　　{
　　　　　　Hashtable ht = new Hashtable();
　　　 　　　ht.Add(new EmployeeID("A0001"), new EmployeeData ("Johnny", "24", "Man"));
　　　　 　　ht.Add(new EmployeeID("A0002"), new EmployeeData ("Vicky", "20", "female"));
　　　 　　　ht.Add(new EmployeeID("A0003"), new EmployeeData ("Allen", "30", "male"));
　　　　 　　Console.WriteLine("Please input the Employee ID");
　　　　　　string userId = Console.ReadLine();
　　　　　　//當 輸入ID的是否,返回員工的詳細數據
　　　　　　EmployeeData E1 = (EmployeeData)ht[new EmployeeID(userId)];
　　　　　　if (E1 != null)
　　　　　　{
　　　　　　　　Console.WriteLine ("Employee " + userId+"Data is :");
　　　　 　　　　Console.WriteLine(E1.Name);
　　　　　　　　 Console.WriteLine(E1.Age);
　　　　　　　　Console.WriteLine (E1.Gender);
　　　　　　}
　　　　　　Console.ReadLine ();
　　　　}
　　}
}

結果如圖所示