For my project, I need to map integers so that inputting int X will output int Y where both X and Y are defined during runtime.

I've used Dictionary<int,int> in .NET but its memory use is too high and the access speed is too long for my case.

Instead, I want to make a custom class that essentially does what a Dictionary<int,int> does in that it maps an integer key to an integer value.

What is the underlying concept behind the Dictionary and how would I implement something like it?

Note: I don't need to remove elements or check if the collection contains an element. I only need to be able to define input-output pairs and access the outputs with inputs.

  • So, you want to code a Dictionary, that isn't a Dictionary, but behaves like a Dictionary, without the memory use of a Dictionary that is somehow faster than O(1)... but isn't a Dictionary. Did I get that right?
    – user40980
    Commented Jul 14, 2015 at 1:45
  • No, I want to code something that accomplishes one of the things a Dictionary accomplishes.
    – JPtheK9
    Commented Jul 14, 2015 at 2:01
  • 1
    The thing you are asking for is a Dictionary. Remove, check, and contains are just bits you get on the side that come with the underlying data structure. ContainsKey is a trivial tweak to TryGetValue. Look at the reference code and see if you can make it faster or take less memory (I assure you that if you are able to do one, you will pay a heavy price for it in the other).
    – user40980
    Commented Jul 14, 2015 at 2:09
  • 2
    Maybe you can use Binary Search Tree. It will use way less memory but it will be slower to access values (but can be faster to access sequential data). BTW which language are you using? Maybe you can use a compiled language instead of scripting language.
    – Mandrill
    Commented Jul 14, 2015 at 2:17
  • @MichaelIT I'd rather not prune through the 1148 lines of code in the Dictionary's source code. In any case, it'll be fun and edifying to make my own map.
    – JPtheK9
    Commented Jul 14, 2015 at 2:24

2 Answers 2


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.


I looked at the source code of the dictionary and noticed the use of "buckets". I'm not exactly sure how a dictionary sorts objects into buckets but it's a simple task with integers.

The main problem, I've logiced, is converting the input into an index that's small as possible yet doesn't collide with other inputs' indexes to make the array the outputs are stored in as small as possible, which is where buckets come in.

If the input is 255, the array can't be that large to store the output in the index of 255. Instead, operations are done on the number to determine where its output is stored.

Here's my implementation. It's optimized for my particular use because the largest key is 255.

public class FastMap {
    //8 buckets because the maximum key is 255
    public int[][] Buckets = new int[][8];

    public void Add (int input, int output)
        //Finding out which bucket output will be assigned in
        int bucketIndex = input % 32;
        //Finding out the index inside of the bucket the output will be assigned to
        int innerIndex = input / 32;
        //Dropping output into the necessary bucket
        int[] bucket = Buckets[bucketIndex];
        if (bucket == null) 
            bucket = new int[8];
            Buckets[bucketIndex] = bucket;
        bucket[innerIndex] = output;
    public int GetValue (int input)
        return (Buckets[input % 32][input / 32]);

I'm going to be playing with this more but already, my implementation out-performs Dictionary<int,int> in both memory use and performance.

  • 5
    The reason your question was unanswerable was because you failed to mention the 255 constraint. Commented Jul 14, 2015 at 2:57
  • 2
    Chain bucket hash collision resolution.
    – user40980
    Commented Jul 14, 2015 at 3:30
  • 2
    How the hell is a Dictionary's memory usage too high if you only have 255 int,int pairs? That is using somewhere around 2K.
    – Telastyn
    Commented Jul 14, 2015 at 11:39
  • 1
    @Telastyn I have about 2000 of those dictionaries.
    – JPtheK9
    Commented Jul 14, 2015 at 17:55
  • 1
    @JPtheK9 - oh no! 4 meg! That is breaking the bank!
    – Telastyn
    Commented Jul 14, 2015 at 19:25

Not the answer you're looking for? Browse other questions tagged or ask your own question.