C 将任何对象(类型 void *)表示为整数(计算标识符)
C representing any object (type void *) as the integer number (calculated identifier)
我需要实现 hash table(或哈希映射)来存储任何类型的键。所以我用了void *key
和size_t key_size
。我需要为这些键写 hash_function(void *key, size_t key_size) 。
哈希函数需要计算数组中的索引。所以我首先需要计算此类对象的整数表示。如果这将是字符串,我可以获得字符串中每个字符的 ascii 数字并将它们相加。但是我这可以是任何类型(任何指针),即指向字符串的指针指向结构的指针我如何计算这样的整数表示?
也许我可以将这个 void *
转换成 char *
然后循环遍历 key_size 字节?
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
}
这里通常的答案是让 insert
函数的调用者提供他们自己的散列函数,如下所示:
void insert(struct hash_table* table, void* data, int (*hash_function)(void*)) {
int hash = hash_function(data);
// insert data...
}
然后你可以为每一个要插入的类型实现一个hash函数,传给insert
函数:
void hash_string(void* data) {
char* s = (char*)s;
// hash the string...
}
// somewhere else
insert(&table, "Hello, world!", &hash_string);
我需要实现 hash table(或哈希映射)来存储任何类型的键。所以我用了void *key
和size_t key_size
。我需要为这些键写 hash_function(void *key, size_t key_size) 。
哈希函数需要计算数组中的索引。所以我首先需要计算此类对象的整数表示。如果这将是字符串,我可以获得字符串中每个字符的 ascii 数字并将它们相加。但是我这可以是任何类型(任何指针),即指向字符串的指针指向结构的指针我如何计算这样的整数表示?
也许我可以将这个 void *
转换成 char *
然后循环遍历 key_size 字节?
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
}
这里通常的答案是让 insert
函数的调用者提供他们自己的散列函数,如下所示:
void insert(struct hash_table* table, void* data, int (*hash_function)(void*)) {
int hash = hash_function(data);
// insert data...
}
然后你可以为每一个要插入的类型实现一个hash函数,传给insert
函数:
void hash_string(void* data) {
char* s = (char*)s;
// hash the string...
}
// somewhere else
insert(&table, "Hello, world!", &hash_string);