HashMap is a popular interview topic due to its many nuances. The best preparation is often to read the source code of
HashMap. The implementation is already discussed in detail in numerous articles.
Here is the cheat sheet with key aspects to remember:
- Basic Principle: An internal array called
table contains buckets — sub-lists of items that share the same recalculated hash sums; - Hash sum recalculation to fit
int indexes in capacity cells of the table; Rehashing: doubling the size of the table when the number of occupied buckets reaches threshold (capacity*loadFactor);- Inability to shrink once the
table expanded; - Two methods of collision resolution: chaining that is actually used in
HashMap, and open addressing alternative; - Concurrency options: over-synchronized
Hashtable and sophisticated ConcurrentHashMap; - Java 8 optimization: transforming the list in a bucket into a tree when it reaches 8 elements to improve access time from O(n) to O(log n) in the case of many collisions;
- Explicit use of bucket 0 for a
null key; - Relation to
HashSet – a HashMap where only keys are utilized; - Absence of order guarantees.
Discussing this topic during an interview will likely touch on the characteristics of the
equals/hashCode methods. There might also be a discussion about alternative key-value stores like
TreeMap and
LinkedHashMap.