实现一个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.

一般来说，你创建一个名为包含键和值桶的数组，带有可选的指针来创建一个链接列表。

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:

<一个href=\"http://attractivechaos.awardspace.com/khash.h.html\">http://attractivechaos.awardspace.com/khash.h.html

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