C#基礎複習（4） 之 淺析List、Dictionary

来源:https://www.cnblogs.com/sword-magical-blog/archive/2019/04/04/10657313.html
-Advertisement-
Play Games

參考資料 [1] .netCore 源碼 https://github.com/dotnet/corefx [2] 《Unity 3D腳本編程 使用C 語言開發跨平臺游戲》陳嘉棟著 [3] 《數據結構 第四版》 葉核亞編著 [4] @InCerry【淺析C Dictionary實現原理】https: ...


參考資料

[1] .netCore 源碼 https://github.com/dotnet/corefx
[2] 《Unity 3D腳本編程 使用C#語言開發跨平臺游戲》陳嘉棟著
[3] 《數據結構 第四版》 葉核亞編著
[4] @InCerry【淺析C# Dictionary實現原理】https://www.cnblogs.com/InCerry/p/10325290.html

基礎知識

  1. 在C#中，List是最常用的可變長泛型列表，類似數組，用於存儲一系列數據，使用下標進行索引。
  2. Dictionary（字典）是C#中最常用的鍵值對存儲數據結構，通過鍵（須為不可變類型）來對其中的值進行索引。

疑難解答

  1. List如何實現可變長機制？
  2. List增刪查改的效率如何？
  3. Dictionary底層如何實現？
  4. Dictionary的增刪查改效率如何？

List如何實現可變長機制？

List是C#中的可變長數組，它是ArrayList的泛型版本，由於ArrayList中所有對象都是Object，往其中加入值類型數據時會頻繁觸發裝箱拆箱（關於裝箱拆箱的詳情，可以參考我上一篇博文【C#基礎複習（2） 之 裝箱拆箱】），導致效率問題，同時還有一些關於強制轉換的安全問題，所以一般不使用ArrayList。

List底層是通過一個泛型數組進行實現，根據他的無參初始化方法可以知道，當我們使用new List<T>()的方式生成他時，他是將當前內部的數組指向了一個空數組。這段源碼內容如下：

public class List<T> : IList<T>, IList, IReadOnlyList<T>
{
    private const int DefaultCapacity = 4;

    private T[] _items; // Do not rename (binary serialization)
    private int _size; // Do not rename (binary serialization)
    private int _version; // Do not rename (binary serialization)

    private static readonly T[] s_emptyArray = new T[0];

    // Constructs a List. The list is initially empty and has a capacity
    // of zero. Upon adding the first element to the list the capacity is
    // increased to DefaultCapacity, and then increased in multiples of two
    // as required.
    public List()
    {
        _items = s_emptyArray;
    }

    ....
}

那麼問題就來了，既然初始化的時候，內部數組指向的是一個只讀的empty數組，那麼為什麼我們還可以自如地向List中增加或刪除元素呢？他是如何實現可變長機制的呢？

直接跳到List的Add方法中查看一下實現。其增加元素主要跟三個方法有聯繫，分別是Add,AddWithResize以及EnsureCapacity，下麵是它們的源碼部分。

    [MethodImpl(MethodImplOptions.AggressiveInlining)]
    public void Add(T item)
    {
        _version++;
        T[] array = _items;
        int size = _size;
        if ((uint)size < (uint)array.Length)
        {
            _size = size + 1;
            array[size] = item;
        }
        else
        {
            AddWithResize(item);
        }
    }

    // Non-inline from List.Add to improve its code quality as uncommon path
    [MethodImpl(MethodImplOptions.NoInlining)]
    private void AddWithResize(T item)
    {
        int size = _size;
        EnsureCapacity(size + 1);
        _size = size + 1;
        _items[size] = item;
    }

    private void EnsureCapacity(int min)
    {
        if (_items.Length < min)
        {
            int newCapacity = _items.Length == 0 ? DefaultCapacity : _items.Length * 2;
            // Allow the list to grow to maximum possible capacity (~2G elements) before encountering overflow.
            // Note that this check works even when _items.Length overflowed thanks to the (uint) cast
            if ((uint)newCapacity > Array.MaxArrayLength) newCapacity = Array.MaxArrayLength;
            if (newCapacity < min) newCapacity = min;
            Capacity = newCapacity;
        }
    }

    public int Capacity
    {
        get
        {
            return _items.Length;
        }
        set
        {
            if (value < _size)
            {
                ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.value, ExceptionResource.ArgumentOutOfRange_SmallCapacity);
            }

            if (value != _items.Length)
            {
                if (value > 0)
                {
                    T[] newItems = new T[value];
                    if (_size > 0)
                    {
                        Array.Copy(_items, 0, newItems, 0, _size);
                    }
                    _items = newItems;
                }
                else
                {
                    _items = s_emptyArray;
                }
            }
        }
    }

