Menu
As per Sun Java Implementation, during expansion, ArrayList grows to 3/2 it's initial capacity whereas for HashMap the expansion rate is double. What is reason behind this?
As per the implementation, for HashMap, the capacity should always be in the power of two. That may be a reason for HashMap's behavior. But in that case the question is, for HashMap why the capacity should always be in power of two?
769
The ArrayList has O(n) performance for every search, so for n searches its performance is O(n^2). The HashMap has O(1) performance for every search (on average), so for n searches its performance will be O(n). While the HashMap will be slower at first and take more memory, it will be faster for large values of n.
While HashMap stores elements with key and value pairs that means two objects. So HashMap takes more memory comparatively. ArrayList allows duplicate elements while HashMap doesn't allow duplicate keys but does allow duplicate values.
HashMap, being a hashtable-based implementation, internally uses an array-based data structure to organize its elements according to the hash function. HashMap provides expected constant-time performance O(1) for most operations like add(), remove() and contains(). Therefore, it's significantly faster than a TreeMap.
As the number of elements in the HashMap increases, the capacity is expanded. The load factor is the measure that decides when to increase the capacity of the Map. The default load factor is 75% of the capacity. The threshold of a HashMap is approximately the product of current capacity and load factor.
The expensive part at increasing the capacity of an ArrayList is copying the content of the backing array a new (larger) one.
For the HashMap, it is creating a new backing array and putting all map entries in the new array. And, the higher the capacity, the lower the risk of collisions. This is more expensive and explains, why the expansion factor is higher. The reason for 1.5 vs. 2.0? I consider this as "best practise" or "good tradeoff".
73
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
