Hash tables in C++

Please tell me how I can implement hash tables in C++.

Thanks!
dshrenikAsked:
Who is Participating?
 
McNeticConnect With a Mentor Commented:
You can for example use stl "map" class, described here: http://www.cplusplus.com/reference/stl/map/

Basically, it works like this:

std::map <std::string, char> grade_list;

grade_list["John"] = 'B';

etc...
0
 
Infinity08Commented:
That's a pretty generic question. Could you narrow it down a bit ? What is your specific issue ? What will this hash table be used for ? What are the characteristics of its usage ? Etc.
0
 
Infinity08Connect With a Mentor Commented:
>> You can for example use stl "map" class, described here: http://www.cplusplus.com/reference/stl/map/

That is NOT a hash table.
0
Cloud Class® Course: Certified Penetration Testing

This CPTE Certified Penetration Testing Engineer course covers everything you need to know about becoming a Certified Penetration Testing Engineer. Career Path: Professional roles include Ethical Hackers, Security Consultants, System Administrators, and Chief Security Officers.

 
dshrenikAuthor Commented:
I would want something similar in complexity to HashMap in Java.
They must have the same complexity with operations such as insert/delete/search, when compared to Java's HashMap.

Thanks!
0
 
McNeticCommented:
Technically, a map must not be a hash table; however, a hash table is an implementation of an associative array, and a stl map is also an implementation of an associative array. Also, I can not imagine how this would be implemented without using a hash table.
I think this is what the author asked for, if not, he should elaborate.

@Infinity08: This is probably a bit off topic, but if you think I'm wrong, could you please explain? Or give a link to an explanation?
0
 
McNeticCommented:
Ok, I'm sorry, I found it by myself. A map is usually implemented by a tree, and has a complexity of O(log n). C++0X has a hash_map which might be the right thing.
0
 
Infinity08Connect With a Mentor Commented:
>> C++0X has a hash_map which might be the right thing.

Some mainstream compilers have already provided an implementation of std::hash_map as an extension. So, maybe you already have one available on your platform.
0
 
dshrenikAuthor Commented:
So C++'s hash_map and Java's HashMap have the same time and space complexity?
0
 
Infinity08Commented:
I think this is already being addressed in your other question : http://www.experts-exchange.com/Programming/Languages/CPP/Q_26855003.html ... right ?

If this one is a duplicate, please feel free to delete it.
0
 
dshrenikAuthor Commented:
Well, I did not "Java" as a zone for this. Hence the other question.
0
 
Infinity08Commented:
Well, it's up to you ... if you no longer need this one, you can delete it. If you want to steer it in a different direction than the difference between a Java HashMap and a C++ hash_map, you can of course keep it open ;)
0
 
evilrixConnect With a Mentor Senior Software Engineer (Avast)Commented:
If you are just after a good solid implementation of a hash map you could do worse than look at Google's implementation.
http://google-sparsehash.googlecode.com/svn/trunk/doc/index.html

It works on both Windows and Linux and is available on most Linux distros as a package you can install.
0
 
trinitrotolueneConnect With a Mentor Director - Software EngineeringCommented:
If you are looking at accurate performance figures you would need to profile your code with the different implementations

VS2010 provides implementations in <unordered_map>

Previously MS supported hash_maps via extensions in the stdext and cliext namespaces

http://msdn.microsoft.com/en-us/library/1fe2x6kt%28v=VS.100%29.aspx

You could also take a look at STLPort's implementation here
0
 
trinitrotolueneDirector - Software EngineeringCommented:
My suggestion is give the MS implementation a good look. You can find it here
0
 
trinitrotolueneDirector - Software EngineeringCommented:
With the MS implementation in <unordered_map> you can also set the maximum load factor. So this would enable you to tweak the performance to a large extent. The Maximum load factor as you would know controls the bucketing.

So you could either go with the default bucketing or have a say in it by tweaking the load factor
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.