c - 数据结构如何在堆上组织

Question

现在我必须做的项目的结构如下所示:

typedef struct bucket {
   char *key;
   void *value;
   struct bucket *next;
} Bucket;

typedef struct {
   int key_count;
   int table_size;
   void (*free_value)(void *);
   Bucket **buckets;
} Table;

有人可以向我解释一下这些结构是如何组织的吗？就像我想知道 Bucket **buckets 指向什么。这种数据格式应该是一个具有存储桶链接列表的表。

图表会有所帮助。

谢谢。

Answer 1

您的Table对象有:

(a) 两名成员持有尺寸信息:key_count和table_size

(b) 函数指针 free_value不带任何参数，也不返回任何内容。据推测，它与 Table 的其他成员一起做了一些事情。

(c) 并回答您的问题:Bucket **buckets;是一个指针数组，每个指针都指向 Bucket 的链表的。

@Charlie 在评论中添加的链接应该会教您有关哈希表的更多信息。

这个想法很简单:你想存储一堆 values在表中，但您不喜欢搜索整个表来查找条目。鉴于N值，这会花费你 O(N) (将简单的表视为单个链接列表)。

你认为你可以“散列”这个 value通过称为“散列函数”的自定义函数生成“key”并存储key-value改为配对。

这样，当您需要查找 value 时，您会找到它的哈希值(即 key )，这会将您带到 Bucket 的链接列表的。每个Bucket在此列表中包含 key-value一对。您遍历列表，直到找到您的值。

如果您的自定义哈希函数足够智能，不会将多个值哈希为相同的 key ，您可以将查找时间减少到远小于 O(N) .

将其视为传播您的values分成几个单链表，并且能够知道想要遍历 O(1) 中的哪个列表通过哈希函数计算时间。

编辑:我刚刚注意到您的 Bucket struct 有一个键和值字段。我上面解释的使用 key获取 values 的链接列表。所以，我对列表的理解不需要 key作为一名成员，因为它实际上只是一个值(value)链。

我想知道为什么你需要 Bucket当它有下一个指针时，保存一个冗余的关键成员。