创建一个空哈希表
我正在尝试创建一个结构的空哈希表:
struct htab
{
size_t capacity;
size_t size;
struct pair *data;
};
数据是结构对值的链表列表 . 这些链表包含标记(虚拟值)作为第一个元素 .
struct pair
{
uint32_t hkey;
char *key;
void *value;
struct pair *next;
};
所以我把它写成容量为4,大小为0.我怎样才能将'data'数组的所有单元格初始化为0?
struct htab *htab_new()
{
struct htab *newtable =
malloc(sizeof(struct htab));
if (newtable == NULL)
{
errx(1, "Not enough memory!");
}
newtable->capacity = 4;
newtable->size = 0;
newtable->data = calloc(// ??);
return newtable;
}
另外,我怎么测试这实际上是否有效?
回答(2)
这些链接列表包含作为第一个元素的标记(虚拟值) .
newtable->data = calloc(capacity, sizeof(*newtable->data));
// but you should check the result of calloc as well, just as you did for malloc!
你会发现钥匙已经分配了一个值实际使用的插槽吗?然后,您将无法使用空指针作为键 . 如果只使用 next
指针,那么为什么要使用结构呢?你可以有一个指针数组,然后sentinel将是一个空指针:
struct pair** data;
有趣的是,有了这个,你就不需要像上面给出的那样改变对calloc的调用( sizeof(*data)
现在将是指针的大小......) .
旁注:见calloc and pointers ......
2 years ago
在评论中,OP提到他们从一个例子中学得更好 . (这不是一个答案本身,只是一个例子 . 请考虑这是一个扩展的评论,而不是答案 . )
让我们看一个简单的,现实世界的例子吧;但有些东西不能只是复制粘贴并呈现为自己的作品 .
假设我们需要一个文本或标记的哈希表,比方说
表本身是一个指针数组,并通过链接解决哈希冲突 . 请注意,我实际上只使用键,而不是键值对;这是为了避免将此示例代码复制粘贴并呈现为某人自己的工作 . 我写这篇文章是为了帮助新程序员理解,而不是让作弊者作为他们的家庭作业提交 . (我不是指OP,请注意 . 这些问题通常是通过网络搜索找到的,我会为整个小组编写这些答案,而不仅仅是提问者 . )
表初始化为特定大小:
对于哈希函数,我喜欢用于文本字符串的DJB2 Xor变体 . 它不是特别好(会有碰撞),但它非常简单快速:
请注意,我使用
size_t
作为哈希的类型 . 你可以使用你想要的任何类型,但在大多数架构中,它与指针的大小相同,即 .要向哈希表添加数据条目:
当我最初编写如上所述的代码时,我总是将其编写为测试程序,并对其进行测试 . (这在技术上属于_4921范式 . )
在这种情况下,我们可以简单地将插槽数作为命令行参数,并从标准输入读取每一行作为要添加到散列表的数据 .
因为标准C没有实现
getline()
,所以我们最好使用fgets()
,而使用固定大小的行缓冲区 . 如果我们宣布我们有一个预处理器宏
MAX_LINE_LEN
,默认为16383,但可以在编译时使用编译器选项覆盖 . (使用GCC,Intel CC和clang,您可以使用例如-DMAX_LINE_LEN=8191
将其减半 . )在
main()
中,如果参数计数不正确,或者-h
或--help
是第一个参数,我喜欢打印用法:接下来,我们可以尝试将第一个命令行参数解析为
size_t size;
. 我喜欢使用"sentinel"字符来检测参数在值之后是否有垃圾(除了空白):下一部分是从标准输入中读取每一行,并将它们添加到哈希表中 .
此时,我们有
table
个size
个插槽 . 我编写测试程序来编写纯文本输出(如果简单)或Graphviz DOT格式输出(如果结构像图形) . 在这种情况下,图形输出格式听起来更好 .而已 . 如果使用
10
作为命令行参数编译并运行上述程序,并使用feed对于它的标准输入,它将输出
喂给Graphviz
dot
会生成一个漂亮的图表:如果要查看数据字符串上方的实际哈希值,请更改为
正如我所说,DJB2 Xor哈希并不是特别好,对于上面的输入,你需要至少43个哈希表槽来避免链接 .