实现一个HashMap

如何去从头开始在C中创建一个HashMap？将考虑什么参数，以及如何测试hashmap，它有多好？就像在你说你的哈希映射完成之前你需要运行的基准测试用例一样。实现一个HashMap

来源

2009-05-08 Thunderboltz

源代码，例如，如果你知道他们背后的基本知识，应该不会太难。

通常，您将创建一个名为“桶”的数组，其中包含键和值，并带有一个用于创建链接列表的可选指针。

当您使用密钥访问哈希表时，将使用自定义哈希函数处理该密钥，该函数将返回一个整数。然后，取出结果的模数，这就是数组索引或“桶”的位置。然后，用存储的密钥检查未加密的密钥，如果匹配，则找到正确的位置。

否则，你有一个“碰撞”，必须爬过链表和比较键，直到你匹配。（注意一些实现使用二叉树代替链表进行碰撞）。

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

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

来源

2009-05-08 05:55:41 Unknown

除了LL和树之外，您还可以为每个存储桶使用不同散列处理冲突的哈希映射。 – sudo 2016-10-06 03:57:13

最好的方法取决于预期的密钥分配和冲突的号码。如果预计碰撞相对较少，那么使用哪种方法确实是并不重要。如果大量碰撞预期为，那么要使用哪一个取决于重新哈希的成本或探测与操纵可扩展存储区数据结构。

但这里是那么的An Hashmap Implementation in C

来源

2009-05-08 05:52:48 TStamper

由于后面的帖子说我们还需要处理碰撞。此外，哈希实现有一个table_size，就像固定的一样。如果我们想动态增加散列表的大小，程序员不知道它是如何完成的。你能提出一些建议吗？ – Thunderboltz 2009-05-08 05:58:20

调整密钥空间的大小意味着更改哈希函数或至少函数的参数并重新哈希所有条目。每个不同大小的地图都需要一组不同的散列函数来维护所需的密钥分布。 – TStamper 2009-05-08 06:03:33

链接已中断 – 2017-06-21 19:26:39

还有其他的机制来处理溢出比溢出项的头脑简单的链表其中例如浪费了大量的记忆。

要使用哪种机制取决于其他因素，如果您可以选择散列函数并且可能选择多个函数（实现例如双重散列来处理冲突）;如果你期望经常添加项目或者地图一旦填充就是静态的;如果你打算删除或不删除项目; ...

实现此目的的最佳方法是首先考虑所有这些参数，然后不要自己编码，而是选择一个成熟的现有实现。 Google有一些很好的实现 - 例如http://code.google.com/p/google-sparsehash/

来源

2009-05-08 06:32:21

虽然与算法相关，但sparsehash是一个hashmap的C++实现。如果你正在寻找pure-C预卷的hashmaps，请看看别处。 – 2014-02-13 07:56:43

hashmap的主要目标是存储一个数据集，并使用一个唯一的键提供近乎恒定的时间查询。有两种常用的样式散列映射实现的：

分离链：一个与铲斗的阵列（链表）
打开寻址：与额外的空间分配的单个阵列，从而索引的碰撞可以通过将被解析进入相邻的插槽。

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

当负载因数保持在某个阈值以下（一般约为0.7）并且使用合理的散列函数时，使用开放寻址的散列表具有潜在的性能优势。这是因为它们避免了潜在的缓存未命中和许多与链表关联的小内存分配，并且在连续的预分配数组中执行所有操作。通过所有元素迭代也更便宜。捕获是使用开放寻址的hashmaps必须重新分配到更大的大小，并重新保持理想的加载因子，否则他们将面临显着的性能损失。他们的负载系数不可能超过1.0。

一些关键绩效指标，以创建一个HashMap当评估将包括：

最大负载因子
在插入时的平均碰撞数
分布：分布不均（集群）可能表明一个贫穷散列函数。
各种操作的相对时间：放入，取出，删除现有和不存在的条目。

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

https://github.com/DavidLeeds/hashmap

来源

2016-11-11 10:50:19 Dave

实现一个HashMap

回答

相关问题