c++ - 为什么哈希表中的第 2 级指针不需要 malloc() 来分配内存？

Question

我目前正在学习分离链来解决散列中的冲突。下面显示了一个创建哈希表的示例。我看到 hash_tbl *new_table = malloc(sizeof(hash_tbl));为 new_table 分配一大块内存.接下来，new_table->list = malloc(sizeof(node *) * size); 似乎将 new_table 除以size存储 node **list 的第一级指针.

Q1:我不明白的是为什么我不需要 malloc() node **list; 指针的第二级标记为###？

Q2:由于代码是正确的，for (int i=0; i<size; i++){
new_table->list[i] = NULL; }初始化new_tbl->list[i]指向的链表的头指针？

附注谁能用图形说明他的解释？

typedef struct Node {
    char *str;
    struct Node *next;
} node;

typedef struct Hash_Tbl {
    int size;       
    node **list; //### 
} hash_tbl;

int main() {
  int size = 6;
  create_hash_table(size);
}
hash_tbl *create_hash_table(int size) {
  if (size < 1)   return NULL;

  hash_tbl *new_table = malloc(sizeof(hash_tbl));
  if (new_table == NULL)    return NULL;

  new_table->list = malloc(sizeof(node *) * size);
  if (new_table->list == NULL)     return NULL;

  // Initialize the elements of the hash table
  for (int i=0; i<size; i++){
    new_table->list[i] = NULL;
  }

  new_table->size = size;

  return new_table;
}

Answer 1

I can't figure out is that why do I NOT need to malloc() the 2nd level of the pointer at node **list;

由于哈希表一开始是空的，因此您还不需要分配第 2 级。 create_hash_table 的代码将所有桶设置为 NULL 以指示它们为空。

does [for loop] initialize the head pointer of the linked list pointed to be new_tbl->list[i]?

哈希表中没有一个“头指针”。 list[] 数组的每个元素都是它自己的头指针。所有这些指针都被初始化为NULL，表示它们对应的桶是空的。

最初，所有的遗愿 list 都是空的。当您开始向哈希表中添加项目时，列表就会开始填充。

下图显示了一个包含六个桶的哈希表。桶 1 和 3 有一些元素；剩下的桶是空的。桶 1 没有碰撞，而桶 3 有双向碰撞。