.net源码分析 – Dictionary泛型

绝地灬酷狼 2021-06-26 16:06 365阅读 0赞

`Dictionary<TKey, TValue>`源码地址：[https://github.com/dotnet/corefx/blob/master/src/System.Collections/src/System/Collections/Generic/Dictionary.cs][https_github.com_dotnet_corefx_blob_master_src_System.Collections_src_System_Collections_Generic_Dictionary.cs]

## 接口 ##

`Dictionary<TKey, TValue>`和`List<T>`的接口形式差不多，不重复说了，可以参考`List<T>`那篇。  
![在这里插入图片描述][20181129154729548.png]

## 变量 ##

看下有哪些成员变量：

private int[] buckets;
    private Entry[] entries;
    private int count;
    private int version;
    
    private int freeList;
    private int freeCount;
    private IEqualityComparer<TKey> comparer;
    private KeyCollection keys;
    private ValueCollection values;
    private Object _syncRoot;

`buckets`是一个`int`型数组，具体什么用现在还未知，后面看，暂时可以理解成区，像硬盘我们一般会做分区归类方便查找。

`entries`是`Entry`数组，看看`Entry`:

private struct Entry
    { 
        public int hashCode;    // Lower 31 bits of hash code, -1 if unused
        public int next;        // Index of next entry, -1 if last
        public TKey key;           // Key of entry
        public TValue value;         // Value of entry
    }

是个结构，里面有`key, value`, 说明我们`Dictionary`的`key`和`value`就是用这个结构保存的，另外还有`hashcode`和`next`，看起来像链表一样，后面用到时再具体分析其用处。

`count`：和`List <T>`一样，是指包括元素的个数（这里其实也不是真正的个数，下面会讲），并不是容量

`version`: `List <T>`篇讲过，用来遍历时禁止修改集合

`freeList`, `freeCount`这两个看起来比较奇怪，比较难想到会有什么用，在添加和删除项时会用到它们，后面再讲。

`comparer`: `key`的比较对象，可以用它来获取`hashcode`以及进行比较`key`是否相同

`keys`, `values`这个我们平常也有用到，遍历`keys`或`values`有用

`_syncRoot`，`List<T>`篇也讲过，线程安全方面的，`Dictionary`同样没有用到这个对象，`Dictionary`也不是线程安全的，在多线程环境下使用需要自己加锁。  
例子

`Dictionary`的代码比`List`相对复杂些，下面不直接分析源码，而是以下面这些常用例子来一步一步展示`Dictionary`是怎么工作的：

Dictionary<string, string> dict = new Dictionary<string, string>();
    
    dict.Add("a", "A");
    
    dict.Add("b", "B");
    
    dict.Add("c", "C");
    
    dict["d"] = "D";
    
    dict["a"] = "AA";
    
    dict.remove("b");
    
    dict.Add("e", "E");
    
    var a = dict["a"];
    
    var hasA = dict.ContainsKey("a");

这里对`hashcode`做些假设，方便分析：

"a"的`hashcode`为3

"b"的`hashcode`为4

"c"的`hashcode`为6

"d"的`hashcode`为11

"e"的`hashcode`为10  
构造函数

先看第一句，`new` 一个`Dictionary<string, string>`，看源码里的构造函数，有6个

public Dictionary() : this(0, null) {  }
    
    public Dictionary(int capacity) : this(capacity, null) {  }
    
    public Dictionary(IEqualityComparer<TKey> comparer) : this(0, comparer) {  }
    
    public Dictionary(int capacity, IEqualityComparer<TKey> comparer)
    { 
        if (capacity < 0) throw new ArgumentOutOfRangeException(nameof(capacity), capacity, "");
        if (capacity > 0) Initialize(capacity);
        this.comparer = comparer ?? EqualityComparer<TKey>.Default;
    }
    
    public Dictionary(IDictionary<TKey, TValue> dictionary) : this(dictionary, null) {  }
    
    public Dictionary(IDictionary<TKey, TValue> dictionary, IEqualityComparer<TKey> comparer) :
        this(dictionary != null ? dictionary.Count : 0, comparer)
    { 
        if (dictionary == null)
        { 
            throw new ArgumentNullException(nameof(dictionary));
        }
        if (dictionary.GetType() == typeof(Dictionary<TKey, TValue>))
        { 
            Dictionary<TKey, TValue> d = (Dictionary<TKey, TValue>)dictionary;
            int count = d.count;
            Entry[] entries = d.entries;
            for (int i = 0; i < count; i++)
            { 
                if (entries[i].hashCode >= 0)
                { 
                    Add(entries[i].key, entries[i].value);
                }
            }
            return;
        }
    
        foreach (KeyValuePair<TKey, TValue> pair in dictionary)
        { 
            Add(pair.Key, pair.Value);
        }
    }

大部分都是用默认值，真正用到的是`public Dictionary(int capacity, IEqualityComparer<TKey> comparer)`，这个是每个构造函数都要调用的，看看它做了什么：

`if (capacity > 0) Initialize(capacity);` 当`capacity`大于0时，也就是显示指定了`capacity`时才会调用初始化函数，`capacity`指容量，`List<T>`里也有说过，不同的是`Dictionary`只能在构造函数里指定`capacity`，而`List<T>`可以随时指定。接下来看看初始化函数做了什么：

private void Initialize(int capacity)
    { 
        int size = HashHelpers.GetPrime(capacity);
        buckets = new int[size];
        for (int i = 0; i < buckets.Length; i++) buckets[i] = -1;
        entries = new Entry[size];
        freeList = -1;
    }

`HashHelpers.GetPrime(capacity)`根据传进来的`capacity`获取一个质数，质数大家都知道 2，3，5，7，11，13等等除了自身和1，不能被其他数整除的就是质数，具体看看这个获取质数的函数：

public static readonly int[] primes = { 
        3, 7, 11, 17, 23, 29, 37, 47, 59, 71, 89, 107, 131, 163, 197, 239, 293, 353, 431, 521, 631, 761, 919,
        1103, 1327, 1597, 1931, 2333, 2801, 3371, 4049, 4861, 5839, 7013, 8419, 10103, 12143, 14591,
        17519, 21023, 25229, 30293, 36353, 43627, 52361, 62851, 75431, 90523, 108631, 130363, 156437,
        187751, 225307, 270371, 324449, 389357, 467237, 560689, 672827, 807403, 968897, 1162687, 1395263,
        1674319, 2009191, 2411033, 2893249, 3471899, 4166287, 4999559, 5999471, 7199369, 8639249, 10367101,
        12440537, 14928671, 17914409, 21497293, 25796759, 30956117, 37147349, 44576837, 53492207, 64190669,
        77028803, 92434613, 110921543, 133105859, 159727031, 191672443, 230006941, 276008387, 331210079,
        397452101, 476942527, 572331049, 686797261, 824156741, 988988137, 1186785773, 1424142949, 1708971541,
        2050765853, MaxPrimeArrayLength };
            
    public static int GetPrime(int min)
    { 
        if (min < 0)
            throw new ArgumentException("");
        Contract.EndContractBlock();
    
        for (int i = 0; i < primes.Length; i++)
        { 
            int prime = primes[i];
            if (prime >= min) return prime;
        }
    
        return min;
    }

这里维护了个质数数组，注意，里面并不是完整的质数序列，而是有一些过滤掉了，因为有些挨着太紧，比方说2和3，增加一个就要扩容很没必要。

`GetPrime`看`if (prime >= min) return prime;`这行代码知道是要获取第一个比传进来的值大的质数，比方传的是1，那3就是获取到的初始容量。

接着看初始化部分的代码：`size`现在知道是3，接下来以这个`size`来初始化`buckets`和`entries`，并且`buckets`里的元素都设为-1，`freeList`同样初始化成-1，这个后面有用。

初始化完后再调用这行代码 ： `this.comparer = comparer ?? EqualityComparer<TKey>.Default;` 也是初始化`comparer`，看`EqualityComparer<TKey>.Default`这个到底用的是什么：

public static EqualityComparer<T> Default
    { 
        get
        { 
            if (_default == null)
            { 
                object comparer;
                        
                if (typeof(T) == typeof(SByte))
                    comparer = new EqualityComparerForSByte();
                else if (typeof(T) == typeof(Byte))
                    comparer = new EqualityComparerForByte();
                else if (typeof(T) == typeof(Int16))
                    comparer = new EqualityComparerForInt16();
                else if (typeof(T) == typeof(UInt16))
                    comparer = new EqualityComparerForUInt16();
                else if (typeof(T) == typeof(Int32))
                    comparer = new EqualityComparerForInt32();
                else if (typeof(T) == typeof(UInt32))
                    comparer = new EqualityComparerForUInt32();
                else if (typeof(T) == typeof(Int64))
                    comparer = new EqualityComparerForInt64();
                else if (typeof(T) == typeof(UInt64))
                    comparer = new EqualityComparerForUInt64();
                else if (typeof(T) == typeof(IntPtr))
                    comparer = new EqualityComparerForIntPtr();
                else if (typeof(T) == typeof(UIntPtr))
                    comparer = new EqualityComparerForUIntPtr();
                else if (typeof(T) == typeof(Single))
                    comparer = new EqualityComparerForSingle();
                else if (typeof(T) == typeof(Double))
                    comparer = new EqualityComparerForDouble();
                else if (typeof(T) == typeof(Decimal))
                    comparer = new EqualityComparerForDecimal();
                else if (typeof(T) == typeof(String))
                    comparer = new EqualityComparerForString();
                else
                    comparer = new LastResortEqualityComparer<T>();
    
                _default = (EqualityComparer<T>)comparer;
            }
    
            return _default;
        }
    }

为不同类型创建一个`comparer`，看下面代码是我们用到的`string`的`comparer`：`hashcode`直接取的`string`的`hashcode`，其实这里面的所有类型取`hashcode`都是一样，`equals`则有个别不同。

internal sealed class EqualityComparerForString : EqualityComparer<String>
    { 
        public override bool Equals(String x, String y)
        { 
            return x == y;
        }
    
        public override int GetHashCode(String x)
        { 
            if (x == null)
                return 0;
            return x.GetHashCode();
        }
    }

基本构造函数就这些，还有个构造函数可以传一个`IDictionary<TKey, TValue>`进来，和`List<T>`一样，也是初始化就加入这些集合，首先判断是否是`Dictionary`，是的话直接遍历它的`entries`，加到当前的`entries`里，如果不是则用枚举器遍历。

为什么不直接用枚举器呢，因为枚举器也是要消耗一些资源的，而且没有直接遍历数组来得快。

这个构造函数添加时用到了`Add`方法，和例子里`Add`一样，正好是接下来要讲的。

## `Add("a", "A")` ##

下图就是初始变量的状态：  
![在这里插入图片描述][2018112916245965.png]

`Add`方法直接调用`Insert`方法，第三个参数为`true`

public void Add(TKey key, TValue value)
    { 
        Insert(key, value, true);
    }

再看`Insert`方法，这个方法是核心方法，有点长，跟着注释一点一点看。

private void Insert(TKey key, TValue value, bool add)
    { 
        if (key == null)
        { 
            throw new ArgumentNullException(nameof(key));
        }
        //首先如果buckets为空则初始化，第一次调用会走到这里，以0为capacity初始化，根据上面的分析，获得的初始容量是3，也就是说3是Dictionary<Tkey, TValue>的默认容量。
        if (buckets == null) Initialize(0); 
    
        //取hashcode后还与0x7FFFFFFF做了个与操作，0x7FFFFFFF这就是int32.MaxValue的16进制，换成二进制是01111111111111111111111111111111，第1位是符号位，也就是说comparer.GetHashCode(key) 为正数的情况下与0x7FFFFFFF做 & 操作结果还是它本身，如果取到的hashcode是负数，负数的二进制是取反再补码，所以结果得到的是0x7FFFFFFF-(-hashcode)+1，结果是正数。其实简单来说，它的目的就是高性能的取正数。
        int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
    
        //用得到的新hashcode与buckets的大小取余，得到一个目标bucket索引
        int targetBucket = hashCode % buckets.Length;
    
        //做个遍历，初始值为buckets[targetBucket]，现在"a"的hashcode为3，这样targetBucket现在是0，buckets[0]是-1，i是要>=0的，循环走不下去，跳出
        for (int i = buckets[targetBucket]; i >= 0; i = entries[i].next)
        { 
            if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key))
            { 
                if (add)
                { 
                    throw new ArgumentException(SR.Format(SR.Argument_AddingDuplicate, key));
                }
                entries[i].value = value;
                version++;
                return;
            }
        }
    
        int index;
        //freeCount也是-1，走到else里面
        if (freeCount > 0)
        { 
            index = freeList;
            freeList = entries[index].next;
            freeCount--;
        }
        else
        { 
            //count是元素的个数0， entries经过初始化后目前length是3，所以不用resize
            if (count == entries.Length)
            { 
                Resize();
                targetBucket = hashCode % buckets.Length;
            }
            //index = count说明index指向entries数组里当前要写值的索引，目前是0
            index = count;
    
            //元素个数增加一个
            count++;
        }
    
        //把key的hashcode存到entries[0]里的hashcode，免得要用时重复计算hashcode
        entries[index].hashCode = hashCode;
        //entries[0]的next指向buckets[0]也就是-1
        entries[index].next = buckets[targetBucket];
        //设置key和value
        entries[index].key = key;
        entries[index].value = value;
        //再让buckets[0] = 0
        buckets[targetBucket] = index;
        //这个不多说，不知道的可以看List<T>篇
        version++;
    }

