-1

现在，对于我必须做的项目，我的结构看起来像这样：

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指向什么。这种数据格式应该是一个具有桶链表的表。

图表会有所帮助。

谢谢你。

4

1 回答 1

0

你的Table对象有：

(a) 两名持有尺码信息的成员：key_count和table_size

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

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

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

这个想法很简单：你想在一个表中存储一堆values，但你不喜欢搜索整个表来查找条目。给定N值，这会让你付出代价O(N)（把一个简单的表想象成一个单链表）。

您认为您可以value通过称为“散列函数”的自定义函数“散列”它以生成“ key”并存储该key-value对。

这样，当您需要查找 时value，您会找到它的散列（即key），这会将您带到 的链表Bucket。Bucket此列表中的每个都包含一key-value对。您遍历列表，直到找到您的值。

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

可以把它想象成将你分散values到几个单链表中，并且能够O(1)通过你的散列函数及时知道你想要遍历哪个列表。

编辑：我刚刚注意到你的Bucket结构有一个键和值字段。我上面解释的使用 akey来获取values. 所以，我的列表概念不需要key作为成员，因为它实际上只是一个价值链。

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

于 2013-10-28T00:15:35.733 回答