根據以上代碼，可以瞭解以下情況：

  1. 當List的容量尚且足夠時，會自動向內部的數組後面增加數據
  2. 當List的容量不足（即內部維護的_size大於等於實際數組的長度）時，調用AddWithResize方法，而AddWithResize又會調用EnsureCapacity方法進行擴容。
  3. 調用EnsureCapacity時，如果當前List容量為空（即我們使用無參構造方法new出List時），會讓當前容量增加一個預設值（即DefaultCapacity），如果當前容量不為空，那麼就讓當前容量翻倍。

在EnsureCapacity方法中僅僅只是對容量（Capacity）進行了賦值，而沒有去動真正的數組。實際上玄機在Capacity的set方法中，當容量改變時，會生成一個新的數組，然後將當前數組的所有值拷貝到新數組中。

這樣，List為什麼能自動擴容就基本清楚了。

總結一下，實際上List內部還是使用了數組對數據進行存儲，只不過在添加數據時，對用於保存數據的數組的長度與List的邏輯長度_size進行比較，當內部用於保存數據的數組的長度過小時，就會自動申請擴容，擴寬的容量是原來的兩倍。

List增刪查改的效率如何？

List增刪查改的效率也可以通過源碼分析而來，有興趣的同學可以去看參考資料[1]。下麵直接給出結論：

數據結構 Add Remove Find GetByIndex
List O(1) O(n) O(n) O(1)

其中Remove和Find都是遍歷查找，所以時間複雜度頗高。

Dictionary底層如何實現？

說到Dictionary，還是要說一下它的非泛型版本HashTable，HashTable和Dictionary內部原理類似，都是使用Hash的方法來對鍵值對進行映射，而非傳說中的紅黑樹（C#中的SortedDictionary是由紅黑樹實現），但細節上不太相同，其中HashTable使用的是雙重哈希（double hashing）的方法來避免哈希衝突，而Dictionary則是使用鏈接技術（Chaining）。

關於Hash

Hash(又譯作“散列”)是用來按關鍵字存儲和查找的技術，仔細回想一下，如果我們要在數組中查找某一個元素，常用的有以下幾種方法：

  1. 遍歷查找，時間複雜度O(n)，當數組數據量過大時將會有性能瓶頸
  2. 二分查找，時間複雜度O(logn)，只對有序的數組有效，條件過於嚴苛。

而Hash表的技術就是將查找時間降為O(1)的一項技術。他的基本原理很簡單，就是將關鍵字與要存儲的值建立一個映射關係，當我們使用關鍵字訪問數組時，就能以O(1)的時間內查找到該值。

一個Hash函數典型示例圖如下所示，其中每一個Key經過哈希函數的變換，都變成了對應的hash值。（圖片引用自https://www.cnblogs.com/InCerry/p/10325290.html）

下麵再舉一個簡單的Hash表例子，下麵的數組下標與值一一對應，如a[1]=1,a[100]=100，這樣，如果我們要查詢某個數，如99，只需根據a[99]中的值是否為0即可判斷數組記憶體不存在整型數據99。

下標 0 1 2 ... 99 100
值 0 1 0 ... 99 0

但是上面這個例子有一個缺陷，那就是，如果要存儲數字10000，而就要開闢長度為1w的數組，如果數組元素不密集，將會造成許多浪費。這時，就可以使用Hash函數來對關鍵字進行一些處理。

Hash函數中可以通過一系列的操作來使得關鍵字的數值儘量小而不會重覆，比如取餘操作。

同樣是舉一個簡單的例子，以 關鍵字 % length（數組長度） 這樣的哈希函數來像下麵這樣存儲數據。

下標 0 1 2 3
值 1000 1009 10 123
hash函數處理關鍵字 1000%4=0 1009%4=1 10%4=2 123%4=3

其中關鍵字與值一一對應，關鍵字通過hash函數的處理變成了對應該值的下標。

Hash衝突

