How to implement a Hashmap in C Help Please!

[gwolf1]

Hi Everyone,

I was wondering how I can implement a hashmap function in C. I have to define a struct:

struct hashmap;
typedef struct hashmap hashmap;

This has to be a multimap so that a key can point to different values.

If also need to initialise this hashmap like so:

hashmap* hm_initialize();

Any help is greatly appreciated!

[deceptikon]

Do you know anything about hash tables? That's the first step, as a hashmap as it's usually seen is really just a pretty interface over a hash table.

[rubberman]

There is no standard hashmap for C, though there is for C++ (a template class). You are going to need to do the heavy lifting to implement this yourself, or find some open source code that implements it. As I have implemented such code in the past (not open source, sorry - belongs to Applied Materials now), I know something of this subject. First, you need to use a good hashing algorithm that will generate non-colliding key hashes. Those keys are then used to index the data records.

A good source of information on how to implement this stuff is Donald Knuth's "The Art of Computer Programming", volume 3, "Sorting and Searching".

[gwolf1]

So how would I do this?

[deceptikon]

So how would I do this?

Start by turning on your brain, reading the provided links and references, and then doing some actual work to apply what you learn. Seriously, I'm sensing a complete lack of effort and unwillingness to think on your part. Nobody is going to do this for you or hold your hand, especially if you act like you're somehow entitled to it.

[gwolf1]

Start by turning on your brain, reading the provided links and references, and then doing some actual work to apply what you learn. Seriously, I'm sensing a complete lack of effort and unwillingness to think on your part. Nobody is going to do this for you or hold your hand, especially if you act like you're somehow entitled to it.

I'm sorry that you came to the conclusion that I'm not willing to put in the work to fnish my own projects. That is the reason I came to Daniweb in the first place. I wanted some input on how to start this project properly and thats why I didnt post the ALL OF THE CODE. I understand that there are alot of people that come here and ask you guys to complete their projects, but you shouldnt just insult someone like that just because you have the knowledge to complete it and the other person whos posting does not. Nobody is entitled to their work being done for them, but no one should be insulted like. As constructive critisicm is always welcome, nobody should be ridiculed like that.

[deceptikon]

As constructive critisicm is always welcome, nobody should be ridiculed like that.

Ridiculed? Insulted? I think you're being overly sensitive here. Anyway, I call it like I see it, and if you didn't want it seen that way then the onus is on you to post more carefully. You posted insufficient code to show proof of effort in the first place, and immediately shot back with "So how would I do this?" after being given two excellent resources. How are we to interpret this as anything but an unwillingness to think and work?

I apologize if my words are too harsh, and I'm more than happy to help you if you ask a specific question about hashmap implementation. However, you need to understand that this isn't a simple task, and nobody can tell you how to do it without essentially writing the same thing from either my first link or the book rubberman recommended.

Your question is akin to asking how one would perform brain surgery; it's not something that can be answered without a significant amount of prerequisite information that most people will be unwilling to give you when you appear as if you're too lazy to acquire it on your own. Further, even with the prerequisite information, the answer is so complex, verbose, and varied that nobody will be willing to provide detailed instructions from start to finish.

So go forth and do some research. Try things on your own. When you have a specific difficulty in concept or implementation, please don't hesitate to ask for help with it. You'll find that we're very helpful when it comes to specific questions because they're possible to answer without writing a tome.

I'd also recommend reading the How To Ask Smart Questions site for hints on how to ask a better question.

@james sir, truly saying you, how sweetly you behave. after reading these posts, I know you didn't have said anything harsh, still you saying "i apologize". hats off to you. Day be day, I am going to be fan of yours :-) am lucky to have teacher like you :)

[Schol-R-LEA]

@gwolf1: The link which Deceptikon provided - which I will repeat here - gives detailed explanations and code samples for managing different sorts of hash tables. It should give you enough of an overview to get you started, and would surely do a better job than we could do by attempting to answer you on the fly.

Some additional links which may prove useful:
+ Wikipedia: Hash Table
+ Wikipedia: Hash Function
+ Wikibooks: Hash Tables
+ Hash Tables
+ Literate Programming: Hash Table in C
+ Simple C Hash Table Example

[rubberman]

FWIW, use the sha256 hash algorithm if you want to generate a REALLY unique hash value. So far, there are no collisions detected, anywhere! If you do detect one, publish it - you will gain instant internet fame! :-)

[deceptikon]

FWIW, use the sha256 hash algorithm if you want to generate a REALLY unique hash value.

A cryptographically secure hash is far too slow and heavy for most hash table applications. When working with hash tables you want the fastest possible hash algorithm that produces the fewest collisions for the expected data. Collisions are easy to resolve, and they only become an issue when there are so many that the resolution method begins to overwhelm the primary lookup.

So far, there are no collisions detected, anywhere! If you do detect one, publish it - you will gain instant internet fame! :-)

Sorry, but in the context of hash tables it's easy (even trivial) to create a collision unless you design a perfect hash for that specific application. Keep in mind that the hash is being munged to fit into the range of table indices. While SHA-256 may not produce collisions when unrestricted, you'll be bombarded with collisions the instant those hashes are forced into a [0,N] hash table, where N is significantly smaller than the upper range of the hash. This is the basic pigeonhole principle.