2

几天前我发布了这个问题，每个人都建议我使用void*，我做到了。我认为他们中的一些人还指出了一些我需要注意的事情，但我不确定它们到底是什么。但是，我遇到了一些问题......

我不会将我所有的代码都发布在它很大的地方，相反，我会发布我认为重要的东西，希望足以让你帮助我。

我的哈希表结构是这样的：

typedef void * HashKey;
typedef void * HashValue;

typedef struct sHashItem {
    HashKey key;
    HashValue value;

    char status;
} HashItem;

typedef struct sHashTable {
    HashItem *items;

    int count;
    float load;
    int size;

    Bool (*compare)(HashKey, HashKey);
    unsigned (*hash)(void *);
} HashTable;

我的插入函数的签名是这样的：

Bool hashInsert(HashTable * const table, HashKey key, HashValue value);

在该函数内部的某个地方，当我在哈希表中找到一个空闲存储桶时，我会这样做：

table->items[index].key = key;
table->items[index].value = value;
table->items[index].status = USED;
table->load = ++table->count / (float)table->size;

所有这些都带来了一些问题：

1）正如您在上面看到的，我只是将空闲存储桶的每个键/值对设置为与键/值hashInsert函数参数传递的相同指针。这带来了一个问题，您可能已经注意到了......例如，做这样的事情：

char str[50];
scanf("%s%*c", str);
hashInsert(t1, (HashKey)str, (HashValue)5);
scanf("%s%*c", str);
hashInsert(t1, (HashKey)str, (HashValue)3);

如果输入是“KeyA”，然后是“KeyB”，则两者都将“KeyB”作为存储桶键。同样的事情适用于值而不仅仅是键，因为它们基本上是相同的类型，因为我想让我的代码完全模块化，适用于任何数据类型。

我怎么能解决这个问题？

我的第一个想法是使用strdup(str)并将其传递给hashInsert函数。那将解决问题。由于这是在主代码中处理的，因此我也可以轻松地将malloc()其用于需要作为值传递的任何其他数据类型（键可能始终是字符串或 int）。

但是这个解决方案带来了另一个问题......

2）我应该如何释放这个分配的内存？当然，它是由“主程序员”而不是“哈希表模块程序员”分配的，所以“主程序员”应该在主代码中释放它，对吧？但是，对我来说，这看起来不像模块化代码。

我的代码还有一个hashDestroy功能，可以释放所有分配的内存。但是我怎样才能使用这个功能来释放一切呢？我不能只遍历每个键/值并free()在它们上使用，因为它们中的一些可能一开始就不是malloc'd任何程序员的，我不需要释放它们。

我怎样才能知道哪些是我hashDestroy必须免费的，哪些不应该？

3）最后，我想我也可以把这个问题混在一起......在第一点，我的建议是使用strdup()或malloc“修复”那个特定问题（同时引入另一个问题），但这看起来也不是很模块化大部头书。这种内存分配应该在哈希表模块代码中完成，而不是由“主程序员”在主代码中完成。

你建议我如何解决这个问题？我的意思是，数据类型可以是任何东西，虽然使用strdup()有很大帮助，但它只适用于字符串。如果我需要为某些特定结构或只是一个 int 分配内存怎么办？

很抱歉这篇大文章，但我认为这些问题都是相关的，我需要一些帮助来弄清楚它们，因为我的 C 知识并不是那么极端。我最近才知道void*所以...

4

5 回答 5

2

哇：这将需要一些完整的答案。但是，您需要的关键之一是您正在处理的任何内容的大小 - 使用 void 指针很好，但您需要知道您正在接收其地址的对象有多大。

[...] 每个人都建议我使用 void*，我照做了。[...]

我的哈希表结构是这样的：

typedef void * HashKey;
typedef void * HashValue;

typedef struct sHashItem {
    HashKey key;
    HashValue value;
    char status;
} HashItem;

typedef struct sHashTable {
    HashItem *items;
    int count;
    float load;
    int size;

    Bool (*compare)(HashKey, HashKey);
    unsigned (*hash)(void *);
} HashTable;

您可能需要一个size_t key_sz;和一个size_t val_sz;成员HashItem。您的散列函数指针需要知道要散列的密钥有多大。

对于 HashKey 应该是什么，我有两种看法。这部分取决于您如何使用这些东西。看起来你想要：

  • 鉴于我选择的这个关键价值，
  • 存储/返回与其关联的数据。

在这种情况下，您可能还需要将哈希数存储在HashItem; 那是您的散列函数返回的值 - 显然是一个无符号整数。我不确定compare函数（函数指针）上的签名应该是什么；我怀疑它应该采用一对 HashKey-and-size 值，或者可能是一对 HashItem 指针。

我的插入函数的签名是这样的：

Bool hashInsert(HashTable * const table, HashKey key, HashValue value);

在该函数内部的某个地方，当我在哈希表中找到一个空闲存储桶时，我会这样做：

table->items[index].key = key;
table->items[index].value = value;
table->items[index].status = USED;
table->load = ++table->count / (float)table->size;

所有这些都带来了一些问题：

1) 正如您在上面看到的，我只是将空闲存储桶的每个键/值对设置为与键/值 hashInsert 函数参数传递的相同指针。这带来了一个问题，您可能已经注意到了......例如，做这样的事情：

