Question

I only know that the difference between hashmap and map is that hashmap is implemented with hash function but map is implemented with tree. Could any body add anything more?

Based on this, is there any thing hashmap can do but map cannot?

Was it helpful?

Solution

  • Hashmaps have average case better performance for access (O(1)), but worse worst case performance (O(n)). Maps are always O(lg(n)).

  • Maps are ordered by their key, hashmaps are not.

  • Hashmaps generally use more memory than maps.

  • Maps typically allow for faster iteration.

  • Good hash functions are harder to write than good ordering functions (and more difficult to analyse).

I don't believe there's anything that a hashmap can do that a map can't.

OTHER TIPS

A map requires the key has a strict weak ordering, which perhaps may not exist. A hashmap only needs a hash function. So in this way a hashmap can be used with keys that have no strict weak ordering.

One advantage that hashmaps have over trees is that, in a multi-threading environment, you don't have to lock the whole container to add or remove a single key - locking the single relevant entry in the hash table is (almost) enough.

Almost because there may be metadata (number of items in the hashtable, for instance) to update. And you probably need to lock the whole table to grow or shrink it, of course.

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow