How does a HashMap work?

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.