Integer Map Algorithm

Question

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.

Answer 1

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.

Answer 2

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.