看到这里可以先猜一下用`bucket`的目的，`dictionary`是为了根据`key`快速得到`value`，用`key`的`hashcode`来对长度取余，取到的余是0到(`length-1`)之前一个数，最好的情况全部分散开，每个`key`正好对应一个`bucket`，也就是`entries`里每一项都对应一个`bucket`，就可以形成下图取`value`的过程：  
![在这里插入图片描述][20181129163126239.png]  
这个取值过程非常快，因为没有任何遍历。但实际情况是`hashcode`取的余不会正好都不同，总有可能会有一些重复的，那这些重复的是怎么处理的呢，还是先继续看`Insert`的代码：

变量状态如下图：  
![在这里插入图片描述][20181129163142974.png]  
从这图可以看出来是由`hashcode`得到`bucket`的`index`(紫色线)，而`bucket`的`value`是指向`entry`的`index`(黄色线), `entry`的`next`又指向`bucket`上一次的`value`(红色线)，是不是有链表的感觉。

## `Add("b", "B")` ##

由于"b"的`hashcode`为4，取余得1，并没有和现有的重复，所以流程和上面一样（左边的线不用看，属于上面流程）

## `Add("c", "C")` ##

"c"的`hashcode`是6，取余得0，得到也是在第0个`bucket`，这样就产生碰撞了，

