1

我有以下结构：

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 个条目创建一个哈希表，但它不起作用！谁能帮我？我真的很感激！

4

4 回答 4

9

预先分配所有 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() 的返回值，当然你应该在实际代码中这样做

需要第二个函数来执行实际的哈希插入，然后需要分配一个新的存储桶，根据键计算哈希值，在哈希表的数组中选择正确的位置，然后在其中插入新条目。

于 2008-12-16T08:57:39.807 回答
0

hash_table总是只有sizeof(hash_table)字节大。table元素是指向元素指针数组的指针bucket。所以你需要这样的东西：

hash_table* ht = malloc(sizeof(hash_table));
ht->size = 101;
ht->table = malloc(sizeof(bucket*)*ht->size);

但我怀疑可能有一些初始化方法，然后你可以做这样的事情：

hash_table* ht = alloc_hash_table(101);

无论如何，我对 C 语言有点生疏，所以对此持保留态度。

于 2008-12-16T08:47:28.377 回答
0

不完全的。假设这是 C，您可能想要创建一个函数：

 hash_table* init_table(size_t size) {
     size_t i;
     hash_table* ht = (hash_table*)malloc(sizeof(hash_table));
     if (ht == NULL) return NULL;
     ht->size = size;
     ht->table = (bucket**)malloc(sizeof(bucket*)*size);
     if (ht->table == NULL) {
         free(ht);
         return NULL;
     }
     for (i = 0; i < size; ++i) {
         ht->table[i] = NULL;
     }
     return ht;
 }

您可能需要该结构中的其他一些字段。

如果您想变得棘手，并且从不重新分配存储桶，您可以这样做：

 hash_table* init_table(size_t size) {
     hash_table* ht = (hash_table*)malloc(sizeof(hash_table)+sizeof(bucket)*size);
     if (ht == NULL) return NULL;
     ht->size = size;
     ht->table = (bucket**)(ht+1);
     for (i = 0; i < size; ++i) {
         ht->table[i] = NULL;
     }
     return ht;
 }

编辑：我将我的 bucket* 表固定到 bucket**

EDIT2：我已经摆脱了 memset 并为 malloc 添加了错误检查。

于 2008-12-16T08:48:56.890 回答
0

您的 typedef 有一些问题。假设您使用 MSVC。

声明您在此处拥有的类型的一种简单方法是：

此 typedef 包括 _type {} 类型，*ptype；同时声明类型和指向自定义类型的指针的格式。如果您在 hash_table 中看到向下，则可以使用 pbucket *table，它消除了代码中额外的 ***，并且可以在进行动态分配时提供帮助（帮助您保持头脑清醒，了解分配的内容等。 ）。您的原始 typedef，如果您看起来有 typedef struct bucket {} bucket;，您至少需要修改您在指定 typedef 时拥有的两个“桶”名称之一。

如果您使用 C++ 构建设置，您还需要进行转换，如果使用普通 C，您可能不需要转换，所以您的 malloc 行将是（我做了以下 typedef 更改）；

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

无论哪种方式，这个片段都应该适合你；

typedef struct _bucket {    
    char *key;    
    void *data;    
    _bucket *next;
} bucket, *pbucket;

typedef struct _hash_table {    
    size_t size;    
    pbucket *table;
}hash_table, *phash_table;
于 2009-02-21T03:30:32.180 回答