.NET 字典，速度驚人，但它是如何工作的？
好吧，我承認我沒有挖出反射器來看看這裡發生了什麼，但我希望有人能告訴我。
Microsoft 如何使添加和獲取如此之快，我可以通過將項目粘貼到數組中來快速添加，我可以通過對數組進行排序和使用二進制搜尋來快速獲取。但是，如果我每次添加項目時都進行快速排序以加快獲取數據的速度，那麼添加速度會大大減慢，如果每次嘗試獲取數據時都必須對數據進行排序，那麼添加項目的速度會大大降低。
有人知道字典的內部工作原理嗎？它比數組需要更多的記憶體，所以很明顯除了聰明的算法之外還有一些東西在幕後進行。
我正在努力理解魔法並從中學習！
在
dictionary<T,T>.Net 中是一種稱為雜湊表的資料結構：關於雜湊表和 .Net 字典：
<http://en.wikipedia.org/wiki/Hash_table>
<http://msdn.microsoft.com/en-us/library/4yh14awz.aspx>
<http://www.cs.auckland.ac.nz/~jmor159/PLDS210/hash_tables.html>
二進制搜尋：
<http://en.wikipedia.org/wiki/Binary_search>
你是對的，它使用比數組更多的記憶體來檢索數據。這是您為更快訪問而付出的代價。（在大多數情況下確實如此，當您開始考慮建構雜湊表與數組的設置時間時，有時排序數組的設置時間和訪問速度可能更快。但通常這是一個有效的假設。）
不久前，我在我母親的墳墓上發誓要詳細回答這個問題，我花了很長時間，因為我的一些細節和概念有點生疏，但是，不用多說，在這裡它去：
.NET Dictionary 如何在長度上或某種…
首先，讓我們從概念開始，就像許多其他答案已經指出的那樣，它是雜湊表
Dictionary<TKey, TValue>的通用（在 C# 語言功能的意義上）實現。雜湊表只是一個關聯數組，也就是說，當您傳遞一對（鍵，值）時，該鍵用於計算雜湊碼，該雜湊碼本身將有助於計算記憶體插槽（稱為儲存桶）的位置) 在底層儲存陣列（稱為…儲存桶）中，您剛剛傳遞的對和一些其他附加資訊將被保存在其中。這通常通過計算
%雜湊碼對數組/桶大小的模來實現：hashCode % buckets.Length.這種關聯數組的搜尋、插入和刪除的平均複雜度為 O(1)（即恆定時間）……除非在某些情況下，我們稍後會深入研究。所以一般來說，在字典中查找內容比在列表或數組中查找要快得多，因為您不必~通常~遍歷所有值。
如果你注意我到現在為止所說的話，你會注意到可能已經有問題了。如果基於我們的密鑰計算的雜湊碼與另一個完全相同怎麼辦？或者更糟糕的是一堆其他的鑰匙？這基本上意味著我們可以最終在同一個位置？我們如何管理這些衝突？很顯然，非常聰明的人早在幾十年前就已經考慮過這個特殊問題，並提出了兩種解決碰撞的主要方法：
- 單獨的連結：基本上這對儲存在與儲存桶不同的儲存中（通常稱為條目），例如，對於每個儲存桶（計算每個索引），我們可以有一個條目列表，其中儲存已儲存在同一位置的不同值“索引”（由於相同的雜湊碼），基本上在發生衝突的情況下，您必須遍歷鍵（並找到另一種方法，而不是雜湊碼來區分它們）
- 開放定址：所有內容都儲存在儲存桶中，基於我們接下來檢查的第一個儲存桶，在探測線性探測、二次探測、雙散列等值的方式上也存在不同的方案。）
任一沖突解決規則的實施有時可能會有很大差異。在 .NET 字典的情況下，資料結構依賴於衝突解決的分離連結類型，就像我們將在幾分鐘內看到的那樣。
好的，現在讓我們看看如何在 .NET 中插入東西
Dictionary<TKey, TValue>，歸結為通過以下方法的程式碼：
private void Insert(TKey key, TValue value, bool add)注意：閱讀下面的插入步驟後，您可以通過檢查我的答案底部原始碼中作為連結給出的程式碼來找出刪除和查找操作背後的基本原理。
第 1 步：給我雜湊碼
有兩種方法
TKey可以計算密鑰的雜湊碼：
一個依賴於預設
IEqualityComparer<TKey>實現比較器，如果您不傳遞任何參數，Dictionary<TKey, TValue>該參數基本上是由EqualityComparer<TKey>.Default（此處提供的實現）生成的，以防 TKey 是與所有常見的東西（如原語和字元串）不同的類型，如自定義類型，IEqualityComparer<in TKey>將利用以下實現（包括overrides）：
bool Equals(object obj)int GetHashCode()另一個，嗯，依賴於
IEqualityComparer<in TKey>你可以傳遞給Dictionary<TKey, TValue>建構子的實現。界面
IEqualityComparer<in T>如下所示：// The generic IEqualityComparer interface implements methods to if check two objects are equal // and generate Hashcode for an object. // It is use in Dictionary class. public interface IEqualityComparer<in T> { bool Equals(T x, T y); int GetHashCode(T obj); }無論哪種方式，字典最終都會使用比較器獲得第一個雜湊碼：
comparer.GetHashCode()第二步：獲取目標桶
我們
TKey通過 鍵從密鑰中獲得的雜湊碼IEqualityComparer<in T>有時可能是負數，如果我們想獲得數組的正索引，這並沒有真正的幫助……發生的情況是，為了擺脫負值，
Int32由 得到的雜湊碼與（即或）comparer.GetHashCode()“與” （在布爾邏輯的意義上：位）：Int32.MaxValue``2147483647``0x7FFFFFFFvar hashCode = comparer.GetHashCode(key) & 0x7FFFFFFF;獲取目標桶（索引）如下：
var targetBucket = hashCode % buckets.Length稍後還將看到如何
buckets調整數組的大小。( ) 是一個欄位，
buckets包含欄位中第一個相關槽的索引，定義如下：int[]``private``Dictionary<TKey, TValue>``entries``Entry[]``Entryprivate struct Entry { public int hashCode; public int next; public TKey key; public TValue value; }
key和是不言自明的欄位，關於該欄位value，它基本上表示該鏈中是否有另一個項目（即具有相同雜湊碼的多個鍵）的索引，如果該條目是鏈的最後一項，則該欄位設置為。hashcode``next``next``-1注：中的
hashCode欄位Entrystruct為負值調整後的欄位。第三步：檢查是否已經有條目
在那個階段，重要的是要注意行為會有所不同，具體取決於您是更新 (
add = false) 還是嚴格插入 (add = true) 新值。我們現在將檢查與
targetBucket從第一個條目開始的條目相關的條目，可以通過以下方式給出：var entryIndex = buckets[targetBucket]; var firstEntry = entries[entryIndex];帶有註釋的實際（簡化）原始碼：
// Iterating through all the entries related to the targetBucket for (var i = buckets[targetBucket]; i >= 0; i = entries[i].next) { // Checked if all if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) { // If update is not allowed if (add) { // Argument Exception: // "Item with Same Key has already been added" thrown =] ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_AddingDuplicate); } // We update the entry value entries[i].value = value; // Modification while iterating check field version++; return; } }注意：該
version欄位也是在其他常見的 .NET 資料結構（例如List<T>）中使用的欄位，它有助於在迭代（onMoveNext()）時進行檢測（並引發相關異常）。第 4 步：檢查數組是否需要調整大小
// The entries location in which the data will be inserted var index = 0; // The freeCount field indicates the number of holes / empty slotes available for insertions. // Those available slots are the results of prior removal operations if (freeCount > 0) { // The freeList field points to the first hole (ie. available slot) in the entries index = freeList; freeList = entries[index].next; // The hole is no longer available freeCount--; } else { // The entries array is full // Need to resize it to make it bigger if (count == entries.Length) { Resize(); targetBucket = hashCode % buckets.Length; } index = count; count++; }注意：關於
Resize()呼叫：
buckets與許多其他集合一樣，它將底層數組 (和entries)的大小加倍，以便通過在調整集合大小時提供充足的空間來避免過多的調整大小操作。- Double->>ish<< 因為大小只能是預先計算的集合中的素數，
Int32例如。3,7,11,17, …，7199369因為使用素數可以減少碰撞次數（請參閱SO 上的答案）實際上在該
Resize()方法的早期，新的大小計算如下：public static int ExpandPrime(int oldSize) { var min = 2 * oldSize; if ((uint) min > 2146435069U && 2146435069 > oldSize) { return 2146435069; } return HashHelpers.GetPrime(min); }第 5 步：添加條目
由於字典完成了孔和大小的檢查，因此它最終可以使用剛剛計算的 , 和 right 添加條目，並相應地調整目標
hashCode儲存key桶value：indexentries[index].hashCode = hashCode; // If the bucket already contained an item, it will be the next in the collision resolution chain. entries[index].next = buckets[targetBucket]; entries[index].key = key; entries[index].value = value; // The bucket will point to this entry from now on. buckets[targetBucket] = index; // Again, modification while iterating check field version++;獎金：字元串特殊處理
引用自下面列出的 CodeProject 源：
為了確保每個“獲取”和“添加”操作不會超過每個桶的 100 個項目，正在使用碰撞計數器。
如果在遍歷數組以查找或添加項目時，衝突計數器超過 100（限制是硬編碼的）並且
IEqualityComparer類型為，則正在為替代字元串散列算法生成EqualityComparer<string>.Default一個新實例。IEqualityComparer<string>如果找到這樣的提供者，字典將分配新數組並使用新的雜湊碼和相等提供者將內容複製到新數組中。
這種優化可能對您的字元串鍵未均勻分佈的情況很有用，但也可能導致大量分配和 CPU 時間浪費以生成字典中可能是很多項目的新雜湊碼。
用法
每當您使用自定義類型作為鍵時，請不要忘記實現
IEqualityComparer介面或覆蓋兩個 Object 方法（雜湊碼 + 相等），以免在插入時觸到自己的腳。您不僅可以避免一些糟糕和令人討厭的意外，還可以控制您插入的項目的分佈。通過均勻分佈的雜湊碼，您可以避免連結太多項目，從而避免浪費時間迭代相關條目。
受訪者/ers的旁注
我想強調一個事實，知道面試的這些實現細節通常沒什麼大不了的（實際實現與 .NET 的某些版本（“正常”或核心……）不同，而且可能仍會發生變化在稍後的時間點））。
如果有人問我這個問題，我會說：
您正在尋找的答案在 StackOverflow 上 :)
您正在尋找的答案也是
您正在尋找的答案不需要實現細節，這裡的官方文件足以滿足大多數案例。
除非，除非……你應該在你的日常工作中自己實現一個雜湊表斜線字典，在這種情況下，那種知識（即實現細節）可能會派上用場，甚至是強制性的。
資料來源：