for (int i = buckets[targetBucket]; i >= 0; i = entries[i].next)
    { 
        if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key))
        { 
            if (add)
            { 
                throw new ArgumentException(SR.Format(SR.Argument_AddingDuplicate, key));
            }
            entries[i].value = value;
            version++;
            return;
        }
    }

这里`Insert`函数里就会走进`for`循环，不过"c"不是已经有的`key`，`hashcode`匹配不到所以if就不会进了。

状态如图：  
![在这里插入图片描述][20181129163347769.png]  
从图上看到，新添加的`entry`的`index`给到第0个`bucket`的`value` (黄色线)，而`bucket`上一次的`value`(红色线)也就是上次添加的元素的`index`给到新添加`entry`的`next`，这样通过`bucket`得到最新的`entry`，而不停的通过`entry`的`next`就可以把同一个`bucket`下的`entry`都遍历到。

## `dict["d"]="D" -> Resize()` ##

再用索引器的方式加入"`d`"，

public TValue this[TKey key]
    { 
        set
        { 
            Insert(key, value, false);
        }
    }

也是`insert`，不过第三个参数是`false`，这样`insert`里碰到相同的`key`会替换掉而不是像`Add`那样抛异常，这个还是不会走到`if`里去，因为`key`不重复

if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key))
    { 
        if (add)
        { 
            throw new ArgumentException(SR.Format(SR.Argument_AddingDuplicate, key));
        }
        entries[i].value = value;
        version++;
        return;
    }

