Solved

Hash tables in C++

Posted on 2011-03-01
15
392 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
How to improve team productivity

Quip adds documents, spreadsheets, and tasklists to your Slack experience
- Elevate ideas to Quip docs
- Share Quip docs in Slack
- Get notified of changes to your docs
- Available on iOS/Android/Desktop/Web
- Online/Offline

 

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

Enabling OSINT in Activity Based Intelligence

Activity based intelligence (ABI) requires access to all available sources of data. Recorded Future allows analysts to observe structured data on the open, deep, and dark web.

Join & Write a Comment

Suggested Solutions

Title # Comments Views Activity
cb: unreferenced local variable 11 65
How to convert MFC APP to Win32 APP. 19 55
c++ syntax question 9 34
Header of docx file 17 58
When writing generic code, using template meta-programming techniques, it is sometimes useful to know if a type is convertible to another type. A good example of when this might be is if you are writing diagnostic instrumentation for code to generat…
Often, when implementing a feature, you won't know how certain events should be handled at the point where they occur and you'd rather defer to the user of your function or class. For example, a XML parser will extract a tag from the source code, wh…
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.

706 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

19 Experts available now in Live!

Get 1:1 Help Now