根據上面的描述，可以看出Hash函數要保證根據關鍵字算出的每一個Hash值都不重覆是一件並不簡單的事。

舉個例子，同樣是使用上面那個 關鍵字 % length 的hash函數，如果要向加入值1000和400就會出現問題，因為它們經過計算之後得到的下標值都為0。這時就發生了Hash衝突（也稱為Hash碰撞）。

關於Hash衝突，一個更為準確的定義如下：

設兩個關鍵字k1和k2(k1!=k2)，如果hash(k1)=hash(k2)，即它們的散列地址相同，表示不同關鍵字的多個元素映射到同一個存儲位置，這種現象稱為衝突。

當發生Hash衝突時，我們就用對衝突進行處理。常見的處理衝突的方法有兩種，一種是開放定址法（如線性探查法、二次探查法），一種是鏈地址法。

線性探查法

線性探查法的描述如下(引用自《數據結構》)：

  1. 設一個元素關鍵字為k，其散列地址為i = hash(k)。
  2. 若散列表中i位置已存儲元素，則產生衝突，探測下一個位置i+1是否為空，若空，則存儲該元素；
  3. 否則繼續探測下一個位置i+2，以此類推。

探測的地址序列是i+1、i+2、....直至找到一個空位置。

設有hash函數如下：

int hash(int data,int[] nums){
    return data % nums.length;
}

線性探查法的查找過程如下圖所示：

根據以上描述，可以發現，使用線性探查法來解決hash衝突，當衝突越多時，hash表查找速度越慢，這是因為在下次插入或者查找Hash表的時候，衝突依然存在。

二次探查法

針對線性探查法出現的問題，一種改進方法是二次探查法。
也就是Hash衝突聚集在某個範圍內，每次向下檢查平方的步長。

舉個例子，對於線性探查法來說，如果位置index滿了，他會檢查index+1,index+2,index+3,....,index+n，以此類推。

對於二次探查法來說，如果位置index滿了，他會檢查index+1^2^ ,index+2^2^ , index+3^2^ , ... , index+n^2^。

其操作過程如圖所示：

鏈地址法

與開放定址法不同，鏈地址法在遇到衝突時不會將衝突的元素放到當前數組的前面或後面，而是將同類衝突（即hash(i)都等於k的元素）放入一個鏈表，在查找時，首先根據hash函數找到鍵值，然後沿著這條鏈表向後面進行查找。

《數據結構》一書中對此是這樣描述的：

  1. 採用散列數組存儲元素，將元素key存儲在數組的hash(key)位置
  2. 採用一條同義詞單鏈表存儲一組同義詞衝突元素，散列數組中各元素都可鏈接同一條同義詞單鏈表。

設有hash函數如下：

int hash(int data,int[] nums){
    return data % nums.length;
}

鏈地址法的操作流程如下圖所示：

負載因數

從上面的分析中可以看出，當散列表一開始申請的數組空間越小、衝突的元素越多時，每次插入、查詢元素的所消耗的時間會越來越多（無論採用哪種解決衝突的方法）。

對於這一點，C#在HashTable中設計了一個叫負載因數的東西。在《Unity跨平臺開發》中是這樣描述它的：

負載因數loadFactor定義範圍在0.1~1.0，它指定了哈希表中元素數量與位置數量之間最大的比例。例如，當loadFactor=0.5時，說明哈希表中只有一半的空間存放了元素值，其餘一半都為空。
向Hashtable類的實例添加新元素時，需要檢查以保證元素與空間大小的比例不會超過最大比例。如果超過了，HashTable類實例的空間將被擴充。

Dictionary也會在必要時擴容，但它的擴容並不是依據loadFactor設計的。這個在後面說說。

Hash桶

有時候Hash函數算出來的HashCode會大於我們用於存放數據的數組的長度，這時我們就不能粗暴的將HashCode直接作為鍵值（內部實現就是作為保存數據的下標）對數據進行映射。

對於這個問題，我們可以使用Hash桶演算法來解決。

對於Hash桶我理解的還不是很透徹，這裡引用一下@InCerry博主對Hash桶演算法的介紹：

因為這樣的一個問題，所以人們就將生成的HashCode以分段的形式來映射，把每一段稱之為一個Bucket（桶），一般常見的Hash桶就是直接對結果取餘。