不过由于容量已经满了，现在会走到下面这段代码：

if (count == entries.Length)
    { 
        Resize();
        targetBucket = hashCode % buckets.Length;
    }

触发`Resize`，看看`Resize`代码：

private void Resize()
     { 
        Resize(HashHelpers.ExpandPrime(count), false);
     }

先通过`HashHelpers.ExpandPrime(count)`取到下个容量大小。

public static int ExpandPrime(int oldSize)
    { 
        int newSize = 2 * oldSize; //新size为两倍当前大小
        if ((uint)newSize > MaxPrimeArrayLength && MaxPrimeArrayLength > oldSize)//这里MaxPrimeArrayLength是int32.MaxValue，size当然不能超过int32的最大值
        { 
            Debug.Assert(MaxPrimeArrayLength == GetPrime(MaxPrimeArrayLength), "Invalid MaxPrimeArrayLength");
    
            return MaxPrimeArrayLength;
        }
    
        return GetPrime(newSize);//这个上面讲过，是取比新size大的第一个质数
    }

所以`resize`的容量不是2倍也不是上面那个质数数组往后找，而是比2倍大的第一个质数。那现在是3，2倍是6，下一个质数是7，扩容的目标是7。

再详细看`resize`实现：

private void Resize(int newSize, bool forceNewHashCodes)
    { 
        Contract.Assert(newSize >= entries.Length);
        int[] newBuckets = new int[newSize];
        for (int i = 0; i < newBuckets.Length; i++) newBuckets[i] = -1;  //重置buckets
    
        Entry[] newEntries = new Entry[newSize];
        Array.Copy(entries, 0, newEntries, 0, count);  //建立新entries并把旧的entries复制进去
    
        if (forceNewHashCodes) // 强制更新hashcode，dictionary不会走进去
        { 
            for (int i = 0; i < count; i++)
            { 
                if (newEntries[i].hashCode != -1)
                { 
                    newEntries[i].hashCode = (comparer.GetHashCode(newEntries[i].key) & 0x7FFFFFFF);
                }
            }
        }
    
        for (int i = 0; i < count; i++) //因为重置了buckets，所以这里遍历entries来重新建立bucket和entry的关系
        { 
            if (newEntries[i].hashCode >= 0)  //hashcode做了正数处理，不应该都是大于0的么，其实不然，remove里讲hashcode为什么会为负
            { 
                int bucket = newEntries[i].hashCode % newSize;
                newEntries[i].next = newBuckets[bucket];
                newBuckets[bucket] = i;  //还是insert里的那一套，同一个bucket index, bucket指向最新的entry的index， 而新entry的next就指向老的entry的index，循环下去
            }
        }
    
        buckets = newBuckets;
        entries = newEntries;
    }

