Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
?
Solved

Hash tables in C++

Posted on 2011-03-01
15
Medium Priority
?
402 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
VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

 

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

Free Tool: Path Explorer

An intuitive utility to help find the CSS path to UI elements on a webpage. These paths are used frequently in a variety of front-end development and QA automation tasks.

One of a set of tools we're offering as a way of saying 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

Introduction This article is the first in a series of articles about the C/C++ Visual Studio Express debugger.  It provides a quick start guide in using the debugger. Part 2 focuses on additional topics in breakpoints.  Lastly, Part 3 focuses on th…
This article shows you how to optimize memory allocations in C++ using placement new. Applicable especially to usecases dealing with creation of large number of objects. A brief on problem: Lets take example problem for simplicity: - I have a G…
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 additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.
Suggested Courses

618 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