C＃字典內部數組大小

我不知道這是否是問在這裏，但請不要殺我:)C＃字典內部數組大小

我有一個論據與有關C＃的字典朋友...... 她告訴我正確的問題如果我可以說一個元素的字典。密鑰的散列碼爲100000，那麼字典的內部數組將爲100000！

這是真的嗎？我試圖在谷歌上找到答案，但由於某種原因，我沒有找到這個問題。

來源

2012-09-28 Sergey Rotbart

Dictionary的默認構造函數「具有默認初始容量」，according to MSDN。

報告還指出：

如果你可以估計集合的大小，使用構造指定初始容量消除了執行大量的大小調整操作，同時將元素添加到字典的需要。

一種這樣的構造簡單地接受一個Int32，其初始化內部存儲如下：

元件的初始數，該詞典可以含有。

字典的「默認初始容量」實際上是類的內部實現細節，因此未在文檔或公共API中公開。

拆卸mscorlib與ilspy和檢查默認構造函數表明，它的實現方式是：

public Dictionary(int capacity, IEqualityComparer<TKey> comparer) 
{ 
    if (capacity < 0) 
    { 
     ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.capacity); 
    } 

    if (capacity > 0) 
    { 
     this.Initialize(capacity); 
    } 

    this.comparer = (comparer ?? EqualityComparer<TKey>.Default); 
}

即Initialize()完全不叫：

public Dictionary() : this(0, null) 
{ 
}

這鏈構造如下實施由默認的構造函數，直接或間接。

Initialize()是設置內部存儲的方法。

所以實際上，如果您調用默認構造函數，內部存儲大小甚至不會初始化，直到您第一次添加項目。所以它基本上是零大小。

Initialize()最終會在第一次調用.Add(), 時調用值爲零。

private void Initialize(int capacity) 
{ 
    int prime = HashHelpers.GetPrime(capacity); 
    this.buckets = new int[prime]; 
    for (int i = 0; i < this.buckets.Length; i++) 
    { 
     this.buckets[i] = -1; 
    } 
    this.entries = new Dictionary<TKey, TValue>.Entry[prime]; 
    this.freeList = -1; 
}

GetPrime(0)返回3，所以this.buckets設置爲包含三個整數的數組。

爲this.entries分配值的行看起來有點奇怪，但我看不出100000在哪裏出現。

簡答題
我覺得你的同事是錯的。

來源

2012-09-28 13:18:24 tomfanning

不，它不是。 Dictionary<,>類的來源證明。

來源

2012-09-28 13:16:30 AgentFire

請問您是否善意指點我的來源？我想知道它是如何工作:) –

[.NET Reflector]（http://www.reflector.net/）擴展將爲您提供幾乎任何框架代碼。 – AgentFire

只需使用反射器來反編譯代碼並自行驗證。

來源

2012-09-28 13:17:34

不，在例如字典將有一個項目與關鍵100000

所以關鍵不到風度影響字典的大小。

來源

2012-09-28 13:17:44

不，這是不正確的。如果我有

Dictionary<int, object[]> dict = new Dictionary<int, object[]>() 
{ 
    {10000, new object[] { 1, 2, 3, 4 }} 
};

這個字典將包含與索引10000，9999不空對象陣列插槽接着我們上面輸入的對象中的一個對象陣列。答案是否定的，你的朋友是錯的。

我希望這會有所幫助。

來源

2012-09-28 13:17:50 MoonKnight

情況並非如此，因爲字典的存儲比這更復雜。此外，散列碼的值可以定義字典的大小（我不知道甚至可以如何製作），但是絕不會以任何方式定義字典的大小。

現在，我們來分解字典的存儲。

只要一個對象被用作字典中的一個鍵，它就不會以任何影響其散列值的方式進行改變。根據字典的相等比較器，字典中的每個鍵都必須是唯一的。鍵不能是空引用（在Visual Basic中爲Nothing），但值可以是，如果值類型TValue是引用類型。

Dictionary需要一個等式實現來確定密鑰是否相等。您可以通過使用接受比較器參數的構造函數來指定IEqualityComparer通用接口的實現;如果您未指定實現，則使用默認通用相等比較器EqualityComparer.Default。如果類型TKey實現System.IEquatable通用接口，則默認的相等比較器將使用該實現。

雖然這是可能散列代碼將被使用，因爲EqualityComparer.Default被定義爲這樣：

默認屬性檢查類型T是否實現System.IEquatable通用接口並且如果是這樣的回報一個使用該實現的EqualityComparer。 否則返回使用由T.

它是提供一種通過無保證是將成爲關鍵是如何產生裝置的Object.Equals和Object.GetHashCode的重寫的EqualityComparer。所以，我希望這有助於你的論點。

底線，沒有辦法散列代碼確定字典的內部尺寸，辭典是可變的和成長，如項目添加由微軟指出：

的容量Dictionary是Dictionary可容納的元素的數量。隨着元素被添加到Dictionary中，根據重新分配內部數組的需要自動增加容量。

你的朋友在爭論之前需要做她的研究。呼！

來源

2012-09-28 13:22:52

散列碼（即GetHashCode）用於將項目放入字典使用的存儲區中。

使用的實際容量是基於字典中元素的數量。

GetHashCode用於什麼的（可能不準確的）僞代碼就像這樣。

List<List<KeyValuePair<T,J>>> buckets; // let's assume this get's allocated somewhere (the dictionary allocates this internally) 
... 
public J GetValueFromDictionary(T key) 
{ 
    int bucketIndex = key.GetHashCode() % buckets.Length; 
    return buckets[bucketIndex].Find(x => x.Key == key).Single().Value; 
}

來源

2012-09-28 13:25:20 Matthew

C＃字典內部數組大小

回答

相關問題