如何像 C++ STL 中那样从头开始在 C 中创建 Hashmap？
将考虑哪些参数以及如何测试哈希图？例如，在您可以说您的哈希图已完成之前，您将运行的基准测试用例是什么？
问问题
144194 次
4 回答
64
好吧，如果您了解它们背后的基础知识，那应该不会太难。
通常，您会创建一个名为“buckets”的数组，其中包含键和值，以及用于创建链接列表的可选指针。
当您使用键访问哈希表时，您使用自定义哈希函数处理该键，该函数将返回一个整数。然后你取结果的模数，这就是你的数组索引或“桶”的位置。然后你用存储的密钥检查未散列的密钥，如果匹配，那么你找到了正确的位置。
否则，您就发生了“冲突”，必须爬过链表并比较键，直到匹配为止。（注意一些实现使用二叉树而不是链表来解决冲突）。
查看这个快速哈希表实现：
于 2009-05-08T05:55:41.213 回答
5
最佳方法取决于预期的密钥分布和冲突次数。如果预计碰撞相对较少，则使用哪种方法实际上并不重要。如果预计会有很多冲突，那么使用哪一个取决于重新散列或探测与操作可扩展桶数据结构的成本。
于 2009-05-08T05:52:48.410 回答
3
hashmap 的主要目标是存储数据集并使用唯一键对其进行近乎恒定的时间查找。有两种常见的 hashmap 实现方式：
- 单独的链接：一个带有一组桶（链表）的链接
- 开放式寻址：分配有额外空间的单个数组，因此可以通过将条目放在相邻的插槽中来解决索引冲突。
如果 hashmap 可能具有较差的散列函数，不希望为可能未使用的插槽预分配存储空间，或者条目可能具有可变大小，则单独链接是可取的。即使负载因子超过 1.0，这种类型的 hashmap 也可以继续相对有效地运行。显然，每个条目都需要额外的内存来存储链表指针。
当负载因子保持在某个阈值以下（通常约为 0.7）并使用相当好的散列函数时，使用开放寻址的散列图具有潜在的性能优势。这是因为它们避免了潜在的缓存未命中和与链表相关的许多小内存分配，并在一个连续的、预先分配的数组中执行所有操作。迭代所有元素也更便宜。问题是使用开放寻址的哈希图必须重新分配到更大的大小并重新哈希以保持理想的负载因子，否则它们将面临显着的性能损失。它们的负载系数不可能超过 1.0。
创建哈希图时要评估的一些关键性能指标包括：
- 最大负载系数
- 插入时的平均碰撞次数
- 冲突的分布：不均匀分布（聚类）可能表明散列函数不佳。
- 各种操作的相对时间：放置、获取、删除现有和不存在的条目。
这是我制作的一个灵活的 hashmap 实现。我使用开放寻址和线性探测来解决冲突。
于 2016-11-11T10:50:19.887 回答
1
除了简单的溢出条目链接列表之外，还有其他机制来处理溢出，例如浪费大量内存。
使用哪种机制取决于您是否可以选择散列函数并可能选择多个（例如实现双散列以处理冲突）；如果您希望经常添加项目，或者地图在填充后是静态的；您是否打算删除项目；...
实现这一点的最佳方法是首先考虑所有这些参数，然后不要自己编写代码，而是选择一个成熟的现有实现。谷歌有一些很好的实现——例如http://code.google.com/p/google-sparsehash/
于 2009-05-08T06:32:21.937 回答