What is the best data structure for this in-memory lookup table?

Question

I need to store a lookup table as an instance member in one of my classes. The table will be initialized when the object is constructed. Each "row" will have 3 "columns":

StringKey (e.g., "car")
EnumKey (e.g., LookupKeys.Car)
Value (e.g, "Ths is a car.")

I want to pick the data structure that will yield the best performance for doing lookups either by the StringKey or the EnumKey.

It's kind of awkward having 2 keys for the same dictionary value. I've never encountered this before, so I'm wondering what the norm is for this type of thing.

I could make a Key/Value/Value structure instead of Key/Key/Value, but I'm wondering what type of performance impact that would have.

Am I thinking about this all wrong?

Answer 1

Well ... "Wrong" is a harsh way of putting it. I think that because the most common dictionary is "single key to value", and a lot of effort goes into providing efficient data structures for that (maps), it's often best to just use two of those, sharing the memory for the values if at all possible.

Answer 2

You have two hashmaps.

• One from StringKey to value.

• One from EnumKey to value.

You do not have to duplicate all the Value instances, those objects can be shared between the two hashmaps.

If it's a LOT of items, you might want to use two treemaps instead of two hashmaps. But the essential principle ("Share the Values") applies to both structures. One set of Values with two maps.

Answer 3

Is it really necessary to key into the same structure with both types of key? You probably don't need to rebuild a complex data structure yourself. You could do some sort of encapsulation for the lookup table so that you really have two lookup tables if memory is not an issue. You could use this encapsulating structure to simulate being able to pull out the value from the "same" structure with either type of key.

OR

If there is some way to map between the enum value and the string key you could go that route with only having one type of lookup table.

Answer 4

LINQ's ILookup(TKey, TElement) interface may help. Assuming your Dictionary is something like:

Dictionary<carKey, carValue> cars;

You could use:

ILookUp<carValue, carKey> lookup = cars.ToLookup(x => x.Value, x => x.Key);

(...actually I think I might have slightly misread the question - but an ILookUp might still fit the bill, but the key/value set might need to be the key and the enum.)

Answer 5

If every value is guaranteed to be accessible by both types of keys, another idea would be to convert one type of key to another. For example:

public Value getValue(String key)
{
    dictionary.get(key); // normal way
}

public Value getValue(Enum enumKey)
{
    String realKey = toKey(enumKey);
    getValue(realKey); // use String key
}

You could have your Enum implement a toKey() method that returns their String key, or maybe have another dictionary that maps Enum values to the String counterparts.