以C＃實現稀疏數組/最快的方式將整數映射到特定的桶/範圍編號

Question

我最初的問題是我需要在C＃中實現一個非常快速，稀疏的數組。最初的想法是使用正常的Dictionary<uint, TValue>並將其包裝在我自己的類中，以僅暴露TValue類型參數。原來這很慢。

所以我的下一個想法是將所需範圍內的每個整數（UInt32.MinValue到UInt32.MaxValue）映射到某個大小的存儲桶並使用它。因此，我正在尋找一種將無符號整數X映射到存儲桶Y的好方法，例如：

將數字0-1023映射到8個不同的存儲桶，每個存儲128個數字，0-127,128-255。

但是，如果有人有更好的方式在C＃中實現一個快速稀疏數組，那麼最值得讚賞。

Answer 1

有實現取決於類似因素而稀疏數組一個101種不同的方式：

• 多少個項目將在數組中
• 如何在項目聚集在一起的
• 空間/速度貿易
• 等

大部分教科書有稀疏陣列上的部分，只是做了谷歌來了，有很多的命中。然後，您將有翻譯的代碼轉換成C＃，或者只是使用代碼別人寫的，我已經發現了兩個沒有太多的精力（我不知道該怎麼好這些）

• Use Specialty Arrays to Accelerate Your Code
• SparseArray for C#

Answer 2

我也注意到，Dictionary<K,V>在鍵是整數時很慢。我不知道爲什麼是這樣的話，但我寫了uint和ulong鍵更快的哈希表的實現：

• Efficient32bitHashTable and Efficient64bitHashTable

注意事項/缺點：

• 64位（密鑰是ulong）是通用的，但另一個（密鑰是uint）假定爲int值，因爲那是我所需要的全部;我相信你可以很容易地使這個通用。

• 目前容量永遠確定哈希表的大小（即它不增長）。