具有特定要求的纯C通用双向哈希表

Question

我必须设计和实现数据结构，其类似于bimap,bidimap或dualmap，即散列表，其中值可以用于提取键，当然也可以用于反方向。

通常情况下，它可以在两个独立的散列表的顶部来实现，但也有一些具体的要求：运行期间

1. 的内存分配（更好地分配所有的内存在启动时只）
2. 份额在启动时
相同的数据（如果实现为两个哈希表）
3. 上限已知
4. 键和值可以是任何数据结构（通用）的项的数目，但长度是固定的
5. 只有C，没有STL，从头
6. 支持删除操作

我至今是：

typedef struct HashTable { 
    int key_len; 
    int data_len; 
    int num_buckets; 
    HashEntry *buckets; 
} HashTable; 

typedef struct HashEntry { 
    void* key; 
    void* data; 
    HashEntry* next; //list for collision resolution 
} HashEntry; 

HashTable* createHashTable (int max_capacity, int num_buckets, int key_len, int data_len); 

所以该计划是创建两个哈希表，每个桶的数组。

在长度max_capacity/num_buckets

然后分配字节数组来共享数据，并作为存储器池的条目，每个条目桶预分配列表：

char* p = malloc((key_len+data_len) * max_capacity);

然后放函数会把键和数据放到字节数组中，两个哈希表都会相应地分配key和data指针。来自

1. 碰撞

   的主要挑战（超过水桶预期数量，这将需要额外拨款）的内存池的

2. 删除操作和管理

如何你会改进设计来应对这些挑战吗？

Answer 1

冲突解决

我不认为碰撞真的要需要额外的分配操作，如果你正确设置它。分配您将能够使用的最大RAM。用一些标志位设置您的存储桶来进行会计核算。你可以借用inode使用的方案;作为一个女儿，你有一个新的未使用的桶链接，你有很大的散列冲突。

考虑

如果不知何故你的钥匙是这样的，您的数据得到了很多的散列碰撞或者你的发行是片面的，因为几个按键习惯了很多，你最终可能有碎片整理您的一路上的桌子。但这只是重写数据的时间间隔比使用该设备的间隔长得多。

删除内存管理。

您将不得不做指针和边界会计，但这就是它。这不是一个新问题。文件系统一直这样做。