如何在 C 中调整哈希表的大小？阵列拒绝改变

Question

struct table
  {
    int size;
    key_value *array[];
  };

struct table *create_table(int size)
{
    struct table *table = calloc(1, sizeof(struct table));
    table->size = size;
    return table;
}

void resize_table(struct table *table, int new_size)
{
    struct table *new_table = create_table(new_size);
    for(int i = 0; i < table->size; i++)
      {
      key_value *p = table->array[i]->next;
      while(has_next(p))
        {
        insert(new_table, p->key, p->value);
        p = p->next;
        }
      }
    *table = *new_table;
}

我试过只制作数组array[]，这也没用。当我尝试通过 new_table 获取重新散列的值时，它工作得很好。但是在分配 *table = *new_table 并通过 table 访问重新散列的值后，它不起作用。为什么 assert(new_table->array[23]->key==23) 有效，但 assert(table->array[23]->key==23) 无效？我已经把 table 设置为 new_table，他们现在不应该一样吗？奇怪的是 size 值发生了变化，但数组没有变化。

当我尝试只改变指针时：

table->array = new_table->array;

我得到 invalid use of flexible array member，我不明白，我不只是将结构中的指针更改为不同的地址，为什么即使它是一个数组也很重要？

我可以使用 alloc/realloc 解决这个问题吗？

Answer 1

这里有很多误解。

key_value *array[];就是所谓的灵活数组成员，一个特殊的功能。具体来说，它是一个 key_value 指针数组，在声明时大小未知。它是一个数组，而不是一个指针。

因此 table->array = new_table->array; 尝试将一个数组分配给另一个数组，这在 C 中是不允许的。必须使用 memcpy 或类似的方式复制数组。
当您需要直接在结构之后分配相邻内存时，灵活的数组成员最有意义。哈希 table 不是一个明显的用例，但它可以工作（并提供良好的缓存性能）。分配 flex 数组成员时需要做的是一次性为结构和数组分配空间，如下所示：
```
struct table *table = calloc(1, sizeof(struct table) + sizeof(key_value*[size]) );
```
灵活数组成员的一个特殊属性是sizeof(struct table)不考虑灵活数组。所以我们需要单独指定那个尺寸。

如果您不这样做，则 key_value 不是有效内存，无法使用。
可以假设
calloc 将所有指针设置为空，所以这很好，保留 calloc 而不是 malloc，它不会初始化任何东西。
这里不行:
```
void resize_table(struct table *table, int new_size)
{
  struct table *new_table = create_table(new_size);
```
由于
中解释的原因
您可以通过两种方式完成这项工作：
- 假设table指向先前分配的数据。在那种情况下，您不应该调用 create_table 而是修改已经分配的数据。可能realloc吧。在这种情况下，realloc 必须使用 sizeof(struct table) + sizeof(key_value*[new_size]).
  与 calloc 不同，
  realloc 不会将数据初始化为零，因此如果您使用 realloc.
  ，则必须为新项显式地执行此操作
- 或者您可以要求调用者通过 struct table** table 向您提供先前分配的数据的地址。然后你可以 free 它，然后重新调用 create_table，将结果存储在 *table 中。当然，您可能希望 memcpy 在调用 free 之前应保留的任何项目。
同样，*table = *new_table; 不会工作，因为它不会复制灵活的数组成员，也不会复制它包含的指针指向的任何数据。

但一般来说，当结构具有指向动态分配数据的指针成员时，不能硬复制结构，否则您最终会得到两个结构，其中的成员指向相同的数据。这意味着您必须使用我上面描述的两种方法中的任何一种重新分配所有数据。

请注意，以上所有只是为 key_value *array[] 中的指针本身分配空间。必须将它们设置为指向在该结构之外的其他地方分配的实际数据。

Answer 2

你最初拥有的时候

struct table
  {
    int size;
    key_value *array[24];
  };

（或其他），固定大小的 24 元素数组是您的结构的一部分，并在 sizeof(struct table) 中计算，并且 space 在 [=20= 中正确分配给它]

struct table *create_table(int size)
{
    struct table *table = calloc(1, sizeof(struct table));
    table->size = size;
    return table;
}

但是当您将其更改为灵活数组时，它没有默认大小，并且在 sizeof(struct table) 中假定没有存储空间。这应该是显而易见的，因为您已明确告诉编译器您 不知道 它应该有多大。您可以通过打印 sizeof 您的结构的两个版本轻松确认您的理解。

因此，您需要明确地告诉calloc要分配多少额外字节：

    struct table *table = calloc(1, sizeof(struct table) + size * sizeof(key_value*));

最后，作业

  *table = *new_table;

也不行，因为两个对象的大小不一定相同。您不能像这样调整第一个对象（编译器甚至不知道其数组长度）的大小，也不会从灵活数组中复制任何元素（因为编译器不知道有多少）。

现在，您已经分配了一个正确大小的对象 - 您需要 return 将其分配给调用者。通常的方法是传递一个指针到指针，这样你就可以用新地址更新调用者：

void resize_table(struct table **table_ptr, int new_size)
{
    struct table *table = *table_ptr; /* this is just to avoid rewriting the rest of the code */
    struct table *new_table = create_table(new_size);
    for(int i = 0; i < table->size; i++)
      {
      key_value *p = table->array[i]->next;
      while(has_next(p))
        {
        insert(new_table, p->key, p->value);
        p = p->next;
        }
      }
    *table_ptr = new_table;
    free(table); /* you're replacing the table, not updating it */
}

可能还有其他问题，比如您似乎总是跳过存储桶中的第一个元素，并且您可以使用realloc来减少数量冗余 calloc/free 操作。

Answer 3

由于结构内部的 array 没有指定大小，它是一个灵活的数组成员，需要动态内存分配。您的代码永远不会这样做，因此您的 array 没有记忆。您可以使用灵活的数组来实现它，但为此我会选择一个指向 key_value.

的指针

喜欢：

struct table
{
    int size;
    key_value **array;
};

struct table *create_table(int size)
{
    struct table *table = malloc(sizeof *table);
    assert(table != NULL);
    table->size = size;
    table->array = calloc(size, sizeof *table->array);
    assert(table->array != NULL);
    return table;
}

void resize_table(struct table *table, int new_size)
{
    key_value **tmp = realloc(table->array, new_size * sizeof *table->array);
    if (tmp == NULL)
    {
        // Error handling or just:
        exit(1);
    }
    table->size = new_size;
    table->array = tmp;
}

如果您更喜欢使用灵活数组成员的解决方案，它类似于：

struct table
{
    int size;
    key_value *array[];
};

struct table *create_table(int size)
{
    struct table *table = calloc(1, sizeof *table + size * sizeof table->array[0]);
    assert(table != NULL);
    table->size = size;
    return table;
}

struct table * resize_table(struct table *table, int new_size)
{
    struct table *tmp = realloc(table, sizeof *table + new_size * sizeof table->array[0]);
    if (tmp == NULL)
    {
        // Error handling or just:
        exit(1);
    }
    tmp->size = new_size;
    return tmp;
}

并使用 resize_table 如：

table = resize_table(table, new_size);

如何在 C 中调整哈希表的大小？阵列拒绝改变

How to resize a hashtable in C? Array refuses to change

c

struct

hashtable