VB.net 2010 視頻教程 VB.net 2010 視頻教程 VB.net 2010 視頻教程
SQL Server 2008 視頻教程 c#入門經典教程 Visual Basic從門到精通視頻教程
當前位置:
魔兽世界wow > 編程開發 > c#教程 >
  • C#教程之C#基礎復習(4) 之 淺析List、Dictionary

  • 2019-04-13 19:03 來源:未知

參考資料

魔兽世界wow www.geyjm.icu [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)的復雜度,不過它會消耗更多的空間就是了(畢竟使用了兩個數組進行維護)。

相關教程