This course will introduce you to Ruby, as well as teach you about classes, methods, variables, data structures, loops, enumerable methods, and finishing touches.

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!

IF not, please tell me the time complexity of operations such as Insert/Delete/Search in a map in C++.

Thanks!

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).

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

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

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.

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.