以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值，因为那是我所需要的全部;我相信你可以很容易地使这个通用。

• 目前容量永远确定哈希表的大小（即它不增长）。