Autocoder

Java HashMap Internals Interview Questions

Last updated 2026-11-19

"How does HashMap work internally?" is probably the single most repeated Java interview question, and interviewers keep digging until you run out of detail. A complete answer covers the table, the hash function, index calculation, collision handling, treeification, resizing and the equals/hashCode contract.

This page walks through these in the order an interviewer typically probes them, using the OpenJDK implementation from Java 8 onwards. The wider API is covered on the Java collections page.

Default capacity16 buckets
Default load factor0.75, so resize after 12 entries
Treeify threshold8 nodes in a bucket and table size at least 64

The one-paragraph answer

HashMap keeps an array of buckets. put(key, value) computes hash(key), maps it to an index with (n - 1) & hash, and stores a node there. Nodes with the same index form a linked list, converted to a red-black tree when a bucket reaches 8 entries and the table has at least 64 slots. When the entry count exceeds capacity times load factor, the table doubles and entries are redistributed.

Java HashMap Internals Interview Questions: questions with worked answers

  1. 1

    Describe the internal structure of a HashMap.

    easy

    It holds a Node<K,V>[] table whose length is always a power of two. Each Node stores the key, value, the cached hash and a next pointer. The table is allocated lazily on the first put, with default length 16, a load factor of 0.75 and therefore a threshold of 12. Fields such as size, modCount and threshold support resizing and fail-fast iteration.

  2. 2

    How is the bucket index computed, and why does HashMap spread the hash?

    medium

    hash(key) is key.hashCode() XOR-ed with itself shifted right 16 bits, which mixes the high bits into the low bits. The index is (n - 1) & hash. Because n is a power of two, n - 1 is a mask of low bits, so only the low bits of the hash would matter without spreading, and keys whose hash codes differ only in the high bits (for example floats) would collide heavily.

    java
    int n = 16;
    int h1 = Integer.valueOf(1).hashCode();   // 1
    int h17 = Integer.valueOf(17).hashCode(); // 17
    System.out.println((n - 1) & h1);   // 1
    System.out.println((n - 1) & h17);  // 1  -> same bucket as key 1
  3. 3

    Why is the table size always a power of two?

    medium

    With a power-of-two length, (n - 1) & hash replaces a slower modulo and always gives a valid index. It also makes resizing cheap: after doubling, each node either stays at its old index or moves to oldIndex + oldCapacity, decided by a single extra bit of the hash. new HashMap<>(100) rounds the capacity up to 128 through tableSizeFor.

  4. 4

    Walk through put(key, value) step by step.

    medium

    1. If the table is null or empty, resize() allocates it. 2. Compute the index. If the bucket is empty, place a new node. 3. Otherwise compare the first node by hash and then == or equals; if it matches, replace the value. 4. If the bucket is a tree, insert into the tree. 5. Otherwise walk the list; replace on a match or append at the tail, and convert the bucket to a tree if the list length reaches the threshold of 8. 6. Increment size and resize if it exceeds the threshold. put returns the old value or null.

  5. 5

    How does get(key) work, and what is its complexity?

    medium

    It hashes the key, finds the bucket, checks the first node and then walks the list or tree comparing the cached hash first and then equals. Average cost is O(1). With a poor hashCode that sends many keys to one bucket the cost is O(n) in a list, and O(log n) since Java 8 once the bucket is treeified.

  6. 6

    What happens in a collision, and when is a bucket treeified or untreeified?

    hard

    Colliding keys are chained in a linked list. When a single bucket reaches 8 nodes (TREEIFY_THRESHOLD), the bucket becomes a red-black tree, but only if the table has at least 64 slots; otherwise HashMap resizes instead, since more buckets usually fixes the problem. When a resize or removal shrinks a tree bucket to 6 nodes or fewer (UNTREEIFY_THRESHOLD) it goes back to a list. The gap between 8 and 6 prevents flip-flopping.

  7. 7

    Show two different strings with the same hashCode and explain what a HashMap does with them.

    medium

    "Aa" and "BB" both have hashCode 2112, since 65*31+97 equals 66*31+66. They land in the same bucket, so the map compares the cached hash (equal), then calls equals (false) and keeps both nodes in the chain. Correctness is preserved by equals; only speed suffers.

    java
    Map<String,Integer> m = new HashMap<>();
    m.put("Aa", 1);
    m.put("BB", 2);
    System.out.println("Aa".hashCode() == "BB".hashCode()); // true
    System.out.println(m.get("Aa") + " " + m.get("BB"));     // 1 2
  8. 8

    What happens during resize?

    medium

    When size exceeds threshold, resize() allocates a table of twice the length and moves the nodes. Since Java 8, each bucket is split into a low list that keeps its index and a high list that goes to index + oldCap, preserving relative order within each. Rehashing is not recomputed from scratch; the bit (hash & oldCap) decides. Resizing is O(n), so presizing a map avoids repeated copies.

  9. 9

    How do you presize a HashMap to avoid resizing for 100 entries?

    medium

    You need capacity at least 100 / 0.75 = 133.3, so ask for 134 or more, which rounds up to a 256 table. A common mistake is new HashMap<>(100), which becomes 128 buckets with threshold 96, so the 97th insertion resizes. Java 19 added HashMap.newHashMap(100) that does the arithmetic for you.

    java
    Map<Integer,String> m = HashMap.newHashMap(100); // Java 19+
    // before 19: new HashMap<>((int) (100 / 0.75f) + 1)
  10. 10

    How are null keys handled?

    medium

    HashMap allows one null key. hash(null) returns 0, so it always sits in bucket 0, and lookups use == null instead of equals. Because get returns null both for a missing key and for a null value, use containsKey or getOrDefault when null values are possible.

  11. 11

    Why must keys be immutable, and what if hashCode is bad or missing?

    hard

    If a key field used in hashCode changes after insertion, the entry is looked up in the wrong bucket and becomes effectively lost. If equals is overridden without hashCode, equal keys hash differently and the map stores duplicates. If hashCode returns a constant, all entries share one bucket: in Java 8 and later a tree bucket gives O(log n) only if the key is Comparable, otherwise lookups degrade towards O(n).

  12. 12

    What is the iteration order of a HashMap? Predict this output.

    medium

    There is no guaranteed order, and it can change after a resize. Small Integer keys appear sorted only by accident, because their hash is their value and the buckets are visited in index order. Never rely on it; use LinkedHashMap for insertion order or TreeMap for sorted order.

    java
    Map<Integer,String> m = new HashMap<>();
    m.put(3, "c"); m.put(1, "a"); m.put(2, "b");
    System.out.println(m);   // {1=a, 2=b, 3=c} in practice
    m.put(17, "q");
    System.out.println(m);   // {1=a, 17=q, 2=b, 3=c}  (17 shares bucket 1)
  13. 13

    How do HashMap, Hashtable, synchronizedMap and ConcurrentHashMap differ?

    medium

    HashMap is unsynchronised and allows nulls. Hashtable is a legacy class with every method synchronised on the whole table and no nulls. Collections.synchronizedMap wraps a map with a single lock and still needs manual locking for iteration. ConcurrentHashMap allows concurrent reads and fine-grained writes and offers atomic methods such as compute, merge and putIfAbsent. See Java concurrency utilities.

  14. 14

    How does ConcurrentHashMap achieve thread safety in Java 8 and later?

    hard

    The old segment locking was removed. An insert into an empty bucket uses a compare-and-swap, and inserts into an occupied bucket synchronise on that bucket head node only, so different buckets update in parallel. Reads are mostly lock-free using volatile fields. Size is tracked with striped counters, and resizing is shared across threads that help transfer bins. Null keys and values are disallowed.

  15. 15

    Is HashMap safe under concurrent modification? What went wrong historically?

    hard

    No. In Java 7 a concurrent resize could link nodes into a cycle and make get spin forever on one CPU. Java 8 fixed the cycle by preserving order during the split, but concurrent puts can still lose updates, corrupt size and throw ConcurrentModificationException during iteration. Use ConcurrentHashMap.

  16. 16

    Implement an LRU cache with LinkedHashMap.

    medium

    LinkedHashMap with accessOrder true moves each accessed entry to the end, so the eldest entry is the least recently used. Override removeEldestEntry to evict once the size exceeds the limit. This is O(1) for get and put but not thread safe.

    java
    class LRU<K,V> extends LinkedHashMap<K,V> {
        private final int cap;
        LRU(int cap) { super(16, 0.75f, true); this.cap = cap; }
        @Override protected boolean removeEldestEntry(Map.Entry<K,V> e) {
            return size() > cap;
        }
    }
    LRU<Integer,String> c = new LRU<>(2);
    c.put(1, "a"); c.put(2, "b"); c.get(1); c.put(3, "c");
    System.out.println(c.keySet()); // [1, 3]
  17. 17

    How is HashSet related to HashMap?

    easy

    A HashSet is a thin wrapper around a HashMap. Each element becomes a key and the value is a shared dummy object named PRESENT. add returns true when the underlying put returns null, which is why HashSet inherits all the hashing and equals rules above.

Frequently asked questions

What is the default capacity and load factor of HashMap?

Capacity 16 and load factor 0.75, so it resizes when the 13th entry is added. The table is created on the first put.

Why 8 for treeification?

With a good hash function bucket sizes follow a Poisson distribution, and a bucket of 8 is extremely rare. The tree is a safeguard against bad hash codes and denial-of-service collisions, not a common path.

Does HashMap keep insertion order?

No. LinkedHashMap does. TreeMap keeps keys sorted.

Can two keys with the same hashCode both be stored?

Yes. They go into the same bucket and equals tells them apart.

Related guides

More in Programming Language Interview Questions by Language

See all in this section