实现HashMap

Question

如何从头开始在C中创建Hashmap？考虑什么参数以及如何测试hashmap有多好？就像在您说哈希映射完成之前需要运行的基准测试用例一样.

Answer 1

好吧,如果你知道它们背后的基础知识,那就不应该太难了.

通常,您创建一个名为"buckets"的数组,其中包含键和值,以及一个用于创建链接列表的可选指针.

使用键访问哈希表时,使用自定义哈希函数处理密钥,该函数将返回整数.然后取结果的模数,即数组索引或"桶"的位置.然后使用存储的密钥检查未散列的密钥,如果匹配,则找到正确的位置.

否则,您遇到了"冲突",必须抓取链接列表并比较密钥,直到您匹配为止.(注意一些实现使用二叉树而不是链表来进行冲突).

看看这个快速哈希表的实现:

http://attractivechaos.awardspace.com/khash.h.html

Answer 2

哈希图的主要目标是存储数据集并使用唯一键对其提供接近恒定时间的查找。hashmap 的实现有两种常见的风格：

• 单独的链接：具有一系列存储桶（链表）的链接
• 开放寻址：分配有额外空间的单个数组，因此可以通过将条目放置在相邻槽中来解决索引冲突。

如果散列映射可能具有较差的散列函数，则不希望为可能未使用的槽预先分配存储，或者条目可能具有可变大小，则优选单独链接。即使负载因子超过 1.0，这种类型的哈希图也可以继续相对有效地运行。显然，每个条目都需要额外的内存来存储链表指针。

当负载因子保持低于某个阈值（通常约为 0.7）并且使用相当好的哈希函数时，使用开放寻址的哈希映射具有潜在的性能优势。这是因为它们避免了潜在的缓存未命中和与链表相关的许多小内存分配，并在连续的预分配数组中执行所有操作。迭代所有元素也更便宜。问题是使用开放寻址的哈希图必须重新分配到更大的大小并重新哈希以保持理想的负载因子，否则它们将面临严重的性能损失。他们的负载因子不可能超过1.0。

创建哈希图时要评估的一些关键性能指标包括：

• 最大负载率
• 插入时的平均冲突次数
• 冲突分布：不均匀分布（聚类）可能表明哈希函数较差。
• 各种操作的相对时间：现有和不存在条目的放置、获取、删除。

这是我制作的一个灵活的哈希图实现。我使用开放寻址和线性探测来解决冲突。

https://github.com/DavidLeeds/hashmap

Answer 3

最佳方法取决于预期的密钥分配和冲突数量.如果预计会发生相对较少的冲突,那么使用哪种方法并不重要.如果预期会发生大量冲突,那么使用哪种冲突取决于重新散列或探测与操纵可扩展桶数据结构的成本.

但这里是C中的Hashmap实现的源代码示例