实现哈希表
我试图在C中创建一个高效的查找表。
我有一个整数作为键，变量长度char*作为值。
我看过uthash，但这需要一个固定长度的char*值。如果我让这个数字很大，那我就占用了太多的内存。
struct my_struct {
int key;
char value[10];
UT_hash_handle hh;
};有人有指点吗？任何洞察力都很感激。
谢谢大家的回答。我使用了uthash，并定义了自己的自定义结构来容纳我的数据。
回答 3
Stack Overflow用户
发布于 2011-07-27 13:06:16
将value字段声明为void *value。
这样，您可以将任何类型的数据作为值，但分配和释放数据的责任将委托给客户端代码。
Stack Overflow用户
发布于 2011-07-27 13:26:37
你首先要考虑一下你的碰撞策略：
- 您会有多个散列函数吗？
- 还是必须在哈希表中使用容器？
我们挑一个。
然后，您必须选择一个分布良好的散列函数。举个例子，我们将选择
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;
}Stack Overflow用户
发布于 2011-07-27 13:06:13
这确实取决于您的密钥字段的分布情况。例如，如果它是一个包含在0到255之间的唯一值，只需使用key % 256来选择桶，您就有了一个完美的散列。
如果它分布在所有可能的int值中，那么任何给出均匀分布的哈希值的函数都可以(比如前面提到的key % 256)，尽管每个桶中有多个值。
在不知道分配的情况下，很难谈论有效的散列。
https://stackoverflow.com/questions/6844739
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号