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结构有一个键和值字段。我上面解释的内容使用key来获取values的链接列表。因此，我对列表的概念不需要key作为成员，因为它实际上只是一个价值链。

我想知道为什么当Bucket有下一个指针时，您需要来保存冗余密钥成员。