我正在尝试用 C 创建一个高效的查找表。
我有一个整数作为键,一个可变长度的 char*
作为值。
我看过 uthash
,但这需要固定长度的 char*
值。如果我把它设为一个很大的数字,那么我就使用了太多的内存。
struct my_struct {
int key;
char value[10];
UT_hash_handle hh;
};
有大佬指点一下吗?非常感谢任何见解。
谢谢大家的回答。我已经使用 uthash
并定义了我自己的自定义结构来容纳我的数据。
最佳答案
您首先必须考虑您的碰撞策略:
- 你会有多个哈希函数吗?
- 或者您是否必须在哈希表中使用容器?
我们会选择 1。
然后你必须选择一个分布良好的散列函数。例如,我们将选择
int hash_fun(int key, int try, int max) {
return (key + try) % max;
}
如果您需要更好的东西,也许可以看看 middle-squared method .
然后,您必须决定什么是哈希表。
struct hash_table {
int max;
int number_of_elements;
struct my_struct **elements;
};
然后,我们必须定义如何插入和检索。
int hash_insert(struct my_struct *data, struct hash_table *hash_table) {
int try, hash;
if(hash_table->number_of_elements >= hash_table->max) {
return 0; // FULL
}
for(try = 0; true; try++) {
hash = hash_fun(data->key, try, hash_table->max);
if(hash_table->elements[hash] == 0) { // empty cell
hash_table->elements[hash] = data;
hash_table->number_of_elements++;
return 1;
}
}
return 0;
}
struct my_struct *hash_retrieve(int key, struct hash_table *hash_table) {
int try, hash;
for(try = 0; true; try++) {
hash = hash_fun(key, try, hash_table->max);
if(hash_table->elements[hash] == 0) {
return 0; // Nothing found
}
if(hash_table->elements[hash]->key == key) {
return hash_table->elements[hash];
}
}
return 0;
}
至少是一种删除方法:
int hash_delete(int key, struct hash_table *hash_table) {
int try, hash;
for(try = 0; true; try++) {
hash = hash_fun(key, try, hash_table->max);
if(hash_table->elements[hash] == 0) {
return 0; // Nothing found
}
if(hash_table->elements[hash]->key == key) {
hash_table->number_of_elements--;
hash_table->elements[hash] = 0;
return 1; // Success
}
}
return 0;
}
关于c - 实现哈希表,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6844739/