Hash table implementation in C for a simple table record

Question

I have a requirement to implement this simple table from one of the DVB S2X standards. The table is relatively small that contains no more than 28 rows. I need to use the key for the table as the second column from the structure below i.e. the kbch value.

typedef struct __attribute__((packed)) {
    float ldpcCodeId;
    unsigned int kbch;
    unsigned int kldpc;
    unsigned char tErrCorrection;
} dvbS2xRecord;

I tried to use some complex hashing algorithms on this 5 digit positive integer to create a hash that I can use an index for my array. I realized that size 28 is a much smaller value for any hashing algorithm to create a hash index without creating any collisions. I tried using key % arrSize which didn't perform as expected.

So I created a simple version of the hash table that can lookup in O(1), by creating a static mapping of the integer with the index in the array. The full version of the code is

#include <stdio.h>


typedef struct __attribute__((packed)) {
    float ldpcCodeId;
    unsigned int kbch;
    unsigned int kldpc;
    unsigned char tErrCorrection;
}dvbS2xRecord;

static const dvbS2xRecord dvbS2xRecordTable[28] = { { .22 ,  14208,  14400,   12 },
                                                    { .25 ,  16008,  16200,   12 },
                                                    { .28 ,  18528,  18720,   12 },
                                                    { .33 ,  21408,  21600,   12 },
                                                    { .4  ,  25728,  25920,   12 },
                                                    { .45 ,  28968,  29160,   12 },
                                                    { .5  ,  32208,  32400,   12 },
                                                    { .53 ,  34368,  34560,   12 },
                                                    { .55 ,  35448,  35640,   12 },
                                                    { .555,  35808,  36000,   12 },
                                                    { .57 ,  37248,  37440,   12 },
                                                    { .6  ,  38688,  38880,   12 },
                                                    { .62 ,  40128,  40320,   12 },
                                                    { .63 ,  41208,  41400,   12 },
                                                    { .64 ,  41568,  41760,   12 },
                                                    { .66 ,  43008,  43200,   12 },
                                                    { .68 ,  44448,  44640,   12 },
                                                    { .69 ,  44808,  45000,   12 },
                                                    { .71 ,  45888,  46080,   12 },
                                                    { .72 ,  46608,  46800,   12 },
                                                    { .73 ,  47328,  47520,   12 },
                                                    { .75 ,  48408,  48600,   12 },
                                                    { .77 ,  50208,  50400,   12 },
                                                    { .8  ,  51648,  51840,   12 },
                                                    { .83 ,  53840,  54000,   10 },
                                                    { .85 ,  55248,  55440,   12 },
                                                    { .88 ,  57472,  57600,   8  },
                                                    { .9  ,  58192,  58320,   8  },
                                                 };

unsigned char hashOf(unsigned int kbch);

inline unsigned char hashOf(unsigned int kbch)
{
    unsigned char idx = 0;

    switch(kbch) {
        case 14208: idx =  0 ; break; case 16008: idx =  1 ; break; case 18528: idx =  2 ; break; case 21408: idx =  3 ; break;
        case 25728: idx =  4 ; break; case 28968: idx =  5 ; break; case 32208: idx =  6 ; break; case 34368: idx =  7 ; break;
        case 35448: idx =  8 ; break; case 35808: idx =  9 ; break; case 37248: idx = 10 ; break; case 38688: idx = 11 ; break;
        case 40128: idx = 12 ; break; case 41208: idx = 13 ; break; case 41568: idx = 14 ; break; case 43008: idx = 15 ; break;
        case 44448: idx = 16 ; break; case 44808: idx = 17 ; break; case 45888: idx = 18 ; break; case 46608: idx = 19 ; break;
        case 47328: idx = 20 ; break; case 48408: idx = 21 ; break; case 50208: idx = 22 ; break; case 51648: idx = 23 ; break;
        case 53840: idx = 24 ; break; case 55248: idx = 25 ; break; case 57472: idx = 26 ; break; case 58192: idx = 27 ; break;
        default: break ;
    }
    return idx;
}

int main() 
{
    for (int i=0; i< 28; i++) {
        printf("value:%d hash:%d\n", dvbS2xRecordTable[i].kbch, hashOf( dvbS2xRecordTable[i].kbch ) );
    }
    return 0;
}

I made the function inline to make the frequent access to lookup the index a bit faster. With this logic e.g. for looking up a record information for a particular kbch value

 unsigned int kbch = 50208;
 printf( "%d %0.3f %d\n", dvbS2xRecordTable[hashOf(kbch)].kldpc, \
                          dvbS2xRecordTable[hashOf(kbch)].ldpcCodeId, \
                          dvbS2xRecordTable[hashOf(kbch)].tErrCorrection );

The code is compiled with gcc 4.8.5 on Centos 7 without any warnings or errors

 gcc -std=c11 -Wall -Wextra -pedantic-errors hashTable.c

How can I further improve this hashing and/or loopkup algorithm?

Answer 1

Use a perfect hash function

What you want is to implement a perfect hash function. This is any function that for any of the valid input values, results in a unique value into to the hash table. Despite the name, there is more than one way to make such a function. Also, it's easier to make if you allow the hash table to be bigger than the number of valid items. There are tools available that, given a set of inputs, can create a perfect hash function for you. One example is GNU gperf, unfortunately it expects the set of inputs to be strings.

Another option is to find try to find a suitable mapping yourself. For example, the smallest difference between two values of kbch is 360, and the minimum value is 14208. So a possible perfect (but not minimal) hash function is:

unsigned int hashOf(unsigned int kbcd) {
    return (kcbd - 14208) / 360;
}

The maximum output value of this function is 122, so you have to make an array of 123 elements, even though only 28 elements will have a useful entry.

28 possible values is a small number, so writing something by hand might outperform a function generated by a generic tool. If you want to know what is faster, benchmark your code.

Don't use __attribute__((packed)) unless you really need strict packing

Why is dvbS2xRecord packed? You may think this is faster because it might use fewer cache lines for dvbS2xRecordTable[], but now the CPU has to do unaligned reads from the dvbS2xRecords, which might slow things down, or result in undefined behavior on CPU architectures that do not support unaligned access.

Answer 2

Use int main(void)

C17::6.11.6:

Function declarators The use of function declarators with empty parentheses (not prototype-format parameter type declarators) is an obsolescent feature.