C#集合之字典的用法
字典表示一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu),這種數(shù)據(jù)結(jié)構(gòu)允許按照某個(gè)鍵來(lái)訪問(wèn)元素。字典也稱為映射或散列表。
字典的主要特性是能根據(jù)鍵快速查找值。也可以自由添加和刪除元素,這有點(diǎn)像List<T>(http://www.dbjr.com.cn/article/244084.htm),但沒(méi)有在內(nèi)存中移動(dòng)后續(xù)元素的性能開(kāi)銷。
下圖是一個(gè)簡(jiǎn)化表示,鍵會(huì)轉(zhuǎn)換位一個(gè)散列。利用散列創(chuàng)建一個(gè)數(shù)字,它將索引和值關(guān)聯(lián)起來(lái)。然后索引包含一個(gè)到值的鏈接。一個(gè)索引項(xiàng)可以關(guān)聯(lián)多個(gè)值,索引可以存儲(chǔ)為一個(gè)樹(shù)型結(jié)構(gòu)。
.NET Framework提供了幾個(gè)字典類。最主要的類是Dictionary<TKey,TValue>。
1.鍵的類型
用作字典中的鍵的類型必須重寫(xiě)Object類的GetHashCode()方法。只要字典類需要確定元素的位置,它就要調(diào)用GetHashCode()方法。GetHashCode()方法返回的int有字典用于計(jì)算在對(duì)應(yīng)位置放置元素的索引。后面介紹這個(gè)算法,現(xiàn)在只需要知道它涉及素?cái)?shù),所以字典的容量是一個(gè)素?cái)?shù)。
GetHashCode()方法的實(shí)現(xiàn)代碼必須滿足的要求:
- *相同的對(duì)象應(yīng)總是返回相同的值
- *不同的對(duì)象可以返回相同的值
- *它應(yīng)執(zhí)行的比較快,計(jì)算的開(kāi)銷不大
- *它不能拋出異常
- *它應(yīng)至少使用一個(gè)實(shí)例字段
- *散列代碼值應(yīng)平均分布在int可以存儲(chǔ)的這個(gè)數(shù)字范圍上
- *散列代碼最好在對(duì)象的生存期中不發(fā)生變化
字典的性能取決于GetHashCode()方法的實(shí)現(xiàn)代碼。
散列代碼值應(yīng)平均分布在int可以存儲(chǔ)的這個(gè)數(shù)字范圍上的原因:
如果兩個(gè)鍵返回的散列代碼值會(huì)得到相同的索引,字典類就必須尋找最近的可用空閑位置來(lái)存儲(chǔ)第二個(gè)數(shù)據(jù)項(xiàng),這需要進(jìn)行一定的搜索,以便以后檢索這一項(xiàng)。顯然這會(huì)降低性能,如果在排序的時(shí)候許多鍵都有相同的索引這中沖突會(huì)更可能出現(xiàn)。根據(jù)Microsoft的算法工作方式,當(dāng)計(jì)算出來(lái)的散列代碼值平均分布在int.MinValue和int.MaxValue之間時(shí),這種風(fēng)險(xiǎn)會(huì)降到最低。
除了實(shí)現(xiàn)GetHashCode()方法之外,鍵類型還必須實(shí)現(xiàn)IEquatable<T>.Equals()方法,或重寫(xiě)Object.Equals()方法。0因?yàn)椴煌逆I對(duì)象可能返回相同的散列代碼,所以字典使用Equals()方法來(lái)比較鍵。字典檢查兩個(gè)鍵A和B是否相等,并調(diào)用A.Equals(B)方法。這表示必須確保下述條件總是成立:
如果A.Equals(B)返回true,則A.GetHashCode()和B.GetHashCode()總是返回相同的散列代碼。
這聽(tīng)起來(lái)有點(diǎn)奇怪,但它很重要。如果上述條件不成立,這個(gè)字典還能工作,但會(huì)出現(xiàn),把一個(gè)對(duì)象放在字典中后,就再也檢索不到它,或者返回了錯(cuò)誤的項(xiàng)。
所以,如果為Equals()方法提供了重寫(xiě)版本,但沒(méi)提供GetHashCode()方法的重寫(xiě)版本,C#編譯器會(huì)顯示一個(gè)警告。
對(duì)于System.Object,這個(gè)條件為true,因?yàn)镋quals()方法只是比較引用,GetHashCode()方法實(shí)際上返回一個(gè)僅基于對(duì)象地址的散列代碼。這說(shuō)明,如果散列表基于一個(gè)鍵,而該鍵沒(méi)有重寫(xiě)這些方法,這個(gè)散列表可以工作,但只有對(duì)象完全相同,鍵才被認(rèn)為是相等的。也就是說(shuō),把一個(gè)對(duì)象放在字典中時(shí),必須將它與該鍵的引用關(guān)聯(lián)起來(lái)。也不能以后用相同的值實(shí)例化另一個(gè)鍵對(duì)象。如果沒(méi)有重寫(xiě)Equals()方法和GetHashCode()方法,在字典中使用類型時(shí)就不太方便。
System.String實(shí)現(xiàn)了IEquatable接口,并重載了GetHashCode()方法。Equals()方法提供了值的比較,GetHashCode()方法根據(jù)字符串的值返回一個(gè)散列代碼。因此,在字典中把字符串用在鍵很方便。
數(shù)字類型(如Int32)也實(shí)現(xiàn)了IEquatable接口,并重載了GetHashCode()方法。但是這些類型返回的散列代碼只能映射到值上。如果希望用作鍵的數(shù)字本身沒(méi)有分布在可能的整數(shù)值范圍內(nèi),把整數(shù)用作鍵就不能滿足鍵值的平均分布規(guī)則,于是不能獲得最佳的性能。Int32并不適合在字典中使用。
如果需要使用的鍵類型沒(méi)有實(shí)現(xiàn)IEquatable接口,并根據(jù)存儲(chǔ)在字典中的鍵值重載GetHashCode()方法,就可以創(chuàng)建一個(gè)實(shí)現(xiàn)IEqualityComparer<T>接口的比較器。IEqualityComparer<T>接口定義了GetHashCode()方法和Equals()方法,并將傳遞的對(duì)象作為參數(shù),這樣可以提供與對(duì)象類型不同的實(shí)現(xiàn)方式。
2.演示字典
創(chuàng)建一個(gè)員工ID(EmployeeId)結(jié)構(gòu),用作字典的鍵。存儲(chǔ)在字典中的數(shù)據(jù)是Employee類型的對(duì)象。
該結(jié)構(gòu)的成員是表示員工的一個(gè)前綴字符和一個(gè)數(shù)字。這兩個(gè)變量都是只讀的,只能在構(gòu)造函數(shù)中初始化。字典中的鍵不應(yīng)改變,這是必須保證的?!?/p>
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); } //由于沒(méi)有填滿整數(shù)取值范圍,GetHashCode方法將數(shù)字向左移動(dòng)16位,再與原來(lái)的數(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); } //比較兩個(gè)EmployeeId對(duì)象的值 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個(gè)元素的容量。容量一般是素?cái)?shù)。 //如果指定了一個(gè)不是素?cái)?shù)的值,Dictionary<TKey,TValue>類會(huì)使用指定的整數(shù)后面緊接著的一個(gè)素?cái)?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>類支持每個(gè)鍵關(guān)聯(lián)一個(gè)值。Lookup<TKey,TElement>類把鍵映射到一個(gè)值集上。這個(gè)類在程序集System.Core中實(shí)現(xiàn),用System.Linq定義。
Lookup<TKey,TElement>類不能像一般的字典那樣創(chuàng)建,必須調(diào)用ToLookup()方法,該方法返回一個(gè)Lookup<TKey,TElement>對(duì)象。ToLookup()方法是一個(gè)擴(kuò)展方法,它可以用于實(shí)現(xiàn)了IEnumerable<T>接口的所有類。
ToLookup()方法需要一個(gè)Func<TSource,Tkey>,Func<TSource,Tkey>定義了選擇器。
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ó)家相同的對(duì)象關(guān)聯(lián)到一個(gè)鍵 var lookupRacers = racers.ToLookup(r => r.Country); foreach (Racer r in lookupRacers["Australia"]) { Console.WriteLine(r); } }
輸出:
Alan Jones Jack Brabham
4.有序字典
SortedDictionary<TKey,TValue>類是一個(gè)二叉搜索樹(shù),其中的元素根據(jù)鍵來(lái)排序。該鍵類型必須實(shí)現(xiàn)IComparable<TKey>接口。
如果鍵的類型不能排序,還可以創(chuàng)建一個(gè)實(shí)現(xiàn)了IComparer<TKey>接口的比較器,將比較器用作有序字典的構(gòu)造函數(shù)的一個(gè)參數(shù)。
SortedDictionary<TKey,TValue>和有序列表SortedList<TKey,TValue>(http://www.dbjr.com.cn/article/244111.htm)的區(qū)別:
- *SortedList<TKey,TValue>類使用的內(nèi)存比SortedDictionary<TKey,TValue>少。
- *SortedDictionary<TKey,TValue>元素的插入和刪除操作比較快。
- *在用已排序好的數(shù)據(jù)填充集合時(shí),若不需要改變?nèi)萘?,ortedList<TKey,TValue>比較快。
到此這篇關(guān)于C#集合之字典的文章就介紹到這了。希望對(duì)大家的學(xué)習(xí)有所幫助,也希望大家多多支持腳本之家。
相關(guān)文章
C#訪問(wèn)SqlServer設(shè)置鏈接超時(shí)的方法
這篇文章主要介紹了C#訪問(wèn)SqlServer設(shè)置鏈接超時(shí)的方法,涉及CommandTimeout屬性的相關(guān)設(shè)置技巧,非常簡(jiǎn)單實(shí)用,需要的朋友可以參考下2015-06-06C#簡(jiǎn)單實(shí)現(xiàn)SNMP的方法
這篇文章主要介紹了C#簡(jiǎn)單實(shí)現(xiàn)SNMP的方法,通過(guò)一個(gè)簡(jiǎn)單的自定義類分析了C#實(shí)現(xiàn)SNMP的相關(guān)技巧,具有一定參考借鑒價(jià)值,需要的朋友可以參考下2015-07-07Unity實(shí)現(xiàn)手機(jī)搖一搖震動(dòng)
這篇文章主要為大家詳細(xì)介紹了untiy實(shí)現(xiàn)手機(jī)搖一搖震動(dòng),文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2019-11-11C#中把DataTable、Dataset轉(zhuǎn)Json數(shù)據(jù)
這篇文章介紹了C#中把DataTable、Dataset轉(zhuǎn)Json數(shù)據(jù)的方法,文中通過(guò)示例代碼介紹的非常詳細(xì)。對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2022-04-04C#構(gòu)建樹(shù)形結(jié)構(gòu)數(shù)據(jù)(全部構(gòu)建,查找構(gòu)建)
這篇文章主要介紹了C#構(gòu)建樹(shù)形結(jié)構(gòu)數(shù)據(jù)(全部構(gòu)建,查找構(gòu)建),小編覺(jué)得挺不錯(cuò)的,現(xiàn)在分享給大家,也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2017-10-10