🔒 Section 13 · Question #27

Can You Use Immutable Objects as Keys in HashMap

Core reasons:

🔒 Immutability 📄 Source Markdown

🟢 Junior Level

30-Second Summary

Not only can you, but you absolutely should! Immutable objects are the strongly recommended, gold standard for keys in HashMap, HashSet, and ConcurrentHashMap.

Core reasons:

  1. Hash Code Stability: An object’s hashCode() is derived from its immutable fields and is guaranteed to remain strictly constant across the entire lifetime of the JVM.
  2. Deterministic Bucket Resolution: In HashMap, bucket indexes are calculated via (capacity - 1) & hash. Because the hash code never mutates, map.get(key) reliably searches the exact bucket where the entry was originally stored during map.put(key, value).
  3. Zero Data Loss & No Memory Leaks: If a mutable key’s fields are altered after insertion, its hash code changes. The entry becomes permanently unretrievable, creating an orphaned “ghost” entry and a silent memory leak.

Premier Key Choices in Java

  • java.lang.String — The most widely used, heavily optimized key in Java.
  • Primitive Wrappers (Integer, Long, UUID).
  • Date/Time API (LocalDate, Instant).
  • Java Records (Java 16+) — The premier choice for composite multi-field keys.
Map<String, UserSession> sessions = new HashMap<>();
sessions.put("token_abc123", new UserSession("Alice"));

// Guaranteed to retrieve Alice's session reliably:
UserSession session = sessions.get("token_abc123");

🟡 Middle Level

The Mechanics of Key Lookup in HashMap

Every map.put(key, value) and map.get(key) operation executes three fundamental steps:

  1. Bit Spreader Hash Perturbation: 
    static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
  2. Bucket Index Resolution: index = (table.length - 1) & hash.
  3. Bucket Node Matching: Validates p.hash == hash && (p.key == key || (key != null && key.equals(p.key))).

If a key is mutable and changes state between put and get:

  • get(key) computes a new hash code, routing to a completely different bucket.
  • The method returns null, even though the entry remains physically stored in the original bucket in heap memory.

Lazy Hash Code Caching Optimization

Immutability unlocks one of the most powerful performance optimizations in the JVM: caching the calculated hashCode():

  • In String, the hash code is computed lazily upon first invocation and stored in private int hash.
  • All subsequent map.get("someKey") calls reuse the pre-calculated integer in $O(1)$ time without traversing characters.
  • Custom immutable classes can easily implement the same pattern:
public final class ImmutableOrderId {
    private final String prefix;
    private final long number;
    private int cachedHash; // Lazy cache field

    public ImmutableOrderId(String prefix, long number) {
        this.prefix = Objects.requireNonNull(prefix, "Prefix required");
        this.number = number;
    }

    @Override
    public int hashCode() {
        int h = cachedHash;
        if (h == 0) {
            h = Objects.hash(prefix, number);
            cachedHash = h;
        }
        return h;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof ImmutableOrderId that)) return false;
        return number == that.number && prefix.equals(that.prefix);
    }
}

🔴 Senior Level

Composite Keys Using Java 16+ Records

When lookup requires matching multiple fields (e.g. tenantId + userId), avoid error-prone string concatenations (tenantId + ":" + userId), which allocate transient garbage. Instead, use a concise Java record:

public record TenantUserKey(UUID tenantId, Long userId) implements Comparable<TenantUserKey> {
    @Override
    public int compareTo(TenantUserKey other) {
        int cmp = this.tenantId.compareTo(other.tenantId);
        return cmp != 0 ? cmp : this.userId.compareTo(other.userId);
    }
}

Senior Advantages:

  1. The record is implicitly final and component fields are private final.
  2. The compiler auto-generates mathematically consistent equals() and hashCode() methods over all components.
  3. Implementing Comparable protects against worst-case degradation during bucket hash collisions.

Collision Resolution and Treeification

When different immutable keys produce identical bucket indexes (Hash Collision):

  1. Entries are initially chained as a singly linked list inside the bucket.
  2. When collisions exceed 8 nodes (TREEIFY_THRESHOLD = 8) and total table capacity is at least 64 (MIN_TREEIFY_CAPACITY = 64), HashMap converts the linked list into a balanced Red-Black Tree (TreeNode).
  3. Search time drops from $O(N)$ to $O(\log N)$.
  4. If the key implements Comparable<K>, nodes are balanced and traversed via compareTo(), avoiding expensive fallback tie-break comparisons via System.identityHashCode().

High-Concurrency Context: ConcurrentHashMap

