?
Solved

Hash tables in C++

Posted on 2011-03-01
15
Medium Priority
?
399 Views
Last Modified: 2012-05-11
Please tell me how I can implement hash tables in C++.

Thanks!
0
Comment
Question by:dshrenik
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 5
  • 3
  • 3
  • +2
15 Comments
 
LVL 8

Accepted Solution

by:
McNetic earned 400 total points
ID: 35006619
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
 
LVL 53

Expert Comment

by:Infinity08
ID: 35006626
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
 
LVL 53

Assisted Solution

by:Infinity08
Infinity08 earned 800 total points
ID: 35006630
>> You can for example use stl "map" class, described here: http://www.cplusplus.com/reference/stl/map/

That is NOT a hash table.
0
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 

Author Comment

by:dshrenik
ID: 35006694
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
 
LVL 8

Expert Comment

by:McNetic
ID: 35006719
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
 
LVL 8

Expert Comment

by:McNetic
ID: 35006762
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
 
LVL 53

Assisted Solution

by:Infinity08
Infinity08 earned 800 total points
ID: 35006788
>> 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
 

Author Comment

by:dshrenik
ID: 35006814
So C++'s hash_map and Java's HashMap have the same time and space complexity?
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 35006865
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
 

Author Comment

by:dshrenik
ID: 35006898
Well, I did not "Java" as a zone for this. Hence the other question.
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 35006920
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
 
LVL 40

Assisted Solution

by:evilrix
evilrix earned 400 total points
ID: 35007532
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
 
LVL 12

Assisted Solution

by:trinitrotoluene
trinitrotoluene earned 400 total points
ID: 35033283
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
 
LVL 12

Expert Comment

by:trinitrotoluene
ID: 35033293
My suggestion is give the MS implementation a good look. You can find it here
0
 
LVL 12

Expert Comment

by:trinitrotoluene
ID: 35033322
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

Featured Post

Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

  Included as part of the C++ Standard Template Library (STL) is a collection of generic containers. Each of these containers serves a different purpose and has different pros and cons. It is often difficult to decide which container to use and …
This article will show you some of the more useful Standard Template Library (STL) algorithms through the use of working examples.  You will learn about how these algorithms fit into the STL architecture, how they work with STL containers, and why t…
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.
The viewer will be introduced to the member functions push_back and pop_back of the vector class. The video will teach the difference between the two as well as how to use each one along with its functionality.
Suggested Courses

777 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question