c - C 中的通用哈希表

Question

我正在尝试用 C 语言创建一个通用哈希表。我阅读了一些不同的实现，并遇到了几种不同的方法。

第一种是像这样使用宏:http://attractivechaos.awardspace.com/khash.h.html

第二种是使用带有 2 个 void 指针的结构，如下所示:

struct hashmap_entry
{
    void *key;
    void *value;
};

据我所知，这种方法并不好，因为这意味着映射中的每个条目至少需要 2 次分配:一次用于键，一次用于值，无论存储的数据类型如何。 (是吗？？？)

如果不走宏观路线，我一直无法找到保持通用性的合适方法。有没有人有任何可能对我有帮助的提示或示例？

Answer 1

C 不直接提供你需要的东西，但是你可能想做这样的事情:

假设您的哈希表是一个固定大小的双链表数组，并且项目总是在应用层分配/销毁是可以的。这些条件并非对所有情况都适用，但在许多情况下都适用。然后你将拥有这些数据结构和函数和原型(prototype)的草图:

struct HashItemCore
{
    HashItemCore  *m_prev;
    HashItemCore  *m_next;
};

struct HashTable
{
    HashItemCore  m_data[256];    // This is actually array of circled
                                  // double linked lists.
    int     (*GetHashValue)(HashItemCore *item);
    bool    (*CompareItems)(HashItemCore *item1, HashItemCore *item2);
    void    (*ReleaseItem)(HashItemCore *item);
};

void  InitHash(HashTable *table)
{
    // Ensure that user provided the callbacks.
    assert(table->GetHashValue != NULL && table->CompareItems != NULL && table->ReleaseItem != NULL);

    // Init all double linked lists. Pointers of empty list should point to themselves.
    for (int i=0; i<256; ++i)
       table->m_data.m_prev = table->m_data.m_next = table->m_data+i;
}

void  AddToHash(HashTable *table, void *item);
void *GetFromHash(HashTable *table, void *item);
....
void *ClearHash(HashTable *table);

在这些函数中你需要实现哈希表的逻辑。在工作时，他们将调用用户定义的回调来找出插槽的索引以及项目是否相同。

这个表的用户应该为他们想要使用的每一对类型定义他们自己的结构和回调函数:

struct HashItemK1V1
{
     HashItemCore m_core;
     K1 key;
     V1 value;
};

int CalcHashK1V1(void *p)
{
     HashItemK1V1 *param  = (HashItemK1V1*)p;
     // App code.
}

bool CompareK1V1(void *p1, void *p2)
{
     HashItemK1V1 *param1  = (HashItemK1V1*)p1;
     HashItemK1V1 *param2  = (HashItemK1V1*)p2;
     // App code.
}

void FreeK1V1(void *p)
{
     HashItemK1V1 *param  = (HashItemK1V1*)p;
     // App code if needed.
     free(p);
}

这种方法不会提供类型安全，因为假定每个应用程序结构都以 HashItemCore 成员开头，项目将作为空指针传递。这将是一种手工制作的多态性。这可能并不完美，但它会起作用。

我使用模板在 C++ 中实现了这种方法。但是，如果您去除所有对 C++ 的幻想，简而言之，它将与我上面描述的完全相同。我在多个项目中使用了我的 table ，它的效果非常好。