实现哈希表

Question

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

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

我研究过 uthash，但这需要固定长度的 char* 值。如果我把这个数字设得很大，那么我就使用了太多的内存。

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

有人有任何指点吗？任何见解都非常感激。

---

谢谢大家的回答。我使用了 uthash 并定义了自己的自定义结构来容纳我的数据。

Answer 1

你首先必须考虑你的碰撞策略：

1. 你会有多个哈希函数吗？
2. 或者您必须在哈希表内使用容器吗？

我们选择 1。

然后你必须选择一个分布良好的哈希函数。对于这个例子，我们会选择

int hash_fun(int key, int try, int max) {
    return (key + try) % max;
}

如果您需要更好的东西，也许看看 middle-squared方法。

然后，您必须决定什么是哈希表。

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;
}

Answer 2

将 value 字段声明为 void *value。

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

Answer 3

这实际上取决于关键字段的分布。例如，如果它的唯一值始终在 0 到 255 之间（包含 0 和 255），则只需使用 key % 256 来选择存储桶，您就拥有了一个完美的哈希值。

如果它均匀分布在所有可能的 int 值上，则任何为您提供均匀分布的哈希值的函数都可以（例如前面提到的 key % 256），尽管有多个每个桶中的值。

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