فریم‌ورک Collections و درونیات HashMapCollections Framework & HashMap Internals

Every program you write eventually has to hold a pile of data somewhere: a list of users, a "id → name" table, a queue of pending jobs. Java ships a whole toolbox for this called the Collections Framework. Most people's problem isn't that they can't use the tools — it's that they don't know what happens behind the curtain of each one, and that's exactly where senior interviews trip people up. This lesson is that behind-the-curtain tour.

Part 0 — words you must feel first

Before the details, let's build the four words that keep recurring, from the ground up. Feel these and the rest is easy.

That idea has a formal name: program to the interface. Declare your fields, parameters, and return types as List / Set / Map, and let only the new expression name the concrete class.

For now, know bucket and hash at this level: hashing means turning an object into an integer, and a bucket is a slot in an array where we place that object according to its number. We'll fully unpack the details in the HashMap section.

The Collections family layout

The Collections Framework is a set of interfaces (Collection, List, Set, Queue, Deque, Map) plus concrete implementations, all under the java.util package. Now one point that confuses many people:

Here's the whole family tree:

            Iterable
               │
          Collection ───────────────┐
          /    |     \               │
       List   Set    Queue ── Deque  │   Map  (separate hierarchy)
        │      │        │       │        │
   ArrayList  HashSet  PriorityQ ArrayDeque  HashMap
   LinkedList LinkedHashSet      LinkedList  LinkedHashMap
   Vector     TreeSet(NavigableSet)          TreeMap(NavigableMap)
   CopyOnWriteArrayList                       ConcurrentHashMap
                                              EnumMap / WeakHashMap / IdentityHashMap

Each interface, in one feel-it sentence:

• List — a numbered row: ordered by index, duplicates allowed, and you can say "give me element #5". Implementations: ArrayList, LinkedList, Vector, CopyOnWriteArrayList.
• Set — a bag that refuses duplicates (duplicate-ness judged by equals). HashSet (unordered), LinkedHashSet (insertion order), TreeSet (sorted, a NavigableSet).
• Queue — a bakery line, usually "first-in first-out" (FIFO); methods offer/poll/peek. PriorityQueue (kept ordered by a heap), ArrayDeque, LinkedList.
• Deque — a double-ended queue (add/remove at both ends); the modern replacement for the old Stack. ArrayDeque is the recommended stack and queue.
• Map — the key→value phone book. HashMap, LinkedHashMap, TreeMap, ConcurrentHashMap, EnumMap, WeakHashMap, IdentityHashMap.

The Big-O cheat sheet

Keep this table like a treasure map; half of collections questions come straight out of these cells.

Let me unpack "amortized", because it matters.

ArrayList vs LinkedList — in detail

ArrayList internally wraps a plain Object[]. Appends are amortized O(1) because when it fills, capacity grows by ~1.5x (newCap = old + (old >> 1)). Random access is a single array index — instant. Removing from the middle shifts every following element back one slot (via System.arraycopy), which is O(n) — but extremely fast per element, because it's one contiguous memory move.

LinkedList is a doubly-linked list of Node objects. Each node is a separate heap allocation with two pointers (to previous and next) plus the object-header overhead.

LinkedList implements both List and Deque. But for stacks and queues, the right choice is something else:

// Prefer ArrayDeque over Stack (which is synchronized and extends Vector)
Deque<Integer> stack = new ArrayDeque<>();
stack.push(1); stack.push(2);      // 2 is on top
int top = stack.pop();              // 2

Deque<Integer> queue = new ArrayDeque<>();
queue.offer(1); queue.offer(2);
int head = queue.poll();            // 1 (FIFO)

HashMap internals — the heart of the interview

Now the most important section. If you deeply learn just one data structure for a senior interview, make it HashMap.

So internally, a HashMap is an array of buckets: Node<K,V>[] table. Each bucket is in one of three states: empty (null), a short linked list of nodes (when several keys landed in one bucket), or — once a bucket gets very crowded — a red-black tree, which is a self-balancing binary search tree.

The key constants

These few numbers are hard-coded into HashMap and worth memorizing:

Hashing and index computation

The subtle bit: HashMap does not use key.hashCode() directly as the bucket number. It first "stirs" the hash a little to improve its quality:

static final int hash(Object key) {
    int h;
    // XOR the top 16 bits into the bottom 16 bits
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

Then the bucket index is computed as (n - 1) & hash, where n is the (power-of-two) table length. Why is that XOR step needed?

The put walk-through, step by step

Let's see exactly what happens when you call map.put(key, value):

1. Compute hash(key), then derive index i = (n-1) & hash.
2. If table[i] is empty, drop the new node there. Done.
3. Otherwise walk the bin. If you find a node with an equal key, overwrite its value. "Equal" means: hash equal and (key == k || key.equals(k)).
4. If not found, append the node to the bin. Now if this bin has ≥ TREEIFY_THRESHOLD (8) nodes and table length ≥ 64, treeify the bin into a red-black tree. But if table length < 64, instead of treeifying, resize the whole table (which spreads the collisions out).
5. Increment size; if now size > threshold (i.e. capacity × loadFactor), resize.

Treeification — why exactly 8?

We said a crowded bin turns into a tree at the threshold of 8. But why 8?

So why do we care about treeifying at all? Because treeify converts that unlucky bin from an O(n) linear scan to O(log n), and this caps hash-collision denial-of-service (DoS) attacks: an attack where the adversary deliberately sends thousands of keys with the same hash so they all pile into one bucket and slow the server to a crawl. The tree bounds that damage. Order inside the tree is first by hash, then by Comparable if the keys implement it, else by an identity-based tiebreak.

Resize — and the beauty of powers of two

When size exceeds the threshold, capacity doubles. This is where "capacity is always a power of two" turns to gold:

oldCap = 16 (10000b). A key with hash whose bit-4 (value 16) is:
   0  -> stays at index j
   1  -> moves to index j + 16

Now a famous piece of history, asked in almost every senior interview:

Fail-fast iterators

Suppose you're looping over a list and, mid-loop, you change the list itself. Java catches this early:

Every structural modification (an add/remove that changes size, or a treeify) bumps an internal modCount. When an iterator is created it snapshots modCount into expectedModCount; on each next() it compares the two and throws ConcurrentModificationException if they differ.

Iterator<String> it = list.iterator();
while (it.hasNext()) {
    if (shouldRemove(it.next())) it.remove();  // safe
}
// list.remove(x) inside a for-each -> ConcurrentModificationException

Why keys must be immutable

This is one of the most frequent production bugs, so feel it well:

Precisely: when you put, the map decides which bucket a key goes to based on its hash at that moment. If you later mutate a field that participates in hashCode/equals, the key now hashes to a different bucket but still physically sits in the old one. get(sameKey) computes the new index, looks in the new bucket, and finds nothing.

// Broken: mutable key
Map<Point, String> m = new HashMap<>();
Point p = new Point(1, 1);
m.put(p, "a");
p.setX(99);                 // mutates fields used by hashCode/equals
m.get(p);                   // null! entry is orphaned in the old bucket

LinkedHashMap and LRU caches

LinkedHashMap extends HashMap and additionally threads every entry onto a doubly-linked list. The result: predictable insertion-order iteration (unlike HashMap, whose order is unspecified).

But its killer feature is something else: access order.

By overriding removeEldestEntry, you can build a bounded LRU cache in a handful of lines:

class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;
    LRUCache(int capacity) {
        super(16, 0.75f, true);      // true = access-order
        this.capacity = capacity;
    }
    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;    // evict LRU when over capacity
    }
}

The constructor's third argument (true) is what turns on access order; and every time a new element is put, Java calls removeEldestEntry, and if it returns true, the head (the least-recently-used) is evicted.

TreeMap / NavigableMap

So far everything revolved around hashing. TreeMap plays a different game: a red-black tree (a kind of self-balancing binary search tree). All its operations are O(log n) and — the crucial difference — iteration happens in sorted key order: either by the key's natural ordering (Comparable) or a Comparator you supply.

That very ability gives you a set of "navigation" methods, collectively called NavigableMap: floorKey, ceilingKey, higherKey, lowerKey, firstKey, lastKey, headMap, tailMap, subMap.

NavigableMap<Integer, String> tm = new TreeMap<>();
tm.put(10, "a"); tm.put(20, "b"); tm.put(30, "c");
tm.floorKey(25);     // 20  (greatest key <= 25)
tm.ceilingKey(25);   // 30  (least key >= 25)
tm.subMap(10, true, 25, true);   // {10=a, 20=b}

ConcurrentHashMap internals (Java 8+)

When multiple threads want to read and write one shared map at once, HashMap is dangerous and the old Hashtable is slow. The right answer is ConcurrentHashMap — but its design changed in Java 8, and that very "change" is a classic interview question.

The modern design works like this:

• Empty bin: installing the first node uses a lock-free CAS (compareAndSwapObject). In the common, uncontended case, no lock is taken at all.
• Non-empty bin: the thread synchronizeds only on the bin's head node — so writers to different buckets never block each other. Lock granularity is one bucket, not the whole map.
• Bins still treeify at 8 (with the same table ≥64 rule), exactly like HashMap.
• Reads never lock. get traverses volatile nodes and always sees a consistent (though possibly slightly stale) view.
• During resize, threads help each other: a special ForwardingNode marks bins that have migrated, and multiple threads cooperatively transfer ranges of the table (transferIndex, stride).

size() has an interesting story too:

The right way to count concurrently goes through the map's own atomic operations, not get-then-put:

ConcurrentHashMap<String, Integer> counts = new ConcurrentHashMap<>();
// atomic, lock-striped read-modify-write — the correct way to count concurrently
counts.merge("apples", 1, Integer::sum);
counts.compute("apples", (k, v) -> (v == null) ? 1 : v + 1);
counts.computeIfAbsent("bananas", k -> 0);
// WRONG under concurrency: get-then-put is a lost-update race
// counts.put("x", counts.getOrDefault("x", 0) + 1);

