R – the best data structure for this in-memory lookup table

data-structuresdictionarylookup

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?

Best Solution

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.

Related Solutions

What are the lesser known but useful data structures

Tries, also known as prefix-trees or crit-bit trees, have existed for over 40 years but are still relatively unknown. A very cool use of tries is described in "TRASH - A dynamic LC-trie and hash data structure", which combines a trie with a hash function.

Python – A data-structure for 1:1 mappings in python

The other alternative is to make a new class which unites two dictionaries, one for each kind of lookup. That would most likely be fast but would use up twice as much memory as a single dict.

Not really. Have you measured that? Since both dictionaries would use references to the same objects as keys and values, then the memory spent would be just the dictionary structure. That's a lot less than twice and is a fixed ammount regardless of your data size.

What I mean is that the actual data wouldn't be copied. So you'd spend little extra memory.

Example:

a = "some really really big text spending a lot of memory"

number_to_text = {1: a}
text_to_number = {a: 1}

Only a single copy of the "really big" string exists, so you end up spending just a little more memory. That's generally affordable.

I can't imagine a solution where you'd have the key lookup speed when looking by value, if you don't spend at least enough memory to store a reverse lookup hash table (which is exactly what's being done in your "unite two dicts" solution).

Best Solution

Related Solutions

What are the lesser known but useful data structures

Python – A data-structure for 1:1 mappings in python

Related Question