HashMap vs ConcurrentHashMap: Java Structure, Operations, and Performance

HashMap Data Structure – implemented as an array of buckets where each bucket holds a linked list of Node<K,V> entries; when a bucket’s list exceeds 8 elements it is transformed into a red‑black tree.

How HashMap Works – put(K,V) computes hash(K), determines the array index, checks the load factor (default 0.75) and resizes when size > capacity·loadFactor. On insertion, if the key is new the entry is added; if the key exists, equals determines whether to replace the value or handle a collision by appending to the list or tree.

Collision Handling – identical hashCode values may map to the same bucket, causing a collision. JDK 1.7 inserts new nodes at the head of the list; JDK 1.8 inserts at the tail. When the list length exceeds TREEIFY_THRESHOLD = 8, it is converted to a red‑black tree to keep lookup time logarithmic.

Hash Function – JDK 1.8 improves the hash by mixing the high 16 bits with the low 16 bits: h = k.hashCode() ^ (h >>> 16), reducing collisions caused by poor hashCode implementations.

Table Capacity and Load Factor – default capacity is 16 (max 1<<30). The load factor (default 0.75) determines the threshold at which the table is resized (e.g., 16 × 0.75 = 12). Resizing doubles the array size and re‑hashes entries.

put Process Summary – compute hash, locate bucket, insert directly if no conflict, otherwise append to list or tree; if the bucket size exceeds the threshold, treeify; after successful insertion, update size and trigger resize if needed.

Array Expansion – a new array twice the old size is allocated; each entry is re‑hashed to either its original index or original index + old capacity.

Why Red‑Black Tree Instead of Binary Search Tree – plain binary trees can degenerate into a linear chain under certain key orders, leading to O(n) lookups. Red‑black trees remain balanced, providing O(log n) performance at the cost of extra rotation and recoloring operations.

HashMap vs LinkedHashMap vs TreeMap

LinkedHashMap preserves insertion order; iteration is slower than HashMap.

TreeMap implements SortedMap, ordering entries by key (natural or custom comparator).

HashMap offers the fastest average‑case insert, delete, and lookup.

HashMap vs Hashtable

Hashtable is synchronized (thread‑safe) while HashMap is not.

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

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

ConcurrentHashMap – a thread‑safe, high‑performance alternative introduced in java.util.concurrent. JDK 1.7 uses segmented locks (each segment is a ReentrantLock); JDK 1.8 replaces segments with CAS‑based updates and synchronized blocks, and also employs red‑black trees for long chains.

Lock Mechanism Differences

Segmented locks give finer granularity than a single lock in Hashtable.

JDK 1.8 reduces lock granularity further by locking at the node level and relying on JVM‑optimized synchronized.

ConcurrentHashMap Concurrency Level – the maximum number of threads that can update the map without contention; default is 16 and is rounded up to the nearest power of two.