![在这里插入图片描述][20181129163840863.png]  
因为大小变了，取余也就不一样，所以`entry`和`bucket`对应的位置也不同了，不过没影响。

`Resize`消耗不低，比`List<T>`的要大，不光要`copy`元素，还要重建`bucket`。

`Resize`后继续上面那一套，看状态图：  
![在这里插入图片描述][20181129164101368.png]  
"d"的`hashcode`为11，余数是4（现在大小是7了哈）,与"b"碰撞，所以next就指到"b"的`index`，而`bucket`则去记新添加的"d"了（典型的喜新厌旧，有没有）。

## dict\[“a”\]=“AA” ##

"a"已经添加过了，再次用索引器添加"a"就走了`if`里面

if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key))
    { 
        if (add) //如果用Add方法会抛异常
        { 
            throw new ArgumentException(SR.Format(SR.Argument_AddingDuplicate, key));
        }
        entries[i].value = value; //替换掉目标entry的值
        version++;
        return;  //这里直接return了，因为只是替换值，与bucket关系并没有改变
    }

![在这里插入图片描述][20181129164244307.png]  
这步就非常之简单，只是"A"替换成"AA"。

## `Remove("b")` ##

来看看`Remove`代码：

public bool Remove(TKey key)
    { 
        if (key == null)
        { 
            throw new ArgumentNullException(nameof(key));
        }
    
        if (buckets != null)
        { 
            int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;
            int bucket = hashCode % buckets.Length;  //先算出hashcode
            int last = -1;  //last初始为-1
            for (int i = buckets[bucket]; i >= 0; last = i, i = entries[i].next)  //last在循环时指向上一个entry的index
            { 
                if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) //先找到相同的key
                { 
                    if (last < 0)  //小于0说明是第1个，last只有初始为-1
                    { 
                        buckets[bucket] = entries[i].next; //remove第一个的话就只要把bucket的值指向要remove的entry的下一个就好了，这样链表就继续存在，只是把头去掉了。
                    }
                    else
                    { 
                        entries[last].next = entries[i].next;  //remove中间或最后的entry就让上一个的next指向下一个的index，可以想像在链表中间去掉一个，是不是得把上下两边再连起来
                    }
                    entries[i].hashCode = -1; //把hashcode置为-1，上面有说hashcode有可能为负，这里就为负数了
                    entries[i].next = freeList;  //freeList在这里用到了， 把删除的entry的next指向freeList，现在为-1
                    entries[i].key = default(TKey); //key和value都设为默认值，这里因为是string所以都是null
                    entries[i].value = default(TValue);
                    freeList = i;  //freeList就指向这空出来的entry的index
                    freeCount++;  //freeCount加一个，这里可以知道freeCount是用来记entries里空出来的个数
                    version++;
                    return true;
                }
            }
        }
        return false;
    }