char str[50];
scanf("%s%*c", str);
hashInsert(t1, (HashKey)str, (HashValue)5);
scanf("%s%*c", str);
hashInsert(t1, (HashKey)str, (HashValue)3);

使用的关键void *是传递地址。在 C 中应该不需要强制转换。您还需要传递事物的大小。因此：

Bool hashInsert(HashTable * const table, HashKey key, size_t key_sz,
                HashValue value, size_t val_sz);

char str[50];
scanf("%s%*c", str);
int value = 5;
hashInsert(t1, str, strlen(str)+1, &value, sizeof(value));

在内部，您将复制数据 - 不使用 'strdup()' 因为您不知道其中没有内部 NUL '\0' 字节。

如果输入是“KeyA”，然后是“KeyB”，则两者都将“KeyB”作为桶键。同样的事情适用于值而不仅仅是键，因为它们基本上是相同的类型，因为我想让我的代码完全模块化，适用于任何数据类型。

我怎么能解决这个问题？

您必须定义谁拥有什么，以及容器是否（以及如何）复制数据。在 C++ 中，容器会复制它们存储的任何内容。

我的第一个想法是使用 strdup(str) 并将其传递给 hashInsert 函数。那将解决问题。由于这是在主代码中处理的，因此我也可以轻松地将 malloc() 用于需要作为值传递的任何其他数据类型（键可能始终是字符串或 int）。

您不能使用“strdup()”，因为一般来说，值和键都不是字符串。如果它们始终是字符串，为什么要使用 'void *' 而不是 'char *'？

您可以决定复制值和键 - 只要您知道大小。

但是这个解决方案带来了另一个问题......

2）我应该如何释放这个分配的内存？当然，它是由“主程序员”而不是“哈希表模块程序员”分配的，所以“主程序员”应该在主代码中释放它，对吧？但是，对我来说，这看起来不像模块化代码。

我的代码还有一个 hashDestroy 函数，用于释放所有分配的内存。但是我怎样才能使用这个功能来释放一切呢？我不能只遍历每个键/值并对它们使用 free() ，因为它们中的一些可能一开始就没有被任何程序员 malloc ，我不需要释放它们。

如何找出我的 hashDestroy 必须释放哪些，不应该释放哪些？

你不能。您必须定义一个策略，并且只有当该策略允许您进行销毁时，您才应该这样做。如果你复制所有内容，你会很轻松。如果你什么都不复制，你会有一个不同的轻松时间（可以说更容易），但是你的消费者有一个地狱般的时间，因为他们需要一个结构来跟踪他们需要发布的内容——也许是一个散列列表......

3）最后，我想我也可以把这个问题混在一起......在第一点，我的建议是使用 strdup() 或 malloc 来“修复”那个特定问题（同时引入另一个问题）但那也不要t 对我来说看起来很模块化。这种内存分配应该在哈希表模块代码中完成，而不是由“主程序员”在主代码中完成。

是的......这基本上是我的建议。

你建议我如何解决这个问题？我的意思是，数据类型可以是任何东西，虽然使用 strdup() 有很大帮助，但它只适用于字符串。如果我需要为某些特定结构或只是一个 int 分配内存怎么办？

请注意，复制只做浅拷贝。如果您要复制的结构包含指针，那么复制代码将只复制指针而不是指向的数据。

因此，通用解决方案将需要某种复制功能。您可能必须要求用户为您提供一个“释放”功能，以释放项目中的内存。您可能需要让用户为您提供已完全分配的数据。您需要考虑谁拥有搜索函数返回的内容 - 它仍然“在”哈希表中还是已被删除。仔细看看 C++ STL 系统 - 一般而言，它做得很好，并且根据它的要求对您的需求进行建模可能是有意义的。但请记住，C++ 有构造函数和析构函数来帮助它。

于 2010-03-07T05:10:59.643 回答
2

我会 malloc 所有数据，并允许客户端item_free()在哈希表初始化时向哈希函数注册一个函数。这样，如何处理它取决于“主要程序员”。

于 2010-03-07T05:11:09.013 回答
1

处理哈希表中的冲突有两种通用解决方案：

  1. 请改用下一个空闲存储桶。
  2. 存储桶存储一个链表，因此可以将多个项目存储在同一个存储桶中。

对于其中任何一个，何时释放永远不会出现的问题，因为所有类型的数据要么由哈希表分配，要么由哈希表的客户端分配。如果您仍然好奇，那么解决这个难题的简短答案是使用智能指针。

于 2010-03-07T04:56:32.643 回答
1

嗯，从我在您的示例中看到的问题不是哈希表冲突（尽管您似乎也有这个问题），而是如何管理存储在表中的项目的内存。我认为做这种事情的标准方法是强制数据结构（哈希表）的用户完成为要放入表中的所有内容分配空间的工作。哈希表应该只需要担心指针。假设你做了一个分配然后在数据结构中复制：当项目从 hastable 中删除时，用户如何知道如何释放内存？

于 2010-03-07T04:58:38.193 回答
0

要实现哈希表，我们需要一组桶。而且由于多个元素可以散列到同一个桶，每个桶都需要一个链表。

做

HashItem *items;

执行上面的第二个要求？

从你的解释来看，不清楚。

一个很好的例子，请参见 K&R 第 6.6 节。链接，其中 name = HashKey 和 defn = HashValue。 替代文字 http://www.goldfish.org/books/The%20C%20Programming%20Language%20-%20K&R/pic64.gif

于 2010-03-07T04:57:55.323 回答