实现HashMap [英] Implementing a HashMap

问题描述

如何从头开始在C中创建Hashmap？
将考虑哪些参数，以及如何测试hashmap有多好？在你说哈希贴完成之前，你需要运行哪些基准测试用例。

How to go about creating a Hashmap in C from scratch ? What would be the parameters taken into consideration and what how would you test the hashmap as to how good it is ? As in what would be benchmark test cases which you require to run before you say that your hash map 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.

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

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:

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

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