假設將生成的hashCode可能取值有2^32個，然後將其切分成一段一段，使用8個桶來映射，那麼就可以通過bucketIndex = HashFunc(key1) % 8這樣一個演算法來確定這個hashCode映射到具體的哪個桶中。

大家可以看出來，通過hash桶這種形式來進行映射，所以會加劇hash的衝突。

Dictionary實現細節

有了上面的理論基礎，我們就可以來看一下Dictionary的源碼到底是如何實現的了。

重要數據項

Dictionary中重要的屬性如下所示：

private struct Entry
{
    public int hashCode;    // 當前鍵經過Hash函數運算後得到的值，如果為-1表示此項為空
    public int next;        // 表示當前數據的key的同類衝突的下一個元素，-1表示結尾
    public TKey key;           // 當前數據的鍵
    public TValue value;         // 當前數據的值
}
private int[] _buckets;     // Hash桶，它的值是指向_entries數組的下標
private Entry[] _entries;   // 用於存儲數據的數組
private int _count;         // 當前entries的下標
private int _freeList;  // 被刪除的Entry在entries中的下標，構成一個單鏈表，該鏈表中所有元素都是空閑的
private int _freeCount; // 有多少個空閑的位置（即有多少個數據項Entry被刪除了）
private int _version;   // 當前Dictionary版本，用於防止字典在迭代過程中被修改

其中Entry是Dictionary中的重要數據結構，對於它的屬性，簡單舉個例子，比如我們平常使用Add("xx",yy)方法，那麼就會創建出一個新的Entry對象，它的key是"xx"，它的hashCode是hash("xx")，它的value是yy。可以看出我們放進字典中的鍵和值被包裝成了這個數據結構。

其中next屬性我註釋說的比較模糊，這裡再仔細的說一下。
前面我們說過C#中的Dictionary是使用鏈地址法來解決Hash衝突的，這個Next屬性就是用來實現鏈地址法的，它指向了下一個、鍵的hashCode值與當前數據的hashCode值相同的數據。

什麼意思呢？簡單來說就是Entry中的next表示在entries數組中的某一個數據項，next的值就是該數據項（Entry）在entries數組中的下標。下麵畫了一幅圖來解釋這個next的意思，通過這樣next的連接，就實現了一個同類衝突的單鏈表。

字典中的Add方法實現細節與效率分析

下麵我們直接圍繞一次Add方法中，發生了什麼過程了講解它的實現細節。為啥是Add方法呢，因為觀察源碼我們可以知道，我們平時常用的map["xx"]=yy這種方法原理和Add實際上是差不多的，只不過Add方法在遇到已有Key時會拋出異常，Add和this[]=yy方法如下所示：

public TValue this[TKey key]
{
    get
    {
        int i = FindEntry(key);
        if (i >= 0) return _entries[i].value;
        ThrowHelper.ThrowKeyNotFoundException(key);
        return default;
    }
    set
    {
        bool modified = TryInsert(key, value, InsertionBehavior.OverwriteExisting);
        Debug.Assert(modified);
    }
}

public void Add(TKey key, TValue value)
{
    bool modified = TryInsert(key, value, InsertionBehavior.ThrowOnExisting);
    Debug.Assert(modified); // If there was an existing key and the Add failed, an exception will already have been thrown.
}

首先，假設Dictionary中已有Hash桶和entries數組的長度均為7，hash("aa")==hash("bb")==hash("cc")=11，hash("dd")=2（註意只是假設），其大致示意圖如下：

下麵根據將待插入數據全部插入Dictionary數據結構中。

  1. 首先對第一個待插入數據"aa"->99的鍵進行hash操作，可知hash("aa")=11，hashCode大於hash桶的數量所以要對它進行一個取餘操作，即 hash("aa") % len(_buckets) = 4。
    可知我們要在hash桶中下標為4的地方存放數據。但是_buckets是整型數組，不能存Entry型數據，所以將Entry數據存放到_entries數組的空閑位置。
    空閑位置是什麼呢，其實就是count屬性所表示的下標。

上面的步驟用偽代碼來描述是這樣的：

// entries當前空閑位置存放當前數據
_entries[_count] = Entry;(即當前數據)
// 計算數據放到hash桶的哪個地方
int index = hash("aa") % len(_buckets);    // => 4
// 使buckets中的數指向entries中存放這個數據的下標處
_buckets[index] = count;

