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 回答