algorithm - Implementing a sparse array in C# / fastest way to map integer to a specific bucket/range number

Question

My initial problem is that I need to implement a very fast, sparse array in C#. Original idea was to use a normal Dictionary<uint, TValue> and wrap it in my own class to only expose the TValue type parameter. Turns out this is pretty slow.

So my next idea was to map each integer in the needed range (UInt32.MinValue to UInt32.MaxValue) to a bucket, of some size and use that. So I'm looking for a good way to map an unsigned integer X to a bucket Y, for example:

Mapping the numbers 0-1023 to 8 different buckets holding 128 numbers each, 0-127, 128-255.

But if someone has a better way of implementing a fast sparse array in C#, that would be most appreciated also.

Answer 1

I, too, noticed that Dictionary<K,V> is slow when the key is an integer. I don’t know exactly why this is the case, but I wrote a faster hash-table implementation for uint and ulong keys:

• Efficient32bitHashTable and Efficient64bitHashTable

Caveats/downsides:

• The 64-bit one (key is ulong) is generic, but the other one (key is uint) assumes int values because that’s all I needed at the time; I’m sure you can make this generic easily.

• Currently the capacity determines the size of the hashtable forever (i.e. it doesn’t grow).