forked from rootusercop/IMP-Interview-Questions
-
Notifications
You must be signed in to change notification settings - Fork 0
/
HashMap Disadvantages
24 lines (23 loc) · 1.75 KB
/
HashMap Disadvantages
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
Very IMP Q -> Disadvantages of HashMap or Hashtable OR Why is BALANCED TREES better than using Hashtable
or HashMap?
Ans ->
In short:
1) Requires more main memory
2) Hashing algorithm does not result in spatial locality. Because hash tables cause
access patterns that jump around, this can trigger microprocessor cache misses that cause long delays.
3) Similar key types will result in more collision(LINEAR PROBING AND CHAINING IS THE APPROACH
USED TO SOLVE COLLSION PROBLEM IN HASHMAP) and hence the hashtable would be more like a linkedlist.
Collisions also ruin memory utilization- if I have 70 elements in 100 buckets, but those 70 elements hash to
only 4 buckets (and yes, Virginia, I’ve seen collision rates this bad), then 96 of my buckets aren’t doing
me any good at, I’m just wasting that space.
4) Occasionally HashMap/Hashtable requires resizing when the original size of HashMap/Hashtable buckets
are full. Resizing takes O(n) time as the elements from the previous hashtable/HashMap are transferred to
a new bigger Hashtable/HashMap. This is not good for implementation.
5) The concept that Hashtables/HashMap offers O(constant) (aka O(1) ) time complexity
for insertion, deletion and searchingis something to rethink on as the datastructure givies that
time complexity on a average scale, which is called as "AMORTIZED" time complexity. That means that there
would be atleast on instance out of n instances where the Time Complexity would be O(n) and not O(constant).
This is the time when the HashMap/Hashtable requires resizing.
http://stackoverflow.com/questions/6924852/what-are-the-disadvantages-to-hashmaps
http://web.archive.org/web/20090430172748/http://enfranchisedmind.com/blog/posts/problems-with-hash-tables/
http://en.wikipedia.org/wiki/Hash_table#Drawbacks