How exactly do lookup tables work and how to implement them?

Question

I made a program recently that dealt with a lot of if/else statements to return particular values. Someone recommended using lookup tables instead. My question is,

1. How do they work and how do you implement them?
2. What is the difference between a map, hash table, and lookup table.

Solution 1

My question is, how do they work and how do you implement it? What is the difference between stl map, hash tables, and lookup tables.

What you're looking for is an efficient mechanism by which you can look up the value that corresponds to a given key.

Your current mechanism (a long list of if/else-if commands) is rather inefficient, in that if you have N possible values to choose from, you will (on average) have to compare your candidate key against (N/2) other keys before you find the one that matches and you can stop looking. (This is known as O(N) complexity)

So what are the other choices?

The simplest one is literally just an array of values, e.g.

const char myLookupTable[1000] = {
    "zero",
    "one",
    "two",
    [...]
    "nine hundred and ninety-nine"
};

... with a lookup table like that, you take a key (which in this case is a number between 0 and 999, inclusive), and look up the corresponding value with a single array-lookup:

 const char * val = myLookupTable[500];

That's super-efficient (O(1) complexity -- it always finishes in constant time, regardless of how big the array is!), but it only works in cases where your keys are unsigned integers in a continuous (and relatively small) range of values. For example, if your keys were strings, this approach wouldn't apply.

For more flexibility, the next option would be STL's std::map. std::map gives you fast key->value lookups from any key-type to any value-type. Internally it is implemented as a tree: each key-value pair is inserted into the tree in such a way that the tree remains sorted with the smallest keys at the left of the tree and the largest keys at the right. Because of that, looking up a key (and its associated value) in a std::map is just a matter of starting at the tree's root node and comparing the key at that node to the key you are looking up: is it less than your key? Then move to the right-hand child. Or it greater than your key? Then move to the left-hand child. Repeat that until you get to the bottom of the tree, at which point you'll either find the key-value pair you were looking for or you'll find that it's not present. This is an algorithm of O(log(N)) complexity, because for a tree with N values in it, it takes log(N) comparisons for the lookup to complete. O(log(N)) is considered pretty good efficiency.

The final data structure you mentioned is a hash table (as seen in std::unordered_map). A hash table does things a bit differently -- internally it is an array, but in order to avoid the limitations of the lookup-table approach, it also comes with an algorithm for figuring out where in its array a given key/value pair is to be stored. It does this by calculating a hash code for the key-object you pass in -- and then using that code to compute an offset into the array (e.g. int array_offset = hash_code % array_size) and looking at that slot in the array to see if the requested key-value pair is there. If it is, then it's done (O(1) performance again!); or if the slot is empty, then it knows that your key isn't in the table and can return failure immediately (O(1) again). If the slot is occupied by some other key/value pair, then the hashtable will need to fall back to another algorithm to sort out the hash collision; different hash tables handle that different ways but it's generally still fairly efficient.

Solution 2

Your question is really to broad since StackOverflow is not a tutorial site, but I feel kind this morning...

A "lookup table" is simply a container (any kind of container) that contains values you look up, and usually map to some other value.

In its simplest form, consider the following:

struct MapIntToString
{
    int value;
    char* string;
};

MapIntToString my_map[] = {
    { 1, "one" },
    { 2, "two" },
    { 3, "three" },
    // ...
};

The above could be considered a lookup table. You can iterate (loop) over my_map to find (look up) the integer 2 and then pick the string "two" from it.

Depending on your need and use-case the above example might not be enough. The code above is basically how it is commonly done in plain C, not C++. For C++ there are better containers for mapping values, like std::map and std::unordered_map.

However sometimes the standard types might not be enough, and there are many other data-structures that could be implemented for looking up things.