c - 适当的内存分配

Question

我有以下构造:

typedef struct bucket {
    char *key;
    ENTRY *data;
    struct bucket *next;
} bucket;

typedef struct {
    size_t size;
    bucket **table;
} hash_table;

但我不知道如何为此分配内存。我试过了:

hash_table* ht = malloc(sizeof(hash_table)*101);

为了创建一个包含 101 个条目的哈希表，但它不起作用!谁能帮我？我真的很感激!

Answer 1

预先分配所有 101 个(或任意数量的)存储桶没有意义，您通常会在向表中插入新数据时一次分配一个。

预分配哈希数组确实有意义，它具有固定大小，但这是一个桶指针数组，而不是桶数组, 所以有些答案是错误的。

你会有这样的东西，创建一个空的哈希表，有一个固定大小的桶数组:

hash_table * hash_table_new(size_t capacity)
{
  size_t i;

  hash_table *t = malloc(sizeof *t);
  t->size = capacity;
  t->bucket = malloc(t->size * sizeof *t->bucket);
  for(i = 0; i < t->size; i++)
    t->bucket[i] = NULL;
  return t;
}

这段代码:

• 分配一个 hash_table 结构来保存表
• 用指示的容量初始化它的大小
• 分配适当长度的桶指针数组
• 确保每个存储桶指针都是 NULL(这不能用 memset() 正确完成，因为假设“所有位为零”是 NULL 在内存中的样子是不安全的)
• 尽可能使用sizeof，但不使用类型，所以没有括号
• 不强制转换 malloc() 的返回值，因为在 C 中这绝不是一个好主意
• 不检查 malloc() 的返回值，当然你应该在实际代码中这样做

需要第二个函数来执行实际的哈希插入，然后需要分配一个新的存储桶，根据键计算哈希值，在哈希表的数组中选择适当的位置，然后将新条目插入到那里.