In-depth Overview of Java HashMap and ConcurrentHashMap: Structure, Operations, and Performance

This document presents a detailed collection of interview‑style questions and answers about Java's HashMap and ConcurrentHashMap, explaining their underlying data structures, hashing logic, load factor, resizing behavior, and concurrency mechanisms.

1. HashMap data structure

HashMap uses a hash table composed of an array of buckets, each bucket holding a linked list of Node<K,V>[] table. When a bucket's list exceeds eight elements, it is transformed into a red‑black tree.

2. How HashMap works

When inserting (put), the key's hash is computed, the array index is derived, and the entry is placed. If a collision occurs, the new node is appended to the list (or tree). Retrieval (get) recomputes the hash, locates the bucket, and traverses the list/tree using equals() to find the matching key.

3. Hash collisions

Identical hash codes do not guarantee equality; they cause collisions, leading to multiple nodes in the same bucket.

4. Hash function implementation (JDK 1.8)

The hash is computed as (h = k.hashCode()) ^ (h >>> 16), mixing high and low bits to reduce collisions.

5. Use of XOR

XOR ensures that any single‑bit change in the original 32‑bit hashCode alters the final hash value, minimizing collisions.

6. Table capacity, load factor, and resizing

Default capacity is 16 (maximum 1<<30); can be set via constructor.

Load factor defaults to 0.75; when size exceeds capacity * loadFactor, the table is resized (typically doubled).

Resizing incurs performance overhead, which can be critical in high‑throughput scenarios.

7. put() process

Compute hash, locate bucket, handle collisions (list or tree), replace existing value if key matches, and trigger resize when threshold is exceeded.

8. Array resizing

A new array twice the size is allocated and each existing node is rehashed to either the original index or original index plus old capacity.

9. Why red‑black tree instead of binary search tree

Red‑black trees provide balanced search performance, avoiding the linear‑time worst case of unbalanced binary trees, while still incurring less overhead than always using a tree for short lists.

10. Red‑black tree properties

Each node is either red or black.

The root is black.

Red nodes have black children.

All leaves (NIL) are black.

Every path from root to leaf contains the same number of black nodes.

11. Changes in JDK 1.8 HashMap

Lists longer than 8 become red‑black trees (bucket count must exceed 64).

Insertion order changed from head‑insertion (JDK 1.7) to tail‑insertion (JDK 1.8).

Entry class replaced by Node.

12. Differences among HashMap, LinkedHashMap, TreeMap

LinkedHashMap preserves insertion order; iteration is slower than HashMap.

TreeMap implements SortedMap and orders entries by key (natural or custom comparator).

13. Typical usage scenarios

HashMap – general‑purpose map for fast insert, delete, lookup.

TreeMap – when ordered traversal by key is required.

LinkedHashMap – when iteration order must match insertion order.

14. HashMap vs. Hashtable

HashMap is not thread‑safe; Hashtable is synchronized.

Hashtable does not allow null keys or values; HashMap allows one null key and multiple null values.

Default sizes differ (HashMap 16, Hashtable 11) and resizing strategies vary.

15. Thread‑safe alternative similar to HashMap

ConcurrentHashMap provides high‑performance thread safety using segment locks (JDK 1.7) or CAS + synchronized (JDK 1.8).

16. HashMap vs. ConcurrentHashMap

Both differ mainly in locking; ConcurrentHashMap forbids null keys/values.

17. Why ConcurrentHashMap outperforms Hashtable

Hashtable uses a single lock for the entire map, causing contention, whereas ConcurrentHashMap employs finer‑grained locking (segments or node‑level CAS), allowing higher concurrency.

18. ConcurrentHashMap lock mechanisms (JDK 1.7 vs 1.8)

JDK 1.7 uses segmented locks (each Segment extends ReentrantLock) and HashEntry objects. JDK 1.8 replaces segments with a plain array of Node s, using CAS and synchronized for updates, and converts long chains to red‑black trees when necessary.

19. Why synchronized replaces ReentrantLock in JDK 1.8

Lock granularity is reduced.

JVM optimizations for synchronized are more mature.

ReentrantLock incurs higher memory overhead under heavy contention.

20. Key fields of ConcurrentHashMap private transient volatile int sizeCtl; – controls initialization and resizing.

21. Data structures inside ConcurrentHashMap Node – basic storage unit, extends HashMap.Entry. TreeNode – node used in red‑black tree representation. TreeBin – container for TreeNode handling tree conversion and locking.

22. put() workflow

If table not initialized, call initTable().

If no hash conflict, insert via CAS.

If conflict, lock the bucket; insert into list or tree.

If list length exceeds 8, convert to red‑black tree.

After successful insertion, update size via addCount() and trigger resize if needed.

23. Resizing (transfer())

Default capacity is 16; during resize the capacity doubles. Multiple threads may assist via helpTransfer() for better throughput.

24. get() workflow

Compute hash, locate bucket.

If first node matches, return it.

If resizing in progress, follow ForwardingNode to the new table.

Otherwise traverse list/tree to find matching key; return null if not found.

25. ConcurrentHashMap concurrency level

The maximum number of threads that can update the map simultaneously without contention; default is 16, rounded up to the nearest power of two.

Source: cnblogs.com/Young111/p/11519952.html