C#集合之字典

来源:http://www.cnblogs.com/afei-24/archive/2017/05/10/6835222.html
-Advertisement-
Play Games

字典表示一種複雜的數據結構，這種數據結構允許按照某個鍵來訪問元素。字典也稱為映射或散列表。 字典的主要特性是能根據鍵快速查找值。也可以自由添加和刪除元素，這有點像List<T>（http://www.cnblogs.com/afei-24/p/6824791.html），但沒有在記憶體中移動後續元素的 ...


　　字典表示一種複雜的數據結構，這種數據結構允許按照某個鍵來訪問元素。字典也稱為映射或散列表。
　　字典的主要特性是能根據鍵快速查找值。也可以自由添加和刪除元素，這有點像List<T>（http://www.cnblogs.com/afei-24/p/6824791.html），但沒有在記憶體中移動後續元素的性能開銷。
　　下圖是一個簡化表示，鍵會轉換位一個散列。利用散列創建一個數字，它將索引和值關聯起來。然後索引包含一個到值的鏈接。一個索引項可以關聯多個值，索引可以存儲為一個樹型結構。
　　
　　.NET Framework提供了幾個字典類。最主要的類是Dictionary<TKey,TValue>。

1.鍵的類型
　　用作字典中的鍵的類型必須重寫Object類的GetHashCode()方法。只要字典類需要確定元素的位置，它就要調用GetHashCode()方法。GetHashCode()方法返回的int有字典用於計算在對應位置放置元素的索引。後面介紹這個演算法，現在只需要知道它涉及素數，所以字典的容量是一個素數。
　　GetHashCode()方法的實現代碼必須滿足的要求：
　　　　*相同的對象應總是返回相同的值
　　　　*不同的對象可以返回相同的值
　　　　*它應執行的比較快，計算的開銷不大
　　　　*它不能拋出異常
　　　　*它應至少使用一個實例欄位
　　　　*散列代碼值應平均分佈在int可以存儲的這個數字範圍上
　　　　*散列代碼最好在對象的生存期中不發生變化
　　字典的性能取決於GetHashCode()方法的實現代碼。

　　散列代碼值應平均分佈在int可以存儲的這個數字範圍上的原因：
　　如果兩個鍵返回的散列代碼值會得到相同的索引，字典類就必須尋找最近的可用空閑位置來存儲第二個數據項，這需要進行一定的搜索，以便以後檢索這一項。顯然這會降低性能，如果在排序的時候許多鍵都有相同的索引這中衝突會更可能出現。根據Microsoft的演算法工作方式，當計算出來的散列代碼值平均分佈在int.MinValue和int.MaxValue之間時，這種風險會降到最低。

　　除了實現GetHashCode()方法之外，鍵類型還必須實現IEquatable<T>.Equals()方法，或重寫Object.Equals()方法。0因為不同的鍵對象可能返回相同的散列代碼，所以字典使用Equals()方法來比較鍵。字典檢查兩個鍵A和B是否相等，並調用A.Equals(B)方法。這表示必須確保下述條件總是成立：
　　　　如果A.Equals(B)返回true，則A.GetHashCode()和B.GetHashCode()總是返回相同的散列代碼。
　　這聽起來有點奇怪，但它很重要。如果上述條件不成立，這個字典還能工作，但會出現，把一個對象放在字典中後，就再也檢索不到它，或者返回了錯誤的項。
　　所以，如果為Equals()方法提供了重寫版本，但沒提供GetHashCode()方法的重寫版本，C#編譯器會顯示一個警告。

　　對於System.Object，這個條件為true，因為Equals()方法只是比較引用，GetHashCode()方法實際上返回一個僅基於對象地址的散列代碼。這說明，如果散列表基於一個鍵，而該鍵沒有重寫這些方法，這個散列表可以工作，但只有對象完全相同，鍵才被認為是相等的。也就是說，把一個對象放在字典中時，必須將它與該鍵的引用關聯起來。也不能以後用相同的值實例化另一個鍵對象。如果沒有重寫Equals()方法和GetHashCode()方法，在字典中使用類型時就不太方便。

　　System.String實現了IEquatable介面，並重載了GetHashCode()方法。Equals()方法提供了值的比較，GetHashCode()方法根據字元串的值返回一個散列代碼。因此，在字典中把字元串用在鍵很方便。

　　數字類型（如Int32）也實現了IEquatable介面，並重載了GetHashCode()方法。但是這些類型返回的散列代碼只能映射到值上。如果希望用作鍵的數字本身沒有分佈在可能的整數值範圍內，把整數用作鍵就不能滿足鍵值的平均分佈規則，於是不能獲得最佳的性能。Int32並不適合在字典中使用。

　　如果需要使用的鍵類型沒有實現IEquatable介面，並根據存儲在字典中的鍵值重載GetHashCode()方法，就可以創建一個實現IEqualityComparer<T>介面的比較器。IEqualityComparer<T>介面定義了GetHashCode()方法和Equals()方法，並將傳遞的對象作為參數，這樣可以提供與對象類型不同的實現方式。

