000: Hash Tables, or sort of

In a few words and at a risk to make some mistakes in my definition, a hash table is basically a data structure or array that allows to return a value paired with another one, usually called “key”, you’ll see let say we want to get the value of 128 but this value is paired with a key value of 2, we would like to have a function like this

uint8 Hash_Table( uint8 key )
{
    if( key == 2 )
    {
        return 128;
    }
    ...
}

pretty simple ha, but suppose our entire table is made of the following values

we could have the following code made of several if/else if sentences each of them for each value in our table

uint8 Hash_Table( uint8 key )
{
    if( key == 0 )
    {
        return 10;
    }
    else if( key == 1 )
    {
        return 42;
    }
    ...
}

Now you can notice one thing the key values in our previous has table start from 0 and ends in number 6, all of them after the other, meaning the key values are the same as the index in the table, of course this can be implemented as an array. the following code illustrate the idea

uint8 Hash_Table( uint8 key )
{
    uint8 table[] = { 10, 42, 36, 7, 11, 100, 200 };
    
    return table[ key ];
}

Are this kind of tables limited to numbers?, not at all, any kind of data can be store and returned it will depends of the type of the array, but to expand even more we can use pointers to any kind of data

As you can see we have values made of strings, in c does not exist the concept of string, so in reality we have pointer to arrays, and that is precisely what we have an array on pointer, but we could use array of pointer to structures, pointer to other arrays, pointer to functions, and a long etc..

char *Hash_Table( uint8 key )
{
    static char *table[] = { "cero", "uno", "dos", "tres", "cuatro", "cinco", "seis" };
    
    return table[ key ];
}

We do not need a function the same array is the hash table, but this is only valid when we have consecutive key values. what happens when our key values are not consecutive?, well the thing become pretty interesting, again lets use the strings as examples and the key values will be represent as IDs

We need to define a structure with two elements a key value a pointer to string, with this new type defined we can declare an array with our string of names

typedef struct _FruitTytpe
{
    uint8 key;
    uint8 *value;
} FruitType;

FruitType FruitTable[SIZE] = 
{
    {
        .key = 23;
        .value = "apple";
    },
    {
        .key = 11;
        .value = "orange";
    },
    ...
} 

Things are not going to be stray forward like having an array like in the previous examples, our key values are not contiguous values but they still contiguous inside an array

 uint8 *Hash_Table( FruitType *table, uint8 key )
 {
    for( uin8 i = 0 ; i < SIZE ; i++ )
    {
        if( table[i]->key == key )
        {
            return table[i]->value
        }
    }
 }

Do we need Key values as integers all the time?, not really, as same as the value the key can be any kind of data you need, remember you can always relay in pointers to do the dirty job

 uint8 Hash_Table( FruitType *table, char *key )
 {
    for( uin8 i = 0 ; i < SIZE ; i++ )
    {
        if( strcmp( table[i]->key, key ) == 0 )
        {
            return table[i]->value
        }
    }
 }

Ok, in reality a hash table is quiet more complex than what we explain because its define a hash value extracted using an algorithm and the hash table has the capacity to be dynamic, meaning we can insert and subtract elements in run time, but this is not desirable in embedded software because we will need to allocate dynamic memory and that is forbidden in microcontroller software