_count++;   // 使得count指向下一個空閑數據

插入數據"aa"->99後，示意圖如下：

  1. 對第二個待插入數據"dd"->11的鍵進行hash操作，可知 hash("dd")%len(_buckets)=2，即要在下標為2的地方存數據。流程大致跟步驟1類似。

插入數據"dd"->11後，內部結構示意圖如下：

  1. 對第三個待插入數據"cc"->3的鍵進行hash操作，可知hash("cc")%len(_buckets)=4，即要在hash桶下標為4的地方保存數據。但是下標為4的地方已經有數據了，這時就發生了衝突。

Dictionary使用鏈地址法來解決hash衝突，此時將新的Entry（包裝了"cc"數據的對象）的next指向之前已經存在的元素，再讓_buckets[index]指向當前新的Entry，這樣，就在_buckets[index]處形成了一個同類衝突元素的單鏈表。

插入數據“cc”後，內部結構示意圖如下所示：

總結
經過前面的三個步驟，三個待插入數據就被插入進了Dictionary中，這裡總結一下Dictionary中插入一個數據要進行的步驟：

  1. 計算待插入數據鍵的HashCode值
  2. 將HashCode映射到Hash桶中，int index = HashCode % _buckets.length
  3. 在_entries數組的空閑處（即count或freelist下標處）“創建”一個包裝好插入數據的Entry對象。（這裡不是說真創建了一個對象，而是將那個位置的Entry屬性的key,hashCode,value值改為待插入數據的屬性）
  4. _buckets[index] 指向 _entries[count]處，插入完成

上面步驟對應的源碼部分如下：

private bool TryInsert(TKey key, TValue value, InsertionBehavior behavior)
{
    ....
    // 找到hashcode對應的Hash桶的位置
    ref int bucket = ref _buckets[hashCode % _buckets.Length];
    ....

    // 獲得當前數組中的空閑位置
    int count = _count;

    // 如果位置不夠，那麼擴容
    if (count == entries.Length)
    {
        Resize();
        bucket = ref _buckets[hashCode % _buckets.Length];
    }
    index = count;
    _count = count + 1;
    entries = _entries;

    ....

    // 目標Entry
    ref Entry entry = ref entries[index];

    ....

    // 將該處空閑的Entry的屬性改完插入數據的屬性
    entry.hashCode = hashCode;
    // Value in _buckets is 1-based
    entry.next = bucket - 1;
    entry.key = key;
    entry.value = value;
    // Value in _buckets is 1-based
    bucket = index + 1;
    _version++;

    ....
}

在前面插入的步驟中，我們可以看到內部變數freeList和freeCount並沒有發生變動，這是因為他們是跟刪除操作(remove)息息相關的,後面講講。

效率分析
根據上面的操作，可以看出Dictionary中，插入一個數據的時間是常數時間，即時間複雜度O(1)。

字典中的Find方法實現細節與效率分析

以上面插入完三個數據的Dictionary為例，下麵講講Find方法的實現細節和效率。

該Dictionary的內部結構如下所示：

假設現在我們執行類似

map["aa"]

的操作，要獲取鍵為"aa"存儲的數據，會經過如下步驟：

  1. 計算key的Hash值，並算出在Hash桶的位置，即 hash("aa") % length
  2. 到達該Hash桶後，沿著這個Entry的next方法一路用"aa" == entry.key?比較過去。這裡表達的意思是，一直沿著這個單鏈表向前找，直到找到key值相同的Entry，那麼這個Entry保存的數據就是我們要找的值。

在Dictionary中還有一個常見的方法是GetValueOrDefault（）,這個方法與上面步驟不同的地方是當沿著單鏈表一直找不到對應鍵值且entry.next==-1時，就會返回預設值。

效率分析
根據以上操作，很顯然查找時間也是常數時間，也就是時間複雜度O(1)，但是這個時間會隨著Dictionary內部衝突的變多而增大，當所有元素衝突到一起時，每次查找都要消耗O(N)的時間。

為瞭解決這個問題，Dictionary內部會在合適的時候進行擴容並更換Hash函數。

字典中的Remove方法實現細節與效率分析

老實說我比較少用到字典的Remove方法額（汗顏），關於Remove方法，前面的步驟和查找是類似的。即先找到當前數據對應的Hash桶位置（不如說增刪改查中查是最核心的，因為增刪改第一個操作都是查）。

