实现一个哈希表

Question

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

我的关键字是整数，值是长度可变的char*。

我已经看过了uthash，但这需要固定长度的char*数值。如果我把它设为大数值，那么我将使用太多内存。

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

有人有什么建议吗？非常感谢任何见解。

---

感谢大家的回答。我选择了uthash并定义了自己的自定义结构以适应我的数据。

- Eamorr

---

在低层级别上，我建议使用一个链表数组来支持您的哈希表。您的哈希函数只需要将“键”映射到数组中的有效值，然后将您的值附加到该位置存在的链表中。与其他哈希实现一样，只要您的哈希函数在数组内相对平均地分布密钥，这将高效执行。 - aroth

嗨，谢谢你的留言。但是我如何高效地找到正确的键呢？ - Eamorr

@Eamorr，找到密钥是哈希函数的责任。哈希需要是确定性的：对于相同的输入始终产生相同的结果。然后无论使用什么密钥存储值，以后检索相同的值。 - luser droog

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

- marc

---

谢谢！在 hash_insert 函数中，应该将 hash_table->number_of_elements < hash_table->max 改为 hash_table->number_of_elements >= hash_table->max 吗？ - Tim

正确。使用开放地址法时，哈希函数显然需要涉及容量，并且重新散列需要在新容量下进行。这是一种最简单的实现方式，我只能鼓励任何人阅读更复杂的技术。 - marc

Answer 2

这真的取决于您关键字段的分布情况。例如，如果它是一个唯一值，始终介于0和255之间，只需使用key％256选择桶，您就有了一个完美的哈希。

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

不知道分布情况，很难谈论高效哈希。

- paxdiablo

Answer 3

将value字段声明为void *value。

这样可以将任何类型的数据用作值，但分配和释放的责任将转移给客户端代码。

- Blagovest Buyukliev