c - 具有特定要求的纯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) ;

然后 put 函数会将键和数据放入字节数组中，两个哈希表都会分配 key和data相应的指针。

主要挑战来自

1. 冲突(存储桶中的数量超出预期，需要额外分配)
2. 移除内存池的操作和管理

您将如何改进设计来应对这些挑战？

Answer 1

碰撞解决

如果您设置正确，我认为冲突实际上并不需要额外的分配操作。分配您将能够使用的最大 RAM。使用一些标志位设置您的存储桶以进行记帐。您可以借用 inode 使用的方案；作为女儿链接到一个新的未使用的存储桶中，其中存在较大的哈希冲突。

注意事项

如果您的 key 不知何故导致您的数据发生大量哈希冲突，或者您的分布不平衡，因为一些 key 被频繁使用，那么您最终可能不得不对表进行碎片整理。但这只是以比设备使用更长的间隔重写数据。

删除内存管理。

您必须进行指针和边界计算，但仅此而已。这不是一个新问题。文件系统一直在这样做。