Solved

Hash tables in C++

Posted on 2011-03-01
15
396 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 100 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 200 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
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!

 

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 200 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 100 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 100 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

Free Tool: ZipGrep

ZipGrep is a utility that can list and search zip (.war, .ear, .jar, etc) archives for text patterns, without the need to extract the archive's contents.

One of a set of tools we're offering as a way to say thank you for being a part of the community.

Question has a verified solution.

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

Templates For Beginners Or How To Encourage The Compiler To Work For You Introduction This tutorial is targeted at the reader who is, perhaps, familiar with the basics of C++ but would prefer a little slower introduction to the more ad…
What is C++ STL?: STL stands for Standard Template Library and is a part of standard C++ libraries. It contains many useful data structures (containers) and algorithms, which can spare you a lot of the time. Today we will look at the STL Vector. …
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 learn how to user default arguments when defining functions. This method of defining functions will be contrasted with the non-default-argument of defining functions.

733 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