後面的步驟的執行如下帶註釋的代碼所示。（代碼引用自@InCerry的博文《淺析C# Dictionary實現原理》）

public bool Remove(TKey key) {
    if(key == null) {
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
    }

    if (buckets != null) {
        // 1. 通過key獲取hashCode
        int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
        // 2. 取餘獲取bucket位置
        int bucket = hashCode % buckets.Length;
        // last用於確定是否當前bucket的單鏈表中最後一個元素
        int last = -1;
        // 3. 遍歷bucket對應的單鏈表
        for (int i = buckets[bucket]; i >= 0; last = i, i = entries[i].next) {
            if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) {
                // 4. 找到元素後，如果last< 0，代表當前是bucket中最後一個元素，那麼直接讓bucket內下標賦值為 entries[i].next即可
                if (last < 0) {
                    buckets[bucket] = entries[i].next;
                }
                else {
                    // 4.1 last不小於0，代表當前元素處於bucket單鏈表中間位置，需要將該元素的頭結點和尾節點相連起來,防止鏈表中斷
                    entries[last].next = entries[i].next;
                }
                // 5. 將Entry結構體內數據初始化
                entries[i].hashCode = -1;
                // 5.1 建立freeList單鏈表
                entries[i].next = freeList;
                entries[i].key = default(TKey);
                entries[i].value = default(TValue);
                // *6. 關鍵的代碼，freeList等於當前的entry位置，下一次Add元素會優先Add到該位置
                freeList = i;
                freeCount++;
                // 7. 版本號+1
                version++;
                return true;
            }
        }
    }
    return false;
}

總結一下，刪除操作就是如下步驟：

  1. 找到目標Entry
  2. 將Entry初始化（HashCode初始化為-1）
  3. 將這個空閑的Entry（因為數據被刪了，所以空閑）插入到Dictionary內部維護的freeList單鏈表中(entries[i].next=freeList這一句)，等待下一次插入數據時，先找到這個freeList中的Entry來插。

效率分析
根據上面代碼所示，Remove操作主要消耗時間的還是查找這一塊，它的時間複雜度和查找相同，為O(1)，但隨著衝突的增多查找時間會逐漸加大。

字典何時擴容

Dictionary內部實際上是維護了兩個數組對數據進行保存，既然是數組，那麼自然會有數組放滿的風險，根據前面的Add方法源碼的分析，可以看到其中有一行當count（空閑位置）== hash桶長度時，會進行擴容操作。

這是擴容比較直觀的觸發條件。在另外一種情況下Dictionary也會觸發擴容，這就是當碰撞次數過多時，它會自動擴容。

那麼什麼是碰撞呢？

在FindEntry方法中，當我們沿著同類衝突元素的單鏈表一直找下去的時候，每遍歷一個元素，碰撞次數collisionCount就+1，當碰撞次數超過設定好的閾值時，就會觸發擴容。

FindEntry方法源碼中觸發碰撞的代碼：

private int FindEntry(TKey key)
{
    ....
    // 碰撞次數
    int collisionCount = 0;
    ...
    do
    {
        if ((uint)i >= (uint)entries.Length || (entries[i].hashCode == hashCode && EqualityComparer<TKey>.Default.Equals(entries[i].key, key)))
        {
            break;
        }

        i = entries[i].next;
        if (collisionCount >= entries.Length)
        {
            ThrowHelper.ThrowInvalidOperationException_ConcurrentOperationsNotSupported();
        }
        // 在遍歷這個單鏈表的時候，每查找失敗一次，碰撞次數+1
        collisionCount++;
    } while (true);
    ...
}

很顯然這個碰撞次數就關係到了我們前面說的查找方法的消耗時間，所以當碰撞次數超過閾值，Dictionary就自動擴容了，並且在擴容後還會使用新的Hash函數來進行HashCode值。

version（版本）和迭代的關係

在C#中，增、刪、改操作都會使得Dictionary中的version（版本）變數改變。

這裡依舊引用一下@InCerry大大的博文對於這個的解釋。

迭代過程中不允許集合出現變化。如果在Java中遍歷直接刪除元素，會出現詭異的問題，所以.Net中就使用了version來實現版本控制。

