c - 有没有办法在C中通过超过1层的多态数据结构传递函数指针

Question

我目前正在开发一个 C 语言项目，涉及编写多态数据结构。我已经创建了一个静态哈希表，它只需要一个指向数据 void *data 的空指针作为插入、查找和删除功能的输入。为了散列数据，我有一个函数指针 typedef int (*hash_t)(size_t, void*);作为创建新表时的参数。最初，我使用哈希表构建一个图表，其中使用如下哈希函数分离键和值并没有真正意义:

int
hash_data(size_t size, void *graph_node) {
    return ((graph_node_t*)node)->id % size;
}

但是现在我正在考虑重用哈希表来记录文本文件中整数的频率，其中 方法会更有意义，所以我正在尝试构建一个字典数据结构来构建通过使用 结构从哈希表中删除:

typedef struct {
    void *key;
    void *value;
} key_value_t;

我再次拥有一个函数指针 typedef int (*hash_t)(size_t, void*);作为创建新字典时的参数，理想情况下我会将函数指针传递给我的哈希表:

int
hash_key_value(size_t size, void *key_value) {
    return hash_key(size, ((pair_t*)pair)->key);
}

问题是我不确定如何拥有这样的函数，它本身调用另一个函数指针，从我的哈希表插入和查找函数中调用。

我尝试过将函数指针作为参数，例如:

int
hash_pair(size_t size, void *pair, hash_key_t hash_key) {
    return hash_key(size, ((pair_t*)pair)->key);
}

但这似乎没有帮助，因为它要求我的哈希代码有一个指向我的 hashKey 函数的指针，该函数由抽象程度较低的两层代码提供。

我考虑过在我的dictionary.c 文件中添加“填空”功能，例如:

int
hash_key(size_t size, void *key) {
    /* some code */
}

但这似乎不如允许在不修改文件的情况下使用字典那么优雅，并且与我已经使用的函数指针方法不一致。

另一种选择是让字典只允许整数键，因为也许我对这个问题采取了太多的 OOP 方法。

Answer 1

哈希函数方法很好，但需要稍作修改!

假设你有一本字典；我们将在此处添加指向哈希函数的指针:

typedef struct dictionary
{
    struct pair* m_data;
    size_t m_capacity;
    HashFunction* m_hash;
}
dictionary;

现在的问题是如何正确定义哈希函数类型。首先:为什么这样的哈希函数要知道 HashMap 的大小？它应该只返回给定对象的值。同一对象的相同值，两个对象的相同值被视为相等，否则理想情况下是不同的。就是这样。为什么哈希函数应该关心将对象的哈希值映射到某些数组边界？这就是插入/查找/删除函数的任务。所以:

typedef size_t (HashFunction)(void*);

(好吧，使用替代语法，我更喜欢typedef签名并保留变量的指针性质，就像在结构中一样......)

现在查找不会考虑一对，而是考虑键:

void* lookup(dictionary* dict, void* key)
{
    // appropriate mapping done here!
    struct pair* p = dict->m_data + dict->m_hash(key) % dict->m_capacity;
    return dict->m_equal(p.key, key) ? p.value : NULL;
}

插入(包括在填充等级太高时重新散列)和删除，然后类似。

请注意，您实际上还需要一个相等比较器才能检测不同对象的关键冲突!并且您可能需要考虑在插入时进行一些适当的冲突处理(例如由数组或链表组成的槽)。