实现哈希表
我正在尝试在C中创建一个高效的查找表。
我有一个整数作为键,可变长度char*
作为值。
我看过uthash
,但这需要一个固定长度的char*
值。 如果我把它变成一个大数字,那么我会使用太多的内存。
struct my_struct { int key; char value[10]; UT_hash_handle hh; };
有没有人有任何指针? 任何见解都非常感激。
谢谢大家的答案。 我和uthash
去了,并定义了我自己的自定义结构来容纳我的数据。
将value
字段声明为void *value
。
这样,您可以将任何类型的数据作为值,但分配和释放它的责任将委派给客户端代码。
首先要考虑你的碰撞策略:
- 你有多个哈希函数吗?
- 或者你必须在哈希表中使用容器吗?
我们选1。
然后你必须选择一个很好的分布式哈希函数。 举个例子,我们选择
int hash_fun(int key, int try, int max) { return (key + try) % max; }
如果你需要更好的东西,也许可以看看中间平方法 。
然后,您将必须决定哈希表是什么。
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; }
这实际上取决于您的关键字段的分布。 例如,如果它是一个始终在0到255之间的唯一值,则只需使用key % 256
来选择存储桶,并且您有一个完美的哈希值。
如果它在所有可能的int
值中均匀分布,那么任何给出均匀分布的哈希值的函数都会(例如前面提到的key % 256
),尽管每个桶中有多个值。
在不知道分布的情况下,谈论有效的哈希值有点困难。