This answer is merely provided to reduce the frustration. In general, a person is better advised to learn how to conduct performance benchmarking properly before asking such a question.
If your "keys" exclusively consist of consecutive integers, you can use an integer array. Zero-based consecutive integers can be used as array index as-is. Non-zero-based consecutive integers may require an index value adjustment before using it with an array.
Even if the keys are not strictly consecutive, in that there are a small amount of holes (unused integer values between the minimum and maximum keys), it might still be beneficial performance-wise to use an array.
Remember that using an array makes your code fragile (more easily broken) to changes. Therefore, carefully analyze your project's current and future needs, and document the limitations inside your code comments, or somehow make them obvious to your project's users.
If there is some magic mathematical functions that map your integer keys into your lookup values, test to see whether that will be faster.
If your dictionary is constructed incrementally (adding keys one by one), consider using the
Dictionary constructor with the size preallocation option, with an estimate of the maximum size needed. This reduces the time spent in reallocating and rehashing.
As pointed out in others' comments, you can benchmark with
SortedDictionary (docs), which is typically, but not guaranteed to be a binary search tree.
If you know that the distribution of your integer keys may have unusual statistical distribution characteristics (for example, all of your keys are even-numbered, and so on), you may have to implement a workaround:
- Depending on the
Dictionary implementation, a workaround might not be necessary if it is already implemented from within.
- Otherwise, you will need to apply a "key diffusion / avalanche function" to your integer keys, and use the modified key as a hash table index inside a typical "modulo-N" hash table.
- A typical good choice (for hash tables) is the MurmurHash3 function.
A sorted int-int dictionary that is initialized up-front and never changed can be re-implemented as an array of integer pairs, and lookup can be performed with binary search.
If the int-int mapping comes from some mathematical functions that has monotonic trends, it might be possible to perform the table lookup faster than binary search.