Top Java Interview Questions for investment banks, health care IT, product companies, e-commerce on Core Java, Spring, Hibernate, Concurrency, Algorithms, Data Structures, Design Patterns, interview questions for experienced.
Thursday, January 21, 2016
Discuss Internals of Hashmap in Java
Important Facts about HashMap
HashMap is a container of pairs
HashMap is list of Buckets arranged by hashcode of key
When a bucket gets too large, hashmap implementation will change that bucket implementation to something like TreeMap, simply by checking number of elements in each bucket. This allows faster lookup when there are too many hash collisions
Get, Put and Remove method offers Big O (1) time complexity (constant runtime), assuming the hash function disperses the elements properly among the buckets
Load factor (default value of 0.75) decides when hashmap will regrow, when capacity reaches of the hashmap is 75% (0.75 is load factor) full, then hashmap will double its size
Size of hashmap is always expressed in 2n to allows faster hashcode calculations using bitwise operator instead of modulus operator. Even if you provide a different capacity at the time of hashmap construction, it will automatically be adjusted to nearest 2n
Capacity and Size are two different things - size is actual number of elements present in hashmap, capacity is size of its internal table at any given point in time. Capacity grows when size becomes equal to capacity x load factor
As a general rule, the default load factor (.75) offers a good tradeoff between time and space costs. Higher values decrease the space overhead but increase the lookup cost (reflected in most of the operations of the HashMap class, including get and put).
Bucket uses TreeNode instead of normal Node if it contains elements more than specified in TREEIFY_THRESHOLD, which is defaulted to 8
The iterators returned by all of this class’s “collection view methods” are fail-fast: if the map is structurally modified at any time after the iterator is created, in any way except through the iterator’s own remove method, the iterator will throw a ConcurrentModificationException. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.
HashMap is defined as Array of Nodes as shown below