What are the disadvantages to hashmaps?

Question

Whatever language I use, I always aim to use the equivalent of a hashmap. However, I was going through some practice interview questions and it asked what is the limitation to this?

The only reason I could think of is limited main memory, but then that wouldn't be limited only to hashmaps, but also ArrayLists etc etc.

Solution 1

There's also the potential for collisions. The cost of writing and/or executing the hashing-function could be high if the requirement for collision avoidance is strict, or if you have a small hash-space.

Solution 2

1. Whilst hash-tables have constant time insertion, a hash-table will occasionally need to grow its internal structure and re-bucket its entries. This is an operation that has a cost proportional to the current size of the hash-table. The result of this is that insertion time is not always consistent, i.e. insertion will be constant, O(1), but occasionally you will notice a linear delay, O(n) as the table is grown. (This behaviour characteristic has led some to suggest favouring a tree over hash-table in the default/naïve case.)
2. You need to make sure the hashing algorithm of the item you are adding is sound. What this means that for an arbitrary set of elements, the resultant hash-codes are spread well across the range of the hash-code type (in Java and C# this is int). If you have a number of items with the same value (zero anyone?) then your hash-table will degrade into an elaborate linked-list and performance will dramatically decrease.
3. You need to ensure that the hash-code of your items does not change over time and that the equality method (Java's equals() or .NET's Equals()) is implemented to compare the same set of fields used for the hash-code. (Ideally this would mean the objects you add to the table are immutable but alternatively you may instead make sure that any mutable fields have no bearing on the hash-code calculation and equals method: a risky strategy. With changing hash-codes the table will not be able to find the entries you have already added to it when you later come to retrieve them.
4. Hash-tables do not, generally, preserve ordering -- be it natural ordering or order of insertion. (Those that do typically employ a parallel structure to maintain the ordering, or else perform a relatively expensive sort at time of iteration.)

See also:

• http://web.archive.org/web/20090430172748/http://enfranchisedmind.com/blog/posts/problems-with-hash-tables/
• http://en.wikipedia.org/wiki/Hash_table#Drawbacks

Solution 3

Use the right data structure for the right job. If you don't need access by a key, don't use a Map.

In terms of HashMap limitations, I guess it can suffer if items have a bad hashing algorithm, but thats about it.

Solution 4

Chained hash tables also inherit the disadvantages of linked lists. When storing small keys and values, the space overhead of the next pointer in each entry record can be significant. An additional disadvantage is that traversing a linked list has poor cache performance, making the processor cache ineffective.

from Wikipedia - Hash Tables

Solution 5

Hash map usage is situational.

If your Hash key is not chosen well ur hash map run at the speed equivalent to that of a list, with the added issue of huge memory hog.

In general Hashmaps are a bad choice when ur gonna perform iterative tasks on your data.

View more solutions