Java collections & generics

How HashMap put and get actually work

A HashMap is an array of buckets. To store a key it computes the key's hashCode(), mixes the bits, masks that down to a bucket index, and puts the entry there. Two keys that land in the same bucket share it as a short linked list. Lookup repeats the steps: hash to a bucket, then walk that bucket calling equals until it finds a match or runs out.

Both steps matter, and the order is the whole game. The bucket comes from hashCode. The match inside the bucket comes from equals. If hashCode sends you to the wrong bucket, equals never even runs.

The equals/hashCode contract

That is why this breaks:

class Point {
  final int x, y;
  Point(int x, int y) { this.x = x; this.y = y; }
  @Override public boolean equals(Object o) { /* compares x and y */ }
  // hashCode NOT overridden
}
Map<Point, String> m = new HashMap<>();
m.put(new Point(1, 2), "A");
m.get(new Point(1, 2)); // null

Wrong "The two Points are equal, so get returns A." The lookup Point is a different instance, and without an overridden hashCode it inherits Object's identity hash. Different hash, different bucket, and the stored entry is never reached. The rule: override hashCode whenever you override equals, computed from the same fields. Equal objects must produce equal hash codes. A HashSet is a HashMap under the hood, so the same bug makes it store visual duplicates.

Keep key fields effectively immutable too. Mutate a field that feeds hashCode after the key is in the map and the entry becomes unreachable, still there, just in the bucket for its old hash.

ArrayList vs LinkedList in practice

ArrayList is a backing array: get(i) is O(1), append is amortized O(1), inserting in the middle shifts the tail. LinkedList is a doubly linked list: cheap to splice once you hold a node, but reaching index i walks i nodes.

The big-O table makes LinkedList look good for inserts. Reality does not. The array's elements sit contiguously in memory, so iteration and indexed reads stream through CPU cache. Every LinkedList node is a separate heap object, so a traversal chases pointers and misses cache constantly. Default to ArrayList. Reach for a linked structure only for real head/tail deque work, where ArrayDeque usually beats LinkedList anyway.

One more everyday trap: removing from a list while iterating it with a for-each loop throws ConcurrentModificationException. Use Iterator.remove() or list.removeIf(...).

HashMap internals, the parts interviewers push on

Default capacity is 16, load factor 0.75. Capacity is always a power of two, so the bucket index is hash & (n - 1) instead of a modulo. That mask only keeps the low bits, so a hashCode with all its entropy up high would collide constantly. HashMap defends against that by spreading: h = key.hashCode(); h ^ (h >>> 16), folding the high 16 bits into the low ones before masking.

When size exceeds capacity * 0.75 the table resizes: double the buckets and redistribute. Because capacity doubles, each entry either stays at index i or moves to i + oldCapacity, decided by one bit, so Java 8 splits a bucket into a low and a high list without recomputing hashes.

Treeification answers hash-collision denial of service. A bucket that grows to 8 entries (TREEIFY_THRESHOLD) converts from a linked list to a red-black tree, capping a pathological bucket at O(log n) instead of O(n). The gate people forget: it only trees if table capacity is at least 64 (MIN_TREEIFY_CAPACITY); below that it resizes instead. A tree reverts to a list at 6 (UNTREEIFY_THRESHOLD). The 8/6 gap is hysteresis so a bucket hovering at the boundary does not flip on every put and remove.

The equals/hashCode contract, stated fully

Equal objects must have equal hash codes. The converse is not required: unequal objects may share a code. Wrong "distinct objects must have distinct hashCodes." That demands a perfect hash, impossible for an unbounded key space. equals must also be reflexive, symmetric, transitive, and consistent. Symmetry is where inheritance bites: a ColorPoint that considers itself equal to a plain Point breaks a.equals(b) == b.equals(a). Prefer composition, or compare getClass() rather than instanceof, when subclasses add state.

Fail-fast is a bug detector, not a lock

ArrayList and LinkedList keep a modCount; an iterator snapshots it and throws ConcurrentModificationException when a structural change makes them disagree. modCount is not volatile, so across threads a missed update can slip through and the check may never fire. Treat fail-fast as a single-thread debugging aid; for concurrent iteration use CopyOnWriteArrayList or a concurrent collection that iterates over a snapshot.

Generics erase, and what that forbids

Generics are compile-time only. The compiler checks types, inserts casts, then erases each parameter to its bound (Object if unbounded), so List<String> and List<Integer> share one runtime Class. The consequences fall out directly: no new T[n] (an array needs a reified component type for its ArrayStoreException check, and T has none), no obj instanceof List<String>, no T.class, no generic Throwable subtypes, no type parameter in a static field. You can still write new ArrayList<T>() or cast (T[]) new Object[n]; the array component type is the blocker, not generics as such.

Wildcards follow from variance. List<? extends Number> produces: read a Number out, but you cannot add, since the compiler cannot prove the element type. List<? super Integer> consumes: add an Integer, but reads come out as Object. Producer Extends, Consumer Super. For whole-map safety across threads, Collections.synchronizedMap wraps every method in one lock and still forces manual synchronization while iterating; ConcurrentHashMap is the scalable alternative; how it locks per bin is java-concurrency territory.