在 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屋！