Hi,
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?
+10
A:
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
2010-03-30 00:24:28
Hashmaps generally use more memory as well.
GMan
2010-03-30 00:35:10
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.
Steve314
2010-03-30 00:41:19
@Steve - I mentioned that O(1) was average case and O(n) was worst case. @GMan - Thanks, I'll add that.
Peter Alexander
2010-03-30 00:43:52
@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.
Steve314
2010-03-30 00:51:54
@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
2010-03-30 01:57:26
@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.
GMan
2010-03-30 02:11:59
@GMan: Ah, yes. Got that, thanks.
jasonline
2010-03-30 02:17:44
+2
A:
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
2010-03-30 01:09:37
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.
Steve314
2010-03-30 01:17:31
A:
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.
Steve314
2010-03-30 01:14:23