The most efficient read-only dictionary data structure in memory

Question

In C #, I have some static data that can be placed in Dictionary<int, T> , where T is some reference type. A web application only needs to be initialized once, statically (it does not change).

Since I don't have to worry about inserting or removing performance, what is the best data structure to use (or should I use it myself)? I probably look at something like ~ 100,000 records, fairly evenly distributed.

I am looking for an optimal algorithm to extract this data. Dictionary<> not bad, but I would suggest that there should be something optimized for read-only data.

I suspect, but did not confirm, that the range of these keys can be 0 - 400 000. If this were so, how would the recommendations change? (I have an idea that I will post as a possible answer).

---

Perhaps I could:

• Scan the data once and take the top key
• Select an array with a maximum key of + 1.
• Make the second pass and save the data in an array.

Would it be better or worse than a HashTable / Dictionary with a reasonable load factor?

Answer 1

Dictionary is the right way. Here is a quote from MSDN :

The universal Dictionary class (Of TKey, TValue) provides a mapping between a set of keys and a set of values. Each dictionary entry consists of a value and a key associated with it. Retrieving a value using its key is very fast, close to O (1) , because the Dictionary (Of TKey, TValue) class is implemented as a hash table.

Thus, it will take a lot of time when creating a dictionary (calculating hashes and building a tree), but it will read your key data very quickly.

edit

If you have more than 50% of the keys in the range from 0 to 400 KB, it makes sense to use a simple array, where the key is the index of the element. This will give you O (1) complexity at best. For your question, only 25% of the keys will be present. So in this case I would go with Dictionary <,>, I don’t think that it has 75% extra memory to store each key-value pair compared to a simple array.

Answer 2

If this is really a dictionary, trie works quite well. Dictionary (hash table) is another option if you fine tune it. Which would be faster ... I do not know, you would need to profile it, I think. Cosmic, trie wins hands down. I don't think .NET has trie in its standard library, but there should be some implementations floating around.