5

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?

Peter Alexander
  • 53,344
  • 14
  • 119
  • 168
skydoor
  • 25,218
  • 52
  • 147
  • 201
  • Kind of similar, maybe not a dupe though: http://stackoverflow.com/questions/2196995/is-there-any-advantage-of-using-map-over-unordered-map-in-case-of-trivial-keys/ – GManNickG Mar 30 '10 at 00:26
  • 1
    Be a little careful with terminology. In some circles, a "map" just refers to an object that does key/value storage and lookup, and a "hashmap" is one implementation of a map. (Where a tree map might be another.). IOW, "map" is an interface, and "hash map" is one concrete implementation. (I'm noting this because your question isn't tagged as or refers to any particular library.) – Ben Zotto Mar 30 '10 at 00:37
  • 3
    @Ben: In C++ `map` almost unambiguously refers to `std::map`, a tree. – GManNickG Mar 30 '10 at 00:40

3 Answers3

10

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

Peter Alexander
  • 53,344
  • 14
  • 119
  • 168
  • Hashmaps generally use more memory as well. – GManNickG Mar 30 '10 at 00:35
  • IMO the O(1) claim for hash tables is a bit of a cheat. There's a fixed bound to the number of keys recognised as distinct without collision handling, and once you get collisions, performance deteriorates to that of your collision handling (often O(n)). OK, the hash has traditionally supported as many unique keys as you can store in memory anyway - but I wonder how many people have neglected to upgrade custom hash calculations from 32 bits to 64 bits, and will get performance degredation with very large hash tables. No size hash table will solve that if the hash itself is too narrow. –  Mar 30 '10 at 00:41
  • @Steve - I mentioned that O(1) was average case and O(n) was worst case. @GMan - Thanks, I'll add that. – Peter Alexander Mar 30 '10 at 00:43
  • @Poita - yes, but my comment relates to a specific and often ignored way in which that theoretical O(n) worst case can become a real world fact. Even when we're using 512bit machines if that ever happens, your existing std::map code will just work - but old hashmap-based code may well need (yet another) reworking to exploit the huge memories of that future time efficiently. –  Mar 30 '10 at 00:51
  • @GMan: Just a clarification, how does hashmap use more memory than the map? Does this happen only in some situations (e.g. few elements) or at all times? Map is implemented as a tree which results to additional pointers. – jasonline Mar 30 '10 at 01:57
  • @jasonline: It depends on implementation, and I have no numbers, but consider a hash map needs to have a large contiguous array to avoid collisions. There will likely be unused slots, etc. Contrarily, a map simply has a constant sized memory allocation per node. No wasted memory. – GManNickG Mar 30 '10 at 02:11
3

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.

rlbond
  • 65,341
  • 56
  • 178
  • 228
  • To be honest, trees and hashmaps have equal problems here. It's an issue I've recently had to address with using finite automata as keys. You can't just do a hash (or comparison) of the in-memory representation because equivalent automata can have different representations. The solution is to derive a canonical form. Once you have a canonical form, you can work equally well from in-memory representations, whether you are comparing or hashing - and that applies for just about any kind of data. If you can hash, you can just as easily define an arbitrary but consistent ordering. –  Mar 30 '10 at 01:17
0

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.