这里可以看出`Dictionary`并不像`List`那样`Remove`，`Dictionary`为了性能并没有在`Remove`做重建，而是把位置空出来，这样节省大量时间。`freeList`和`bucket`类似（一样喜新厌旧），总是指向最新空出来的`entry`的`index`，而`entry`的`next`又把所有空的`entry`连起来了。这样`insert`时就可以先找到这些空填进去。  
![在这里插入图片描述][20181129164455191.png]  
这里"d"的`next`本来是指向"b"的，`Remove(b)`后把"b"的`next`给了"d"(下面那条红线)，这样继续保持链表状态。`freeList`和`freeCount`这里就知道了是用来记住删除元素的`index`和个数。

## `Add("e", "E")` ##

这里再添加一个，因为有空了，所以会优先补上空出来的。

if (freeCount > 0)  //freeCount大于0，所以进来了
    { 
        index = freeList;  //当前index指向最新空出来的
        freeList = entries[index].next;  //把freeList再指到下一个，保持链表
        freeCount--;  //用掉一个少一个
    }

![在这里插入图片描述][20181129164636278.png]  
"e"的`hashcode`为10，所以也在`index`为3的`bucket`里，`bucket value`指向刚添加的`entry`也就是1，而这个`entry`的`next`就指向`bucket`旧的那个。这样就把空出来的又补上了。

通过上面分析，对`Dictionary`添加和删除的原理已经清楚了，这样下面的也会非常容易理解。

## `var a = dict["a"]` ##

来看看索引器的`get`

public TValue this[TKey key]
    { 
        get
        { 
            int i = FindEntry(key);
            if (i >= 0) return entries[i].value;
            throw new KeyNotFoundException();
        }
    }

是通过`FindEntry`来找到`entry`进而得到`value`

private int FindEntry(TKey key)
    { 
        if (key == null)
        { 
            throw new ArgumentNullException(nameof(key));
        }
    
        if (buckets != null)
        { 
            int hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;  //取hashcode
            for (int i = buckets[hashCode % buckets.Length]; i >= 0; i = entries[i].next)  //遍历bucket链表
            { 
                if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) return i; //找到hashcode一致的，也就是同样的key，返回entry索引
            }
        }
        return -1;//没找到key，后面就抛KeyNotFoundException了
    }

## `var hasA = dict.ContainsKey("a")` ##

看看`ContainsKey`代码：

