适当的内存分配

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数组,这将有一个固定的大小,但是这是一个斗指针数组,而不是水桶的数组,这样一些问题的答案是错误的.

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

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()的返回值,当然你应该在实际代码中做到这一点

执行实际的哈希插入需要第二个函数,然后需要分配一个新的桶,从密钥计算哈希值,在哈希表的数组中选择正确的位置,然后在那里插入新的条目.