Michał Ziobro Michał Ziobro - 3 months ago 12
C Question

C representing any object (type void *) as the integer number (calculated identifier)

I need to implement hash table (or hash map) that stores keys of any type. So I have used

void *key
and
size_t key_size
. I need to write hash_function(void *key, size_t key_size) for such keys.

Hash function need to calculate index in the array. So I need in the first place to calculate integer representation of such object. If this will be the string I could get ascii number for each char in the string and sum them up. But I this can be any type (any pointer) i.e. pointer to string pointer to struct how can I calculate such integer representation?

Maybe I could convert this
void *
into
char *
and then loop through key_size bytes?

static int hash_function(void *key, size_t key_size) {

unsigned int h = 0;
char *key_data = (char *) key;

for(int i=0; i < key_size; i++) {
h += key_data[i];
}

return (h * 1049) & HASHTAB_MASK; // HASHTAB_MASK = HASHTAB_SIZE - 1 used instead of modulo operation as such approach is faster
}

Answer

The usual answer here is to have the caller of the insert function to provide their own hash function, like so:

void insert(struct hash_table* table, void* data, int (*hash_function)(void*)) {
    int hash = hash_function(data);
    // insert data...
}

Then you can implement a hash function for each type you want to insert, and pass it to the insert function:

void hash_string(void* data) {
    char* s = (char*)s;
    // hash the string...
}

// somewhere else
insert(&table, "Hello, world!", &hash_string);