Solved

Hash tables in C++

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

Thanks!
0
Comment
Question by:dshrenik
  • 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
 

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
Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

 

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

Is Your Active Directory as Secure as You Think?

More than 75% of all records are compromised because of the loss or theft of a privileged credential. Experts have been exploring Active Directory infrastructure to identify key threats and establish best practices for keeping data safe. Attend this month’s webinar to learn more.

Question has a verified solution.

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

Suggested Solutions

Title # Comments Views Activity
How to split this in C++ 4 94
Unresolved External Symbols 3 68
object oriented programming comparison 5 54
Embarcadero C++ Builder XE10.1 Berlin red arrow Indicator 2 16
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…
Go is an acronym of golang, is a programming language developed Google in 2007. Go is a new language that is mostly in the C family, with significant input from Pascal/Modula/Oberon family. Hence Go arisen as low-level language with fast compilation…
The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.

911 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

Need Help in Real-Time?

Connect with top rated Experts

25 Experts available now in Live!

Get 1:1 Help Now