那麼如何在迭代過程中實現版本控制的呢？我們看一看源碼就很清楚的知道。

在迭代器初始化時，就會記錄dictionary.version版本號，之後每一次迭代過程都會檢查版本號是否一致，如果不一致將拋出異常。

Dictionary的增刪查改效率如何？

經過上面的分析，我們就可以知道Dictionary的增刪改查效率了，列表如下：

數據結構 Add Remove Find Alter
Dictionary O(1) O(1) O(1) O(1)

可以看到字典這個數據結構還是相當給力的，基本的操作流程基本都是O(1)的複雜度，不過它會消耗更多的空間就是了（畢竟使用了兩個數組進行維護）。

總結

這篇博文也是寫的相當久，因為我基礎不是很牢固，一開始寫這個系列的就是為了鞏固下C#基礎，所以可能出現了一些錯誤，如果有讀者看到，還請不吝指出，我會非常感激的。（話說上一篇String和StringBuilder的錯誤還沒改。。懶癌發作。。）

本篇文章後半段關於Dictionary的部分大部分是參考@InCerry的博文【淺析C# Dictionary實現原理】(講的相當清楚)所寫的，emmmm，如果有什麼版權方面的問題，請聯繫我，我會立即刪除這篇文章。


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

-Advertisement-
Play Games
更多相關文章
  • 分分鐘鐘學會Python - 數據類型（int、bool、str）
    第三天學習內容 今日內容 1、整型（int） 2、布爾類型(bool) 3、字元串(str) 內容詳細 1、整型 Python中的整型用int表示。 1.python2中： 在32位機器上，整數的位數為32位，取值範圍為 2 31～2 31 1，即 2147483648～2147483647 在64 ...
  • Python爬蟲（2）：urllib庫
    爬蟲常用庫urllib 註：運行環境為PyCharm urllib是Python3內置的HTTP請求庫 urllib.request：請求模塊 urllib.error：異常處理模塊 urllib.parse：url解析模塊 urllib.robotparse：robot.txt解析模塊 1、url ...
  • 快速排序的Java實現
    1 package quicksort; 2 3 import org.junit.Test; 4 5 import java.util.Arrays; 6 7 public class QuickSort { 8 9 @Test 10 public void setUp() throws Exce... ...
  • Java數據解析之JSON
    文章大綱 一、JSON介紹二、常見框架介紹與實戰三、Studio中GsonFormat插件使用四、項目源碼下載（含參考資料）五、參考文檔 一、JSON介紹 1. 簡介 JSON 的全稱是 JavaScript Object Notation,是一種輕量級的數據交換格 式。 2. 特點 (1)JSON ...
  • 併發系列（3）之 AbstractQueuedSynchronizer 源碼分析
    本文將主要講述 的內部結構和實現邏輯，在看本文之前最好先瞭解一下 隊列鎖， 就是根據 隊列鎖的變種實現的，因為本身 比較複雜不容易看清楚他本身的實現邏輯，所以查看 隊列鎖的實現，可以幫助我們理清楚他內部的關係；關於隊列鎖的內容可以參考 ， "CLH、MCS 隊列鎖簡介" ； 一、AQS 結構概述 在 ...
  • 樂位元組-Java8新特性之函數式介面
    上一篇小樂帶大家學過 Java8新特性-Lambda表達式，那什麼時候可以使用Lambda？通常Lambda表達式是用在函數式介面上使用的。從Java8開始引入了函數式介面，其說明比較簡單:函數式介面(Functional Interface)就是一個有且僅有一個抽象方法，但是可以有多個非抽象方法的 ...
  • Java同步容器和併發容器
    同步容器 在 Java 中，同步容器主要包括 2 類： Vector、Stack、HashTableCollections 類中提供的靜態工廠方法創建的類（由 Collections.synchronizedXxxx 等方法） Vector 實現了 List 介面，Vector 實際上就是一個數組， ...
  • 一場關於 .net core 和 .net framework 編碼的案情分析
    案情背景 目前公司做新項目，基本所有新項目都是用.net core來做，舊項目一半還是基於 .net framework下麵，一半已經遷移到了core平臺。在做新項目的時候，有個功能需要對接到舊項目那邊的介面，功能也不複雜，就是對接介面的參數需要通過簽名，然後進行MD5加密傳輸過去，舊項目那邊也有相 ...
一周排行
    -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.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類