0

我必须设计和实现一个数据结构，就像bimap, bidimapor 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. 去掉内存池的操作和管理

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

4

1 回答 1

0

碰撞解决

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

注意事项

如果您的键以某种方式导致您的数据出现大量哈希冲突，或者您的分布不平衡，因为一些键被大量使用，您可能最终不得不在此过程中对表进行碎片整理。但这只是以比使用设备更长的时间间隔重写数据。

删除内存管理。

您将不得不进行指针和边界核算，仅此而已。这不是一个新问题。文件系统一直这样做。

于 2013-05-22T07:56:30.720 回答