2.演示字典
　　創建一個員工ID（EmployeeId）結構，用作字典的鍵。存儲在字典中的數據是Employee類型的對象。
　　該結構的成員是表示員工的一個首碼字元和一個數字。這兩個變數都是只讀的，只能在構造函數中初始化。字典中的鍵不應改變，這是必須保證的。
 　　

　　　　　　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);
            }
            
            //由於沒有填滿整數取值範圍，GetHashCode方法將數字向左移動16位，再與原來的數字進行異或操作，
            //最後將結果乘以16進位數0x15051505。這樣，散列代碼在整數取值區域上的分佈就很均勻。
            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()
        {
            //構造函數指定了31個元素的容量。容量一般是素數。
            //如果指定了一個不是素數的值，Dictionary<TKey,TValue>類會使用指定的整數後面緊接著的一個素數
          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>類支持每個鍵關聯一個值。Lookup<TKey,TElement>類把鍵映射到一個值集上。這個類在程式集System.Core中實現，用System.Linq定義。

　　Lookup<TKey,TElement>類不能像一般的字典那樣創建，必須調用ToLookup()方法，該方法返回一個Lookup<TKey,TElement>對象。ToLookup()方法是一個擴展方法，它可以用於實現了IEnumerable<T>介面的所有類。
     ToLookup()方法需要一個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));
          //國家相同的對象關聯到一個鍵
          var lookupRacers = racers.ToLookup(r => r.Country);

          foreach (Racer r in lookupRacers["Australia"])
          {
            Console.WriteLine(r);
          }

        }

輸出：
　　Alan Jones
　　Jack Brabham

4.有序字典
　　SortedDictionary<TKey,TValue>類是一個二叉搜索樹，其中的元素根據鍵來排序。該鍵類型必須實現IComparable<TKey>介面。
　　如果鍵的類型不能排序，還可以創建一個實現了IComparer<TKey>介面的比較器，將比較器用作有序字典的構造函數的一個參數。
　　SortedDictionary<TKey,TValue>和有序列表SortedList<TKey,TValue>(http://www.cnblogs.com/afei-24/p/6830376.html)的區別：
　　　　*SortedList<TKey,TValue>類使用的記憶體比SortedDictionary<TKey,TValue>少。
　　　　*SortedDictionary<TKey,TValue>元素的插入和刪除操作比較快。
　　　　*在用已排序好的數據填充集合時，若不需要改變容量，ortedList<TKey,TValue>比較快。


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 1.0 添加WEB API項目並按註釋生成文檔（多項目結構）
    1.新建ASP.NET 項目，模板選擇如圖 2.選擇Web API，並選擇不進行身份驗證方式 成功後我們看到這個結果。 至於其它三種身份驗證方式，不太適合我的使用。而且這種方式也可以在代碼里去實現身份驗證，比較符合已有資料庫的情況，這裡不寫。 3.給項目進行配置修改 3.1 修改對應項目生成路徑。 ...
  • C#語言中的修飾符
    public：公有訪問。不受任何限制。private：私有訪問。只限於本類成員訪問，子類和實例都不能訪問。protected：保護訪問。只限於本類和子類訪問，實例不能訪問。internal：內部訪問。只限於本項目(程式集)內訪問，其他不能訪問。protected internal ：內部保護訪問。只 ...
  • C#基礎---值類型和引用類型
    1、先附上一份值類型和引用類型各自的成員 2、值類型和引用類型的區別 值類型直接存儲其值，引用類型存儲其值的引用 值類型變數都存儲在堆棧中，引用類型在托管堆中分配存儲單元 值類型變數不能為null，必須有確定的值，引用類型被賦值前的值都是null 值類型是從System.ValueType類繼承而來 ...
  • C#集合之不變的集合
    如果對象可以改變其狀態，就很難在多個同時運行的任務中使用。這些集合必須同步。如果對象不能改變器狀態，就很容易在多個線程中使用。 Microsoft提供了一個新的集合庫：Microsoft Immutable Collection。顧名思義，它包含不變的集合類————創建後不能改變的集合類。該類在Sy ...
  • EntityFramework Core 學習掃盲
    0. 寫在前面 1. 建立運行環境 2. 添加實體和映射資料庫 1. 準備工作 2. Data Annotations 3. Fluent Api 3. 包含和排除實體類型 1. Data Annotations [NotMapped] 排除實體和屬性 2. Fluent API [Ignore] ...
  • C#集合之可觀察的集合
    如果需要集合中的元素何時刪除或添加的信息，可以使用ObservableCollection<T>類。這個類是為WPF定義的，這樣UI就可以得知集合的變化。這個類在程式集WindowsBase中定義，需要引用這個程式集。 ObservableCollection<T>類派生自Collection<T> ...
  • C#集合之集(set)
    包含不重覆元素的集合稱為“集（set）”。.NET Framework包含兩個集HashSet<T>和SortedSet<T>，它們都實現ISet<T>介面。HashSet<T>集包含不重覆元素的無序列表，SortedSet<T>集包含不重覆元素的有序列表。 ISet<T>介面提供的方法可以創建合集 ...
  • ListView控制項詳解
    ListView是個較為複雜的控制項 ListView是個較為複雜的控制項 ListView是個較為複雜的控制項 1.定義 把它拽進來，系統會自動在Designer.cs里添加一個 this.listView1 = new System.Windows.Forms.ListView(); 2.初始化，確定 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類