用C实现HashMap [英] Implementing a HashMap in C

问题描述

如何像在C ++ STL中一样从头开始在C中创建Hashmap？

How to go about creating a Hashmap in C from scratch as is present in C++ STL?

需要考虑哪些参数以及如何测试哈希图？像这样，在您可以说哈希映射完成之前将要运行什么基准测试用例？

What parameters would be taken into consideration and how would you test the hashmap? As in, what would the benchmark test cases be which you would run before you could say that your hashmap is complete?

推荐答案

好如果您了解其背后的基础知识，那应该不会太难。

Well if you know the basics behind them, it shouldn't be too hard.

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

Generally you create an array called "buckets" that contain the key and value, with an optional pointer to create a linked list.

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

When you access the hash table with a key, you process the key with a custom hash function which will return an integer. You then take the modulus of the result and that is the location of your array index or "bucket". Then you check the unhashed key with the stored key, and if it matches, then you found the right place.

否则，您遇到了冲突，必须在链接列表中进行爬网并比较键，直到匹配为止。 （请注意，某些实现使用二进制树而不是链接列表进行冲突）。

Otherwise, you've had a "collision" and must crawl through the linked list and compare keys until you match. (note some implementations use a binary tree instead of linked list for collisions).

请查看此快速哈希表实现：

Check out this fast hash table implementation:

https://attractivechaos.wordpress.com/2009/09 / 29 / khash-h /

这篇关于用C实现HashMap的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！