In ConcurrentHashMap, immutable keys are essential for lock-free scaling:

  • During concurrent table resizing (Concurrent Resizing), background threads migrate bins to the new table without acquiring exclusive table locks.
  • Reading threads traverse buckets completely lock-free.
  • Key immutability guarantees that hash evaluation and reference comparisons are atomic and free from data races across CPU caches.

4 Tricky Questions

1. Why does String store its cached hash code in a plain, non-volatile field private int hash, and why is this 100% thread-safe?

Answer: This is Java’s famous Benign Data Race idiom:

  1. String is strictly immutable, and its hash algorithm is a pure deterministic function: computing the hash from the identical immutable byte array always yields the exact same 32-bit integer.
  2. If two threads invoke hashCode() concurrently on a newly created String, both calculate the value independently and write the exact same integer into hash.
  3. In Java, 32-bit int writes are atomic by specification (unlike non-volatile 64-bit long/double), preventing torn reads.
  4. Omitting the volatile modifier eliminates CPU hardware memory fences (StoreLoad/StoreStore barriers), enabling maximum L1 cache read throughput.

2. What happens if a map key is defined as record GroupKey(List<String> tags) and an ArrayList is passed into it?

Answer: A severe hidden failure occurs:

  • While record generates final fields, it provides only shallow immutability.
  • The internal ArrayList reference cannot be reassigned, but the list itself remains mutable.
  • If external code calls tags.add("new_tag"), List.hashCode() dynamically recalculates based on its modified elements.
  • The GroupKey hash code changes, stranding the entry in its old bucket and causing future map.get() calls to return null.
  • Remedy: In composite keys containing collections, defensive copying via List.copyOf(tags) inside a compact constructor is mandatory.

3. Why should custom keys in HashMap implement Comparable<K> when the Map specification requires only equals() and hashCode()?

Answer: In Java 8+, when high hash collisions cause a bucket to treeify into a Red-Black Tree (TreeNode):

  • The tree must order elements to balance itself.
  • If keys implement Comparable<K>, HashMap orders and searches tree nodes using fast compareTo() invocations.
  • If keys do not implement Comparable, the JVM falls back to a slow tie-breaking algorithm (tieBreakOrder): comparing class names via reflection and invoking the native System.identityHashCode(), introducing substantial latency overhead.

4. Can a mutable object be safely used as a key in java.util.IdentityHashMap? What is the catch?

Answer: Yes, in IdentityHashMap a mutable object can be used without losing entries, but the semantics differ fundamentally:

  • IdentityHashMap completely ignores equals() and hashCode().
  • It checks key equality strictly via memory address reference identity (k1 == k2), and computes hash codes using native System.identityHashCode(k).
  • Because memory addresses do not change when internal fields are modified, mutations do not disrupt bucket placement.
  • The Catch: Two distinct instances with identical business data (e.g. two separate User(id=1) objects) are treated as completely different keys. This behavior is suitable for serialization graph caches, but unsuitable for standard business logic.

🎯 Interview Cheat Sheet

Summary: Immutable Keys in HashMap

  • Recommended Practice: Industry-standard; strongly recommended across all key-value data structures.
  • Core Requirement: Stable hashCode() $\to$ deterministic bucket indexing $\to$ zero orphaned entries.
  • Optimization: Lazy hashCode caching in a private field (as in String).
  • Composite Keys: Use Java 16+ record implementing Comparable.
  • Shallow Immutability Hazard: Mutable nested collections inside records break hash contracts unless defensively copied via List.copyOf().

Mutable Key vs. Immutable Key Comparison

Architectural Trait Immutable Key (String, Record) Mutable Key (JavaBean, ArrayList)
Hash Code Stability 🟢 100% Constant for lifetime 🔴 Mutates whenever fields change
Lookup Reliability 🟢 Always resolves correct bucket 🔴 Returns null after field mutation
Memory Leak Risk 🟢 Zero risk 🔴 High risk of orphaned entries
Lazy Hash Caching 🟢 Safe to cache in private field ❌ Impossible (Cache invalidation)

Red Flags to Avoid

  • ❌ “Using an ArrayList as a HashMap key is fine as long as there is only one thread.” (False; single-threaded mutations also alter the hash and corrupt bucket lookup).
  • ❌ “HashMap automatically shifts entries to new buckets if key fields change.” (False; HashMap has no mutation listeners).
  • ❌ “Marking a List field as final is sufficient to make it a safe map key.” (False; the list reference is final, but list contents can still mutate).