public bool ContainsKey(TKey key)
    { 
          return FindEntry(key) >= 0;
    }

和上面一样，通过`FindEntry`来找索引，索引不为`-1`就是包含。

## 其他 ##

看看`Dictionary`还有哪些值得注意的：

public int Count
    { 
       get {  return count - freeCount; }
    }

真正的`count`是`entries`里个数减去里面空着的。

public bool ContainsValue(TValue value)
    { 
        if (value == null)
        { 
            for (int i = 0; i < count; i++)
            { 
                if (entries[i].hashCode >= 0 && entries[i].value == null) return true;
            }
        }
        else
        { 
            EqualityComparer<TValue> c = EqualityComparer<TValue>.Default;
            for (int i = 0; i < count; i++)
            { 
                if (entries[i].hashCode >= 0 && c.Equals(entries[i].value, value)) return true;
            }
        }
        return false;
    }

`ContainsValue`和`ContainsKey`就不一样了，它没有`bucket`可以匹配，只能遍历`entries`，所以性能和`List`的`Contains`一样，使用时需要注意。

另外还有不少代码是为了实现`Enumerator`，毕竟`Dictionary`支持`KeyValuePair`， `Key`， `Value`三种方式遍历，其实这三种遍历都是对`Entries`数组的遍历，这里就不多做分析了。

## 总结 ##

`Dictionary`的默认初始容量为3，并在填满时自动扩容，以比当前值的2倍大的第一个质数（固定质数数组里的）作为扩容目标。

`Dictionary`也不是线程安全，多线程环境下需要我们自己加锁，和`List`一样也是通过`version`来确保遍历时集合不被修改。

`Dictionary`的遍历有三种，`KeyValuePair`，`Key`, `Value`，这三个本质都是遍历`entries`数组。

`Dictionary`取值快速的原理是因为通过`buckets`来建立了`Key`与`entry`之前的联系，通过`Key`的`hashcode`算出`bucket`的`index`，而`bucket`的`value`指向`entry`的`index`，这样快速得到`entry`的`value`，当然也有不同的`key`指向同一个`bucket`，所以`bucket`的`index`总是指向最新的`entry`，而有冲突的`entry`又通过`next`连接，这样即使有冲突也只要遍历很少的`entry`就可以取到值，`Dictionary`在元素越多时性能优势越明显。

当然`Dictionary`为取值快也是付出了一点小代价，就是通过空间换取时间，多加了`buckets`这个数组来建立`key`与`entry`的联系，另外还有`entry`结构里的`hashcode`和`next`，不过相比速度这点代价基本可以忽略了。

下面是上面例子的整个过程图：（右键在新标签页打开）  
![在这里插入图片描述][20181129165253955.png]

[https_github.com_dotnet_corefx_blob_master_src_System.Collections_src_System_Collections_Generic_Dictionary.cs]: https://github.com/dotnet/corefx/blob/master/src/System.Collections/src/System/Collections/Generic/Dictionary.cs
[20181129154729548.png]: /images/20210626/4c45481e9f0e4b838135f32d53d37c2e.png
[2018112916245965.png]: /images/20210626/aba19943ae1d4616abde7f247a9f88a0.png
[20181129163126239.png]: /images/20210626/36024ae61ba844c98bf6c084aa74a108.png
[20181129163142974.png]: /images/20210626/bea97250ddfb40a18ab87777c71ceffa.png
[20181129163347769.png]: /images/20210626/32ebae3227ca4e7a84f6bb13c8e99ae3.png
[20181129163840863.png]: /images/20210626/afa38bc086fe47de88be4014f0a9b8c0.png
[20181129164101368.png]: /images/20210626/5fced4336a7442c6a8d45842e0288538.png
[20181129164244307.png]: /images/20210626/63cec87bc56643fab613ebf302305044.png
[20181129164455191.png]: /images/20210626/5ec828e123f245318d0f455dc1dd19fd.png
[20181129164636278.png]: /images/20210626/11b04f14913c4422b490f53ab422c01b.png
[20181129165253955.png]: /images/20210626/0723e33fdaf943be9af98776179f5314.png