实现哈希表

我正在尝试在C中创建一个高效的查找表。

我有一个整数作为键,可变长度char*作为值。

我看过uthash ,但这需要一个固定长度的char*值。 如果我把它变成一个大数字,那么我会使用太多的内存。

 struct my_struct { int key; char value[10]; UT_hash_handle hh; }; 

有没有人有任何指针? 任何见解都非常感激。


谢谢大家的答案。 我和uthash去了,并定义了我自己的自定义结构来容纳我的数据。

value字段声明为void *value

这样,您可以将任何类型的数据作为值,但分配和释放它的责任将委派给客户端代码。

首先要考虑你的碰撞策略:

  1. 你有多个哈希函数吗?
  2. 或者你必须在哈希表中使用容器吗?

我们选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 ),尽管每个桶中有多个值。

在不知道分布的情况下,谈论有效的哈希值有点困难。