实现哈希表

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

如果你需要更好的东西,也许可以看看中间平方法.

然后,您将必须决定哈希表是什么.

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

这实际上取决于您的关键字段的分布.例如,如果它是一个始终介于0和255之间的唯一值,那么只需使用key % 256选择存储桶即可获得完美的哈希值.

如果它同样在所有可能的分布int值,它给你一个同样分布式哈希值的任何函数会做(如前面提到的key % 256),尽管在每个桶多个值.

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

Answer 3

将该value字段声明为void *value.

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