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
Solved

map in C++ v/s HashMap in Java

Posted on 2011-03-01
7
766 Views
Last Modified: 2012-05-11
Could you tell me if the time complexity of operations with a map in C++ and HashMap in Java are the same?
IF not, please tell me the time complexity of operations such as Insert/Delete/Search in a map in C++.

Thanks!
0
Comment
Question by:dshrenik
7 Comments
 
LVL 86

Expert Comment

by:CEHJ
ID: 35006673
I would doubt they were any different. In theory both languages should use the best possible complexity
0
 
LVL 53

Accepted Solution

by:
Infinity08 earned 334 total points
ID: 35006744
std::map in C++ is NOT a hash table. Most implementations use a BST (binary search tree) to implement std::map, so its time complexity is quite different from that of a hash table.

For example : std::map has O(log n) search complexity for example, while a well-implemented hash table would have O(1) complexity for the same operation.
0
 

Author Comment

by:dshrenik
ID: 35006818
I'm sorry.

Can you tell if C++'s hash_map and Java's HashMap have the same time and space complexity?
0
Free Tool: IP Lookup

Get more info about an IP address or domain name, such as organization, abuse contacts and geolocation.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

 
LVL 53

Expert Comment

by:Infinity08
ID: 35006854
>> Can you tell if C++'s hash_map and Java's HashMap have the same time and space complexity?

I'm not 100% sure about the Java HashMap implementation, but afaik there is a normal hash table behind it.
The std::hash_map in C++ is currently an extension, so the specific implementation depends on the implementer (but the general consensus seems to be a normal hash table).

So, yes : the complexities would be very similar, if not the same.

As always with hash tables though : a lot depends on your choice of hash function, and a proper dimensioning of the hash table (as well as collision strategy if appropriate).
0
 
LVL 33

Expert Comment

by:sarabande
ID: 35008655
can you tell about your keys? and the number of entries now and in future? is your main concern a fast read and find of existing keys or a fast insert/update/delete ?

you may think of making test implementations for either map. if you can serve realistic test data you reliably will know what is the best container for your purpose.

Sara
0
 
LVL 27

Assisted Solution

by:dpearson
dpearson earned 166 total points
ID: 35009443

Can you tell if C++'s hash_map and Java's HashMap have the same time and space complexity?

In terms of space, both will be O(n) - there is one entry in the map for each key and then a list of entries where the keys collide, but each (key,value) pair in the map will appear only once in the data structure so they're O(n) for space.

In terms of time complexity, inserts will be O(1) [locating the hashed entry is a constant time operation and adding to the end of the list of items for a key should also be a constant time operation].  Reads will be O(log n) because the process is locate the hashed entry (which is constant time) and then walk the list of items with the same hash value - which will tend to log n for a large n and a fixed map size.  (If you make your map as large as your key space then this will instead be O(1) - but that's not a typical usage pattern for maps).

C++ and Java will both have the same complexity.

Doug
0
 
LVL 53

Assisted Solution

by:Infinity08
Infinity08 earned 334 total points
ID: 35009478
>> (If you make your map as large as your key space then this will instead be O(1) - but that's not a typical usage pattern for maps).

It is typical for many hash table needs to avoid collisions as much as possible though.
0

Featured Post

Free Tool: Port Scanner

Check which ports are open to the outside world. Helps make sure that your firewall rules are working as intended.

One of a set of tools we are providing to everyone 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

Suggested Solutions

Title # Comments Views Activity
DCT of  2D array using fftw in c++ 9 62
ejb on wildfly 5 30
jsp insert to database example 2 44
C++ help/ Toy problem 19 29
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…
Container Orchestration platforms empower organizations to scale their apps at an exceptional rate. This is the reason numerous innovation-driven companies are moving apps to an appropriated datacenter wide platform that empowers them to scale at a …
This video teaches viewers about errors in exception handling.
The viewer will be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.

808 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