The specialist maps

Three special maps, each built for one specific job:

• EnumMap — when keys are the constants of an enum. Internally it's just a plain Object[] indexed by ordinal() (the enum constant's ordinal number), so it's extremely compact and fast — direct array access, no hashing at all. It iterates in enum declaration order. Always prefer it over HashMap<MyEnum, V>.
• WeakHashMap — holds its keys via weak references.

• IdentityHashMap — uses == and System.identityHashCode, not equals/hashCode. That is, it cares about "being the same object", not "being equal". Internally it uses open addressing (linear probing) with a single flat array of alternating keys and values, not chaining. Uses: topology-preserving graph traversal, serializers, and deep-copy "visited" sets — places where you need reference identity, not logical equality. Here, new String("a") and new String("a") are two entirely distinct keys.

Common pitfalls & gotchas

These are the places where seemingly-correct code breaks silently:

Best practices

Interview Questions

Now let's practice everything you read as real interview questions. Try each yourself first, then look.

List<Integer> list = new ArrayList<>(List.of(1, 2, 3, 4));
for (Integer x : list) {
    if (x == 2) list.remove(x);   // remove(Object)
}
System.out.println(list);

Map<String, Integer> m = new HashMap<>();
m.put("a", 1);
System.out.println(m.get("a") == m.get("a"));

Senior notes & advanced edge cases

You already understand the internals. Now let's get into the things books don't write down but that burn people in production and, in a senior interview, separate someone who "knows" from someone who really knows. None of this repeats the material above — it's all the remaining gap.

Sizing a HashMap: the initial-capacity myth

Many people believe that if they know 1000 entries are coming, new HashMap<>(1000) prevents all resizes. That is wrong, and the culprit is the load factor.

The constructor argument is capacity, not expected number of entries. HashMap rounds it up to the next power of two (tableSizeFor), so 1000 becomes capacity 1024. But a resize fires when size > capacity × 0.75 — i.e. the table doubles as you insert the 769th element. So 1000 entries still incur one resize, the very thing you tried to avoid.

// want 1000 entries with no resize?
int n = 1000;
Map<K,V> m = new HashMap<>((int) Math.ceil(n / 0.75));   // 1334 -> capacity 2048

Map<K,V> m = HashMap.newHashMap(1000);   // JDK 19+, guaranteed no-resize

computeIfAbsent and merge traps

This family of atomic methods is a jewel of modern coding — but it has two deadly traps that are almost always asked in a senior interview.

Map<Integer,Long> memo = new HashMap<>();
Function<Integer,Long> fib = new Function<>() {
    public Long apply(Integer n) {
        return n < 2 ? n
            : memo.computeIfAbsent(n-1, this) + memo.computeIfAbsent(n-2, this);
    }               // ← throws CME on Java 9+
};

Comparator correctness: two bugs that go silent

Sorting and TreeMap ride on Comparators, and two classic mistakes lurk here.

Floating-point keys: NaN and negative zero

Here equals and == deliberately behave opposite to each other, creating two traps:

EnumSet: the forgotten twin of EnumMap

If you have a set of an enum's constants, HashSet<MyEnum> is almost always wrong. EnumSet is internally a bit vector: each constant's ordinal() becomes one bit in a long. Up to 64 constants the entire set is a single long (RegularEnumSet); beyond that, a long[] (JumboEnumSet). Result: add/contains/removeAll are literally a few CPU bit ops, memory is negligible, and iteration is in enum declaration order.

EnumSet<Day> weekend = EnumSet.of(Day.SAT, Day.SUN);    // one long
EnumSet<Day> workdays = EnumSet.complementOf(weekend);  // bitwise complement, instant

The concurrent-collection zoo (beyond ConcurrentHashMap)

ConcurrentHashMap isn't the only player on the concurrency stage. A senior should know the right tool for each shape of concurrency.

Keep this decision tree — caption: "which concurrent collection for which job".

flowchart TD
  Start[Need thread-safe collection?] --> Kind{What shape?}
  Kind -->|Key to value| Sorted{Need sorted keys?}
  Sorted -->|No| CHM[ConcurrentHashMap]
  Sorted -->|Yes| CSLM[ConcurrentSkipListMap]
  Kind -->|List, read-heavy| COW[CopyOnWriteArrayList]
  Kind -->|Producer / consumer| BQ[BlockingQueue family]
  Kind -->|Set| Set[ConcurrentHashMap.newKeySet]

Map<K,V> m = Collections.synchronizedMap(new HashMap<>());
synchronized (m) {                 // mandatory while iterating
    for (var e : m.entrySet()) { ... }
}

Memory footprint at scale

Layers of immutability: view vs copy vs truly immutable

Hard senior interview questions

Source: the official Java documentation and Javadocs (java.util.HashMap, ConcurrentHashMap, TreeMap, LinkedHashMap).