C#集合之字典的用法
字典表示一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，這種數(shù)據(jù)結(jié)構(gòu)允許按照某個鍵來訪問元素。字典也稱為映射或散列表。
字典的主要特性是能根據(jù)鍵快速查找值。也可以自由添加和刪除元素，這有點像List<T>（http://chabaoo.cn/article/244084.htm），但沒有在內(nèi)存中移動后續(xù)元素的性能開銷。
下圖是一個簡化表示，鍵會轉(zhuǎn)換位一個散列。利用散列創(chuàng)建一個數(shù)字，它將索引和值關(guān)聯(lián)起來。然后索引包含一個到值的鏈接。一個索引項可以關(guān)聯(lián)多個值，索引可以存儲為一個樹型結(jié)構(gòu)。
.NET Framework提供了幾個字典類。最主要的類是Dictionary<TKey,TValue>。
1.鍵的類型
用作字典中的鍵的類型必須重寫Object類的GetHashCode()方法。只要字典類需要確定元素的位置，它就要調(diào)用GetHashCode()方法。GetHashCode()方法返回的int有字典用于計算在對應(yīng)位置放置元素的索引。后面介紹這個算法，現(xiàn)在只需要知道它涉及素數(shù)，所以字典的容量是一個素數(shù)。
GetHashCode()方法的實現(xiàn)代碼必須滿足的要求：
- *相同的對象應(yīng)總是返回相同的值
- *不同的對象可以返回相同的值
- *它應(yīng)執(zhí)行的比較快，計算的開銷不大
- *它不能拋出異常
- *它應(yīng)至少使用一個實例字段
- *散列代碼值應(yīng)平均分布在int可以存儲的這個數(shù)字范圍上
- *散列代碼最好在對象的生存期中不發(fā)生變化
字典的性能取決于GetHashCode()方法的實現(xiàn)代碼。
散列代碼值應(yīng)平均分布在int可以存儲的這個數(shù)字范圍上的原因：
如果兩個鍵返回的散列代碼值會得到相同的索引，字典類就必須尋找最近的可用空閑位置來存儲第二個數(shù)據(jù)項，這需要進(jìn)行一定的搜索，以便以后檢索這一項。顯然這會降低性能，如果在排序的時候許多鍵都有相同的索引這中沖突會更可能出現(xiàn)。根據(jù)Microsoft的算法工作方式，當(dāng)計算出來的散列代碼值平均分布在int.MinValue和int.MaxValue之間時，這種風(fēng)險會降到最低。
除了實現(xiàn)GetHashCode()方法之外，鍵類型還必須實現(xiàn)IEquatable<T>.Equals()方法，或重寫Object.Equals()方法。0因為不同的鍵對象可能返回相同的散列代碼，所以字典使用Equals()方法來比較鍵。字典檢查兩個鍵A和B是否相等，并調(diào)用A.Equals(B)方法。這表示必須確保下述條件總是成立：
如果A.Equals(B)返回true，則A.GetHashCode()和B.GetHashCode()總是返回相同的散列代碼。
這聽起來有點奇怪，但它很重要。如果上述條件不成立，這個字典還能工作，但會出現(xiàn)，把一個對象放在字典中后，就再也檢索不到它，或者返回了錯誤的項。
所以，如果為Equals()方法提供了重寫版本，但沒提供GetHashCode()方法的重寫版本，C#編譯器會顯示一個警告。
對于System.Object，這個條件為true，因為Equals()方法只是比較引用，GetHashCode()方法實際上返回一個僅基于對象地址的散列代碼。這說明，如果散列表基于一個鍵，而該鍵沒有重寫這些方法，這個散列表可以工作，但只有對象完全相同，鍵才被認(rèn)為是相等的。也就是說，把一個對象放在字典中時，必須將它與該鍵的引用關(guān)聯(lián)起來。也不能以后用相同的值實例化另一個鍵對象。如果沒有重寫Equals()方法和GetHashCode()方法，在字典中使用類型時就不太方便。
System.String實現(xiàn)了IEquatable接口，并重載了GetHashCode()方法。Equals()方法提供了值的比較，GetHashCode()方法根據(jù)字符串的值返回一個散列代碼。因此，在字典中把字符串用在鍵很方便。
數(shù)字類型（如Int32）也實現(xiàn)了IEquatable接口，并重載了GetHashCode()方法。但是這些類型返回的散列代碼只能映射到值上。如果希望用作鍵的數(shù)字本身沒有分布在可能的整數(shù)值范圍內(nèi)，把整數(shù)用作鍵就不能滿足鍵值的平均分布規(guī)則，于是不能獲得最佳的性能。Int32并不適合在字典中使用。
如果需要使用的鍵類型沒有實現(xiàn)IEquatable接口，并根據(jù)存儲在字典中的鍵值重載GetHashCode()方法，就可以創(chuàng)建一個實現(xiàn)IEqualityComparer<T>接口的比較器。IEqualityComparer<T>接口定義了GetHashCode()方法和Equals()方法，并將傳遞的對象作為參數(shù)，這樣可以提供與對象類型不同的實現(xiàn)方式。
2.演示字典
創(chuàng)建一個員工ID（EmployeeId）結(jié)構(gòu)，用作字典的鍵。存儲在字典中的數(shù)據(jù)是Employee類型的對象。
該結(jié)構(gòu)的成員是表示員工的一個前綴字符和一個數(shù)字。這兩個變量都是只讀的，只能在構(gòu)造函數(shù)中初始化。字典中的鍵不應(yīng)改變，這是必須保證的。
public struct EmployeeId : IEquatable<EmployeeId>
{
private readonly char prefix;
private readonly int number;
public EmployeeId(string id)
{
Contract.Requires<ArgumentNullException>(id != null);
prefix = (id.ToUpper())[0];
int numLength = id.Length - 1;
try
{
number = int.Parse(id.Substring(1, numLength > 6 ? 6 : numLength));
}
catch (FormatException)
{
throw new Exception("Invalid EmployeeId format");
}
}
public override string ToString()
{
return prefix.ToString() + string.Format("{0,6:000000}", number);
}
//由于沒有填滿整數(shù)取值范圍，GetHashCode方法將數(shù)字向左移動16位，再與原來的數(shù)字進(jìn)行異或操作，
//最后將結(jié)果乘以16進(jìn)制數(shù)0x15051505。這樣，散列代碼在整數(shù)取值區(qū)域上的分布就很均勻。
public override int GetHashCode()
{
return (number ^ number << 16) * 0x15051505;
}
public bool Equals(EmployeeId other)
{
if (other == null) return false;
return (prefix == other.prefix && number == other.number);
}
//比較兩個EmployeeId對象的值
public override bool Equals(object obj)
{
return Equals((EmployeeId)obj);
}
public static bool operator ==(EmployeeId left, EmployeeId right)
{
return left.Equals(right);
}
public static bool operator !=(EmployeeId left, EmployeeId right)
{
return !(left == right);
}
}
public class Employee
{
private string name;
private decimal salary;
private readonly EmployeeId id;
public Employee(EmployeeId id, string name, decimal salary)
{
this.id = id;
this.name = name;
this.salary = salary;
}
public override string ToString()
{
return String.Format("{0}: {1, -20} {2:C}",
id.ToString(), name, salary);
}
}客戶端代碼：
static void Main()
{
//構(gòu)造函數(shù)指定了31個元素的容量。容量一般是素數(shù)。
//如果指定了一個不是素數(shù)的值，Dictionary<TKey,TValue>類會使用指定的整數(shù)后面緊接著的一個素數(shù)
var employees = new Dictionary<EmployeeId, Employee>(31);
var idTony = new EmployeeId("C3755");
var tony = new Employee(idTony, "Tony Stewart", 379025.00m);
employees.Add(idTony, tony);
Console.WriteLine(tony);
var idCarl = new EmployeeId("F3547");
var carl = new Employee(idCarl, "Carl Edwards", 403466.00m);
employees.Add(idCarl, carl);
Console.WriteLine(carl);
var idKevin = new EmployeeId("C3386");
var kevin = new Employee(idKevin, "Kevin Harwick", 415261.00m);
employees.Add(idKevin, kevin);
Console.WriteLine(kevin);
var idMatt = new EmployeeId("F3323");
var matt = new Employee(idMatt, "Matt Kenseth", 1589390.00m);
employees[idMatt] = matt;
Console.WriteLine(matt);
var idBrad = new EmployeeId("D3234");
var brad = new Employee(idBrad, "Brad Keselowski", 322295.00m);
employees[idBrad] = brad;
Console.WriteLine(brad);
}3.Lookup類
Dictionary<TKey,TValue>類支持每個鍵關(guān)聯(lián)一個值。Lookup<TKey,TElement>類把鍵映射到一個值集上。這個類在程序集System.Core中實現(xiàn)，用System.Linq定義。
Lookup<TKey,TElement>類不能像一般的字典那樣創(chuàng)建，必須調(diào)用ToLookup()方法，該方法返回一個Lookup<TKey,TElement>對象。ToLookup()方法是一個擴(kuò)展方法，它可以用于實現(xiàn)了IEnumerable<T>接口的所有類。
ToLookup()方法需要一個Func<TSource,Tkey>,Func<TSource,Tkey>定義了選擇器?！ ?/p>
static void Main()
{
var racers = new List<Racer>();
racers.Add(new Racer(26, "Jacques", "Villeneuve", "Canada", 11));
racers.Add(new Racer(18, "Alan", "Jones", "Australia", 12));
racers.Add(new Racer(11, "Jackie", "Stewart", "United Kingdom", 27));
racers.Add(new Racer(15, "James", "Hunt", "United Kingdom", 10));
racers.Add(new Racer(5, "Jack", "Brabham", "Australia", 14));
//國家相同的對象關(guān)聯(lián)到一個鍵
var lookupRacers = racers.ToLookup(r => r.Country);
foreach (Racer r in lookupRacers["Australia"])
{
Console.WriteLine(r);
}
}輸出：
Alan Jones Jack Brabham
4.有序字典
SortedDictionary<TKey,TValue>類是一個二叉搜索樹，其中的元素根據(jù)鍵來排序。該鍵類型必須實現(xiàn)IComparable<TKey>接口。
如果鍵的類型不能排序，還可以創(chuàng)建一個實現(xiàn)了IComparer<TKey>接口的比較器，將比較器用作有序字典的構(gòu)造函數(shù)的一個參數(shù)。
SortedDictionary<TKey,TValue>和有序列表SortedList<TKey,TValue>(http://chabaoo.cn/article/244111.htm)的區(qū)別：
- *SortedList<TKey,TValue>類使用的內(nèi)存比SortedDictionary<TKey,TValue>少。
- *SortedDictionary<TKey,TValue>元素的插入和刪除操作比較快。
- *在用已排序好的數(shù)據(jù)填充集合時，若不需要改變?nèi)萘?，ortedList<TKey,TValue>比較快。
到此這篇關(guān)于C#集合之字典的文章就介紹到這了。希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
這篇文章主要介紹了C#訪問SqlServer設(shè)置鏈接超時的方法,涉及CommandTimeout屬性的相關(guān)設(shè)置技巧,非常簡單實用,需要的朋友可以參考下2015-06-06
今天通過本文給大家介紹C# 使用modbus 讀取PLC 寄存器地址的方法，使用的組件Nmodbus，文中通過實例代碼給大家介紹的非常詳細(xì)，需要的朋友參考下吧2021-10-10
這篇文章主要介紹了C#使用NPOI導(dǎo)入Excel的方法,簡單介紹了NPOI的功能及操作Excel的導(dǎo)入、讀取等相關(guān)技巧,需要的朋友可以參考下2017-04-04
這篇文章主要介紹了C#簡單實現(xiàn)SNMP的方法,通過一個簡單的自定義類分析了C#實現(xiàn)SNMP的相關(guān)技巧,具有一定參考借鑒價值,需要的朋友可以參考下2015-07-07
這篇文章主要為大家詳細(xì)介紹了untiy實現(xiàn)手機搖一搖震動，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-11-11
這篇文章主要分享了C#條碼生成類的實例代碼，具有一定的參考價值，感興趣的小伙伴們可以參考一下2017-06-06
C#中把DataTable、Dataset轉(zhuǎn)Json數(shù)據(jù)
這篇文章介紹了C#中把DataTable、Dataset轉(zhuǎn)Json數(shù)據(jù)的方法，文中通過示例代碼介紹的非常詳細(xì)。對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2022-04-04
C#構(gòu)建樹形結(jié)構(gòu)數(shù)據(jù)(全部構(gòu)建,查找構(gòu)建)
這篇文章主要介紹了C#構(gòu)建樹形結(jié)構(gòu)數(shù)據(jù)(全部構(gòu)建,查找構(gòu)建)，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-10-10
C# 多網(wǎng)卡 Server Listen...2007-04-04
本篇文章是對Wait與Pulse的使用進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-05-05