爲什麼我的字典在C＃中使用複合鍵表現不佳？

Question

我有一個方法，使用遞歸來遍歷樹和更新項目。

目前該方法需要相當長的時間來處理所有的項目，所以我開始優化的東西。其中包括使用字典而不是爲每個項目執行數據庫查詢。

字典定義爲

System.Collections.Generic.Dictionary<EffectivePermissionKey, MyData> 

鍵類型被定義爲

private struct EffectivePermissionKey 
{ 
    // http://blog.martindoms.com/2011/01/03/c-tip-override-equals-on-value-types-for-better-performance/ 
    public override bool Equals(object aObject) 
    { 
    if (aObject == null) 
     return false; 
    else 
     return aObject is EffectivePermissionKey && Equals((EffectivePermissionKey)aObject); 
    } 

    public bool Equals(EffectivePermissionKey aObject) 
    { 
    return this.ID == aObject.ID && this.OrchardUserID == aObject.OrchardUserID; 
    } 

    public override int GetHashCode() 
    { 
    // http://stackoverflow.com/a/32502294/3936440 
    return unchecked(ID.GetHashCode() * 23 * 23 + OrchardUserID.GetHashCode() * 23); 
    } 

    public int ID; 
    public int OrchardUserID; 
} 

當方法運行大約需要5000遞歸更新所有項目。

最初大約需要100秒沒有字典。

DB查詢的第一種方法是使用帶有int鍵的字典替換了22秒。

現在，將DB查詢替換爲使用上面定義的字典並且正確地使用TryGetValue()調用它需要97秒 <-WAT。

這是怎麼回事？什麼會導致這種大規模的性能下降？

編輯

起初，這似乎是一個哈希衝突的問題給我，讓我在EffectivePermissionKey.Equals()添加一個斷點來驗證這種方法的調用，但它不叫，因此沒有哈希衝突我猜。

EDIT2

現在我很困惑。我認爲Equals()只有當哈希代碼不匹配匹配時才被調用。在打印出我的密鑰和TryGetValue()中使用的密鑰的哈希代碼後，我發現這些代碼是匹配的。然後我看着Dictionary<>的源代碼，並有在FindEntry()一條線，看起來像這樣：

if (entries[i].hashCode == hashCode && comparer.Equals(entries[i].key, key)) return i; 

這意味着，在字典中的每個項目關鍵的GetHashCode()和Equals()被調用，因爲我處理所有項目在字典中，項目是數據庫查詢的結果，而這些結果無論如何都是在字典方法之前處理的。

Answer 1

沒有人見過，抱歉花時間，我的做法是完全錯誤的。讓我說明原因。

分解爲簡單的問題：每個樹節點

A -> recursion 1, DB query for permission of node A with ID = 1 
    B -> recursion 2, DB query for permission of node B with ID = 2 
    C -> recursion 3, DB query for permission of node C with ID = 3 
    D -> recursion 4, DB query for permission of node D with ID = 4 

正如你所看到的，一個DB查詢。

現在用於優化這種有缺陷的方法：

Dictionary<int, PermissionData> myMap 

... 

DB query of all permissions and insert into myMap 

... 

A -> recursion 1, myMap.TryGetValue(1, out ...) 
    B -> recursion 2, myMap.TryGetValue(2, out ...) 
    C -> recursion 3, myMap.TryGetValue(3, out ...) 
    D -> recursion 4, myMap.TryGetValue(4, out ...) 

您現在看到的是，查詢一次，但一TryGetValue()調用時每個節點上完成的。

在我的特定情況下，這實際上是慢作爲執行單查詢，因爲

• 字典包含儘可能多的按鍵作爲存在的節點，因爲每個節點都有一個DB權限項

和

• 各自TryGetValue()要求/結果在

  1. 創建密鑰實例（與ID和用戶ID）
  2. 主叫TryGetValue()
  3. 計算所述密鑰實例
  4. 主叫Equals()

這些4個步驟的哈希圍繞執行5000次執行5000次簡單實體框架查詢（SELECT * FROM table WHERE ID = ...）。我不知道爲什麼，但查詢在這裏更快，編譯器可能會優化一些東西。

無論如何，我重寫了整個事情，現在我有一個外部循環遍歷用戶ID和一個內部遞歸遍歷女巫使用簡單的int鍵（節點ID）的字典。它給我照明快速的結果。現在整個執行過程大約需要16秒，而且還需要更多的調整和線程處理，我將其降低到1秒以內。任務完成。