实现一个HashMap
如何去从头开始在C中创build一个HashMap？ 将考虑什么参数，以及如何testing散列表有多好？ 就像在你说你的哈希映射完成之前需要运行的基准testing用例一样。
那么如果你知道背后的基础知识，那就不要太难。
一般来说，你需要创build一个名为“buckets”的数组，它包含key和value，并有一个可选的指针来创build一个链表。
当您使用密钥访问哈希表时，您将使用自定义哈希函数处理该密钥，该函数将返回一个整数。 然后，取出结果的模数，即数组索引或“桶”的位置。 然后你用存储的密钥检查未encryption钥匙，如果匹配，那么你find了正确的地方。
否则，你有一个“碰撞”，必须爬过链表和比较键，直到你匹配。 （注意一些实现使用二叉树代替链表进行冲突）。
看看这个快速的哈希表实现：
最好的方法取决于预期的密钥分配和碰撞次数。 如果预计碰撞相对较less，则使用哪种方法确实无关紧要。 如果预计会发生很多冲突，那么使用哪一个取决于重新哈希或探测的成本与操纵可扩展桶数据结构的成本。
但是这里是C中的一个HashMap实现的源代码示例
hashmap的主要目标是存储一个数据集，并使用一个唯一的键提供近乎恒定的时间查询。 有两种常见的hashmap实现方式：
- 单独的链接：一个有一个桶（链表）
- 开放寻址：分配有额外空间的单个arrays，因此索引冲突可以通过将条目放置在相邻的插槽中来解决。
如果散列映射可能具有较差的散列函数，不希望预先为可能未使用的插槽预先分配存储空间，或者条目可能具有可变大小，则分离链接更为可取。 即使当负载因子超过1.0时，这种types的散列映射也可以继续相对有效地运行。 显然，每个条目都需要额外的内存来存储链表指针。
当负载因子保持低于一定的阈值（一般约为0.7）并且使用相当好的哈希函数时，使用开放寻址的哈希表具有潜在的性能优势。 这是因为它们避免了潜在的caching未命中以及与链表关联的许多小内存分配，并且在连续的预分配数组中执行所有操作。 通过所有元素迭代也更便宜。 捕获是使用开放寻址的hashmaps必须重新分配到一个更大的大小，并重新保持一个理想的负载因子，否则他们将面临显着的性能损失。 他们的负载系数不可能超过1.0。
创build哈希映射时要评估的一些关键性能指标包括：
- 最大负载系数
- 插入时的平均碰撞次数
- 冲突的分布：不均匀分布（聚类）可能表明散列函数较差。
- 各种操作的相对时间：放置，获取，删除现有和不存在的条目。
这是我做的一个灵活的hashmap实现。 我使用开放寻址和线性探测的冲突解决。
还有其他机制来处理溢出，比简单的溢出条目的链接列表，例如浪费大量的内存。
使用哪种机制取决于其他因素，如果你可以select哈希函数并且可能select多个哈希函数（实现例如双重哈希来处理冲突）; 如果你期望经常添加项目或者地图一旦填充就是静态的; 如果你打算删除或不删除项目; …
实现这一点的最好方法是首先考虑所有这些参数，然后不要自己编写代码，而要select一个成熟的现有实现。 Google有一些很好的实现，例如http://code.google.com/p/google-sparsehash/
