我正在实现一个数据结构；项目在范围内的双链表。我想在 O(1) 中查找一个项目是否存在。为此，我想散列键将是项目和值将是节点的节点。
在 Java 中，有内置函数来支持这种特性。
编辑： 简而言之，我想要 C 中的 hashMap 之类的东西。
我应该怎么做才能在 C 中实现它？
问问题
571 次
2 回答
0
如果您将项目存储在链接列表中，那么也将它们存储在哈希中以进行遏制测试似乎......不是最理想的。只需使用哈希表开始，如果您需要它不支持的操作（O(1) 包含测试），请停止使用链表。
于 2012-08-27T19:39:01.177 回答
0
创建一个名为“buckets”的数组，其中包含键和值，以及用于创建链表的可选指针。
当您使用键访问哈希表时，您使用自定义哈希函数处理该键，该函数将返回一个整数。然后你取结果的模数，这就是你的数组索引或“桶”的位置。然后你用存储的密钥检查未散列的密钥，如果匹配，那么你找到了正确的位置。
否则，您就发生了“冲突”，必须爬过链表并比较键，直到匹配为止。（注意一些实现使用二叉树而不是链表来解决冲突）。
查看这个快速哈希表实现：
于 2012-08-29T05:21:33.847 回答