| Default initial capacity | 16 buckets (always a power of two) |
| Default load factor | 0.75 — balances space usage against collision rate |
| Resize trigger | size > capacity × loadFactor → capacity doubles, table rehashed |
| Bucket index formula | (capacity - 1) & hash — bitwise AND instead of modulo |
| Treeification (Java 8+) | bucket ≥ 8 entries AND table capacity ≥ 64 → red-black tree |
| Untreeify threshold | tree shrinks back to a linked list at 6 entries during a resize split |
| hash() spreading | h ^ (h >>> 16) — mixes high bits into low bits before masking |
| Null keys | HashMap allows one null key; Hashtable/ConcurrentHashMap allow none |
Hashing & HashMap Internals Interview Questions & Answers
Q1. What is a hash function and what properties should a good one have?
A: A hash function maps an input key of arbitrary size to a fixed-size output value, ideally spreading outputs uniformly across the possible range to minimize collisions. A good hash function is deterministic (the same input always produces the same output), fast to compute, and exhibits an avalanche effect where small changes to the input cause large, unpredictable changes to the output. In Java, this behavior is implemented per-class through the hashCode() method, which must stay consistent with equals().
Q2. Why do hash tables provide average O(1) time for insert, lookup, and delete?
A: A hash function converts a key into an array index in O(1) time, allowing the table to jump directly to the relevant bucket instead of scanning the whole structure. As long as the hash function distributes keys evenly and the load factor stays low, each bucket holds only a small, roughly constant number of entries, so work within a bucket is also effectively O(1). This trades away the ordering guarantees of a balanced tree (O(log n)) for O(1) average performance, at the cost of worst-case O(n) behavior when collisions pile up.
Q3. What is a hash collision?
A: A hash collision occurs when two distinct keys produce the same hash code, or more specifically map to the same bucket index once the hash is compressed to the table's size. Collisions are mathematically unavoidable once the number of possible keys exceeds the number of buckets, by the pigeonhole principle, so every practical hash table implementation needs a collision-resolution strategy such as chaining or open addressing.
Q4. What is the difference between a hash code and a bucket index?
A: A hash code is the raw value produced by a key's hashCode() method — a full 32-bit int in Java, which can be negative and can span the entire int range. The bucket index is that hash code compressed into the valid range of the table's backing array, typically via modulo or a bitmask. In java.util.HashMap, the bucket index is computed as (n - 1) & hash, where n is the table capacity, an efficient equivalent of hash % n that only works because n is always a power of two.
Q5. Why does HashMap always use capacities that are powers of two?
A: A power-of-two capacity lets HashMap replace the comparatively slow modulo operation with a bitwise AND, (capacity - 1) & hash, which is much cheaper at the CPU level than integer division. It also makes resizing efficient: because capacity always doubles, each entry's new bucket index during a rehash is either its old index or its old index plus the old capacity, so entries in one old bucket split cleanly into two new buckets without recomputing every hash from scratch.
// Simplified index computation used internally by HashMap
static int indexFor(int hash, int capacity) {
return (capacity - 1) & hash; // capacity is always a power of two
}
// capacity=16 (0b10000) -> mask=15 (0b01111)
// hash=37 (0b100101) & 15 = 0b0101 = 5 -> bucket 5Q6. What does it mean for a hash function to have good uniformity?
A: A uniform hash function spreads keys evenly across all buckets so that no bucket receives disproportionately more entries than others. Poor uniformity concentrates entries into a few buckets, degrading those buckets' lookup time toward O(n) even though the table overall has plenty of spare capacity. Uniformity depends both on the quality of each key type's hashCode() implementation and on how the table compresses hash codes into bucket indices.
Q7. What is hash flooding, and why is it a security concern?
A: Hash flooding is a denial-of-service technique where an attacker deliberately supplies many keys that hash into the same bucket, degrading a hash table's average O(1) operations toward O(n) per operation and effectively causing near-quadratic processing time for attacker-controlled input, such as HTTP form fields or JSON object keys. Java mitigates this in HashMap by treeifying overloaded buckets into red-black trees, capping worst-case lookups at O(log n) instead of O(n); some other language runtimes additionally randomize their hash seed per process to make bucket collisions unpredictable to an attacker.
Q8. What is the load factor of a hash table, and how does it affect performance?
A: The load factor is the ratio of stored entries to the number of buckets (size / capacity), and it controls when the table resizes. A low load factor wastes memory on mostly-empty buckets but keeps chains short and lookups fast; a high load factor packs the table tightly, saving memory but lengthening chains and slowing operations. Java's HashMap defaults to 0.75 as a measured compromise between space overhead and time performance for typical workloads.
Q9. What is a perfect hash function?
A: A perfect hash function maps a known, fixed set of keys to distinct slots with zero collisions, typically constructed offline once the full key set is known in advance (e.g., for keywords in a compiler's lexer or a fixed configuration lookup). It is impractical for general-purpose, dynamically changing key sets like those in a typical HashMap, where new keys are inserted at runtime and the hash function must work well for any input, not just a predetermined list.
Q10. How does Object's default hashCode() implementation work if a class doesn't override it?
A: The default Object.hashCode() typically derives from the object's identity — historically related to its memory address, though the JVM is free to implement it any way that stays consistent for a given object's lifetime (e.g., HotSpot uses one of several strategies, including a thread-local xorshift PRNG value cached in the object header). This "identity hash code" means two different objects with identical field values will almost always produce different hash codes unless the class overrides hashCode() to be value-based.
Q11. How does Java's built-in String.hashCode() work?
A: String.hashCode() computes s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1], a polynomial hash using 31 as the multiplier. The constant 31 was chosen because it's an odd prime, which helps avalanche bit patterns, and because 31 * i can be optimized by the JIT into (i << 5) - i, a cheap shift-and-subtract instead of a general multiply. Java caches the computed hash in a private field after first use, since String is immutable and the hash never needs recomputation.
// Equivalent to String.hashCode()
int hashCode(String s) {
int h = 0;
for (int i = 0; i < s.length(); i++) {
h = 31 * h + s.charAt(i);
}
return h;
}Q12. What is HashMap's internal hash() spreading function, and why does it exist?
A: Before computing a bucket index, HashMap runs the key's hash code through static int hash(Object key) { int h; return key == null ? 0 : (h = key.hashCode()) ^ (h >>> 16); }. This XORs the high 16 bits into the low 16 bits, because bucket indexing only uses the low bits of the hash (via (capacity - 1) & hash), and many hashCode implementations vary mostly in their high bits while their low bits stay similar across keys. Spreading the high bits down improves distribution across buckets, especially for smaller table capacities, without materially slowing down the hash computation.
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}Q13. What is separate chaining as a collision resolution strategy?
A: Separate chaining resolves collisions by letting each bucket hold a collection — typically a linked list, and in Java 8+ HashMap, a red-black tree once the list grows large — of all entries that hash to that index. On a collision, the new entry is simply appended to the existing bucket's list rather than displacing anything. Lookup must then traverse the bucket's list/tree comparing keys with equals() until a match is found or the bucket is exhausted.
Q14. What is open addressing as a collision resolution strategy?
A: Open addressing resolves collisions by probing for an alternate empty slot within the same backing array when the initially computed slot is already occupied, rather than growing a list at that slot. All entries live directly inside the array itself (no auxiliary structure per bucket), which improves cache locality but means the table can never hold more entries than its capacity and typically needs a lower load factor to stay performant.
Q15. What is linear probing?
A: Linear probing is the simplest open-addressing scheme: on a collision at index i, it checks i+1, then i+2, and so on (wrapping around) until an empty slot is found. It has excellent cache locality since probes touch adjacent memory, but it is prone to primary clustering, where consecutive occupied slots merge into long runs that make future insertions and lookups progressively slower.
int insertLinearProbe(int[] table, int key) {
int idx = key % table.length;
int start = idx;
while (table[idx] != EMPTY) {
idx = (idx + 1) % table.length;
if (idx == start) throw new IllegalStateException("table full");
}
table[idx] = key;
return idx;
}Q16. What is quadratic probing?
A: Quadratic probing resolves a collision at index i by checking i + 1², i + 2², i + 3², and so on (mod capacity) instead of linear steps. The growing step size spreads out probes faster than linear probing, reducing primary clustering, but it introduces secondary clustering, where keys that collide at the same initial index follow the identical probe sequence, and it can fail to find an empty slot even when one exists unless the table size and probing constants are chosen carefully (e.g., prime capacity).
Q17. What is double hashing?
A: Double hashing uses a second, independent hash function to determine the probe step size: on a collision at h1(key), subsequent probes visit (h1(key) + i * h2(key)) mod capacity for i = 1, 2, 3, .... Because the step size itself depends on the key, two different keys that collide initially are unlikely to follow the same probe sequence, which largely eliminates secondary clustering and gives probing behavior close to true random probing.
Q18. What is the difference between primary clustering and secondary clustering?
A: Primary clustering (seen in linear probing) happens when several different initial hash indices funnel into the same growing run of consecutive occupied slots, because any key landing anywhere within an existing cluster extends it. Secondary clustering (seen in quadratic probing) happens when keys that collide at the exact same initial index follow the identical subsequent probe sequence, clustering along that one path even though they don't create the broad contiguous runs primary clustering does. Double hashing avoids both by making the probe sequence itself key-dependent.
Q19. Why must open addressing use a lower load factor than chaining?
A: In open addressing, every entry lives inside the fixed-size array, so the table cannot exceed a load factor of 1.0, and in practice performance degrades sharply well before that (probe sequences lengthen dramatically as the table nears full). Chaining tolerates a load factor above 1.0 gracefully, since buckets can hold arbitrarily many entries in a list; Java's HashMap resizes at 0.75 partly because chaining degrades far more gently than open addressing would at the same fill ratio.
Q20. Why is deletion harder in open addressing than in chaining, and how is it solved?
A: Simply clearing a slot to "empty" after deletion would break subsequent lookups, because probing relies on scanning until it hits an empty slot — an empty hole in the middle of a probe chain would incorrectly signal "not found" for keys that were probed past it. The standard fix is a tombstone: mark the deleted slot as a special "deleted" state that probing treats as occupied for search purposes (keep scanning past it) but as available for new insertions, sometimes with periodic table rebuilds to purge accumulated tombstones and prevent unbounded probe-sequence growth.
enum SlotState { EMPTY, OCCUPIED, DELETED }
boolean contains(Object[] table, SlotState[] state, int key) {
int idx = key.hashCode() % table.length;
int start = idx;
while (state[idx] != SlotState.EMPTY) {
if (state[idx] == SlotState.OCCUPIED && table[idx].equals(key)) return true;
idx = (idx + 1) % table.length;
if (idx == start) break;
}
return false;
}Q21. What is Robin Hood hashing?
A: Robin Hood hashing is an open-addressing variant (usually with linear probing) where, during insertion, an entry that has already probed further from its ideal slot than the entry currently occupying a candidate slot "steals" that slot, displacing the richer (shorter-probe-distance) entry to continue probing instead. This equalizes probe distances across all entries — no single key ends up with a dramatically longer lookup path than others — which tightens the variance of worst-case lookup time compared to plain linear probing.
Q22. What is cuckoo hashing?
A: Cuckoo hashing uses two (or more) independent hash functions and two backing tables (or two candidate slots per table); a key can live in only one of its two possible slots. On insertion, if a key's slot is occupied, it evicts the current occupant, which then relocates to its own alternate slot, potentially triggering a cascade of evictions. This guarantees O(1) worst-case lookup (check exactly two slots) at the cost of occasionally expensive insertions and the need to rehash/rebuild if a cycle of evictions never terminates.
Q23. Which collision-resolution strategy does java.util.HashMap use, and why chaining over open addressing?
A: HashMap uses separate chaining, where each bucket holds a linked list of nodes (upgraded to a red-black tree when a bucket grows large in a sufficiently large table). Chaining was chosen because it degrades gracefully under high load or poor hash distributions — buckets simply grow longer rather than the whole table failing to find an empty slot — and because Java 8's treeification bounds worst-case bucket lookup at O(log n), a guarantee that's much harder to retrofit onto open addressing.
Q24. Which collision resolution strategy does java.util.Hashtable use?
A: Like HashMap, the legacy Hashtable class also uses separate chaining with linked lists per bucket. It predates HashMap (Java 1.0) and differs mainly in being fully synchronized on every method (making it thread-safe but slow under contention) and in disallowing null keys and null values, unlike HashMap which permits one null key and any number of null values.
Q25. What are the practical trade-offs between chaining and open addressing?
A: Chaining handles arbitrarily high load factors and simplifies deletion (just unlink the node), but each entry carries pointer/node overhead and traversing a chain means chasing pointers across scattered memory, hurting CPU cache performance. Open addressing keeps all data packed in one contiguous array with excellent cache locality and no per-node allocation overhead, but it requires careful load-factor management, tombstone bookkeeping for deletes, and its performance can cliff sharply as the table fills up.
Q26. What actually happens inside HashMap when many keys collide into the same bucket?
A: Initially, the colliding entries form a simple singly linked list (Node<K,V> objects) hanging off that bucket, and lookups within it are O(k) where k is the chain length. If that chain reaches 8 entries and the overall table capacity is at least 64, HashMap converts (treeifies) the bucket into a self-balancing red-black tree of TreeNode<K,V> objects, bounding the worst case for that bucket at O(log k) instead of O(k) — a safeguard originally added to blunt hash-flooding attacks and pathological hash distributions.
Q27. What is the hashCode/equals contract in Java, precisely?
A: The contract, defined on Object, states: (1) hashCode() must return the same value consistently within a single execution as long as no fields used in equals() change; (2) if a.equals(b) is true, then a.hashCode() == b.hashCode() must also be true; (3) it is NOT required that unequal objects have different hash codes, though good hash functions make this likely. Violating rule 2 is the classic bug that silently breaks HashMap, HashSet, and any hash-based collection.
Q28. Why must equal objects have equal hash codes, but not the reverse?
A: Hash-based collections use hashCode() to locate the bucket a key belongs in and equals() only to disambiguate between keys within that same bucket. If two equal objects had different hash codes, they could land in different buckets, so a lookup using one "equal" instance would never find an entry stored under the other — breaking get(), contains(), and set membership entirely. The reverse isn't required because collisions between unequal objects are expected and handled by chaining/probing plus the final equals() check; hash codes are a fast filter, not a definitive answer.
Q29. What breaks if you override equals() without overriding hashCode()?
A: Without a matching hashCode() override, the inherited identity-based hash is used, so two objects that are .equals()-equal will almost certainly land in different buckets. A HashMap.put() followed by an immediate get() with an equal-but-different-instance key can then return null, and a HashSet.add() of a logically duplicate object will silently succeed, inserting a duplicate the set was supposed to reject.
class Point {
int x, y;
Point(int x, int y) { this.x = x; this.y = y; }
@Override public boolean equals(Object o) {
if (!(o instanceof Point p)) return false;
return x == p.x && y == p.y;
}
// BUG: no hashCode() override -> identity hash used
}
Map<Point, String> map = new HashMap<>();
map.put(new Point(1, 2), "origin-ish");
map.get(new Point(1, 2)); // returns null! different instance, different bucketQ30. What are the consequences of a hashCode() implementation that isn't consistent across calls?
A: If hashCode() returns different values across calls for the same logical object (e.g., it depends on the current time, an uninitialized field, or a mutable field that changed), an object inserted into a HashMap or HashSet can become permanently unreachable — a later call computes a different bucket index than the one used at insertion time, so get()/contains() search the wrong bucket and silently fail. The entry isn't lost from the table itself, but it's effectively orphaned and will also leak memory since it can never be found and removed through normal API calls.
Q31. Why are mutable objects dangerous as HashMap keys?
A: A key's bucket is determined by its hash code at insertion time; if a field used in hashCode() changes after insertion, the key's current hash code no longer matches the bucket it actually lives in. Subsequent get() calls compute the new (correct) hash but search the wrong bucket, so the entry appears to vanish even though it's still physically present in the map — and it can create a permanent memory leak, since neither get() nor remove() can locate it anymore.
class MutableKey {
int value;
MutableKey(int value) { this.value = value; }
@Override public int hashCode() { return value; }
@Override public boolean equals(Object o) {
return o instanceof MutableKey k && k.value == value;
}
}
Map<MutableKey, String> map = new HashMap<>();
MutableKey key = new MutableKey(1);
map.put(key, "hello");
key.value = 2; // mutate after insertion -> hash code changes
map.get(new MutableKey(1)); // null - wrong bucket now
map.get(key); // also null - same object, but searches bucket for value=2Q32. What is a good custom hashCode() implementation pattern in Java?
A: Combine the hash codes of all fields used in equals() using a running accumulator multiplied by a small odd prime (traditionally 31), which is exactly what IDEs generate and what Objects.hash() does under the hood. Every field included in equals() must be included in hashCode(), and no field excluded from equals() should be included in hashCode(), or the contract can be violated in subtle ways.
class Employee {
final String id;
final String department;
Employee(String id, String department) {
this.id = id; this.department = department;
}
@Override public int hashCode() {
return Objects.hash(id, department);
}
@Override public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof Employee e)) return false;
return Objects.equals(id, e.id) && Objects.equals(department, e.department);
}
}Q33. Why should HashMap keys generally be immutable?
A: Immutable keys such as String, boxed numeric wrappers like Integer, and records guarantee that a key's hash code never changes after insertion, which is exactly the invariant HashMap's bucket placement relies on. Immutability also makes keys inherently thread-safe to share and compare, and it lets HashMap (in the case of String) safely cache the computed hash code once rather than recomputing it, since the value backing it can never change.
Q34. What do the Objects.hashCode() and Objects.hash() utility methods do?
A: Objects.hashCode(obj) is a null-safe wrapper that returns 0 for a null argument and obj.hashCode() otherwise, avoiding a manual null check. Objects.hash(Object... values) combines multiple values into a single hash code by internally calling Arrays.hashCode() on the varargs array, applying the same 31-multiplier accumulation pattern used for arrays and records — convenient for multi-field hashCode() overrides, though it boxes primitive arguments and allocates a varargs array, making it slightly slower than a hand-written combination for hot paths.
Q35. How do Java records handle hashCode() and equals()?
A: A record automatically generates hashCode() and equals() implementations based on all of its declared components, combining their hash codes and comparing them for structural (value-based) equality, without any manual coding required. This makes records naturally safe and convenient as HashMap keys as long as every component is itself immutable — a record containing a mutable array or mutable object as a component reintroduces the same mutable-key hazard as a hand-written class.
Q36. What is a common hashCode() bug involving array fields?
A: Including an array field directly in a hand-rolled hashCode()/equals() without using Arrays.equals()/Arrays.hashCode() is a frequent mistake, because arrays don't override equals() or hashCode() from Object — comparing two arrays with == or including them raw in Objects.hash() compares/hashes by reference identity, not by content. Two objects holding array fields with identical contents will then incorrectly compare as unequal and hash differently, which silently breaks lookups for keys containing array-typed fields.
Q37. Does overriding equals() require also implementing Comparable's compareTo()?
A: No, they're independent contracts — equals()/hashCode() govern hash-based collections (HashMap, HashSet), while compareTo() governs ordered collections (TreeMap, TreeSet) and sorting. However, Java documents a "consistent with equals" recommendation: ideally x.compareTo(y) == 0 exactly when x.equals(y) is true, because TreeSet and TreeMap use compareTo() alone to determine both ordering and uniqueness — violating this can make an object equal by equals() but treated as a distinct element by a TreeSet.
Q38. Walk through what happens when you call get() with a key whose hash code changed after insertion.
A: HashMap.get() computes the key's current hash code, applies the spreading function, masks it to a bucket index, and searches only that one bucket's chain/tree for an entry whose stored key equals() the lookup key. If the key mutated after insertion, its current hash points to a different bucket than the one it was actually stored in during put(), so the search examines the wrong bucket, finds no match, and get() returns null — even though the entry is still physically present, just unreachable, in its original bucket.
Q39. What's the best practice for choosing which fields to include in hashCode()?
A: Use only immutable fields that also participate in equals(), and prefer a stable subset that uniquely (or near-uniquely) identifies the object rather than every field — including too many fields, especially ones prone to small variations, can hurt distribution quality if it causes near-duplicate objects to still collide. For frequently-hashed, immutable classes, caching the computed hash code in a field (as String does) avoids recomputation on every map operation.
Q40. Is it legal for hashCode() to always return the same constant (e.g., return 1)? What's the effect?
A: It is legal — the contract only requires that equal objects share a hash code, not that the hash function be good — but it is catastrophic for performance. Every key would land in the exact same bucket, degrading every HashMap operation from average O(1) to worst-case O(n) (or O(log n) once that single giant bucket treeifies), effectively turning the hash table into a glorified linked list or tree scanned on every access.
Q41. What is the internal data structure backing java.util.HashMap?
A: HashMap is backed by an array of Node<K,V> (called table), where each element is either null, a single node, the head of a linked list of nodes (chaining), or, since Java 8, the root of a red-black tree of TreeNode<K,V> once a bucket's chain grows long enough. Each Node stores the cached hash, the key, the value, and a reference to the next node in its bucket's chain.
Q42. What are HashMap's default initial capacity and load factor?
A: The no-argument constructor sets an implicit initial capacity of 16 buckets (the table is actually allocated lazily, on the first put()) and a default load factor of 0.75. This means the map resizes once it holds more than 16 * 0.75 = 12 entries, doubling capacity to 32 and rehashing all existing entries into the new table.
Q43. How does HashMap's put() method work step by step?
A: First it computes the key's spread hash and masks it to find the target bucket index. If the bucket is empty, it inserts a new node directly; if occupied, it walks the chain (or searches the tree) comparing hash codes and then equals() against each existing entry — if a match is found, the value is replaced and the old value returned; otherwise a new node is appended at the tail of the chain. After insertion, if the chain length in that bucket reaches the treeify threshold and the table is large enough, the bucket is converted to a tree; finally, if the total size now exceeds capacity * loadFactor, the whole table is resized.
// Simplified conceptual model of HashMap.put()
V put(K key, V value) {
int hash = spread(key == null ? 0 : key.hashCode());
int idx = (table.length - 1) & hash;
Node<K,V> node = table[idx];
if (node == null) {
table[idx] = new Node<>(hash, key, value, null);
} else {
while (true) {
if (node.hash == hash && Objects.equals(node.key, key)) {
V old = node.value;
node.value = value;
return old;
}
if (node.next == null) {
node.next = new Node<>(hash, key, value, null);
break;
}
node = node.next;
}
}
if (++size > threshold) resize();
return null;
}Q44. How does HashMap's get() method work step by step?
A: It computes the key's spread hash, masks it to the same bucket index formula used by put(), and if the bucket is non-empty, it first checks the bucket's head node directly (a fast path for the common single-entry bucket case). If the head doesn't match, it either walks the remaining linked list comparing hash then equals() on each node, or, if the bucket has been treeified, performs a red-black tree search — both stopping as soon as a matching key is found, or returning null if the bucket is exhausted.
Q45. What triggers a resize in HashMap?
A: After every successful insertion of a new key (not an update of an existing key's value), HashMap checks whether size > threshold, where threshold = capacity * loadFactor. If the size has exceeded that threshold, the map immediately resizes — doubling the backing array's capacity and rehashing/redistributing every existing entry into the new, larger table before the put() call returns.
Q46. How does HashMap's resize/rehash mechanism work, and why is it more efficient than a naive full rehash?
A: Because capacity always doubles and stays a power of two, for any entry in an old bucket at index i, its new index after resizing is either still i (if the newly relevant high bit of its hash is 0) or i + oldCapacity (if that bit is 1) — there is no other possibility. HashMap exploits this by splitting each old bucket's chain into exactly two new chains ("lo" and "hi") in a single pass based on that one bit, relinking nodes directly instead of recomputing hash % newCapacity from scratch for every entry, which keeps resize proportional to the number of entries rather than requiring a full re-hash computation per entry.
// Simplified split logic during resize (Java 8+)
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> e = oldTable[oldIndex];
while (e != null) {
Node<K,V> next = e.next;
if ((e.hash & oldCapacity) == 0) { // bit is 0 -> stays at same index
if (loTail == null) loHead = e; else loTail.next = e;
loTail = e;
} else { // bit is 1 -> moves to index + oldCapacity
if (hiTail == null) hiHead = e; else hiTail.next = e;
hiTail = e;
}
e = next;
}
newTable[oldIndex] = loHead;
newTable[oldIndex + oldCapacity] = hiHead;Q47. Why did Java 8 change resize to preserve relative order within a bucket, and what bug did the old behavior cause?
A: Pre-Java 8 HashMap rehashed by inserting each old-bucket entry at the head of its new bucket's list, which reversed the chain's order on every resize. Combined with non-atomic pointer updates, this reversal created a notorious bug: if two threads resized a HashMap concurrently (despite it not being thread-safe), the head-insertion pattern could form a circular reference between nodes, causing get() to spin in an infinite loop and pin a CPU core at 100%. Java 8's lo/hi tail-append split preserves each bucket's original relative order and, as a side effect, removed that specific infinite-loop failure mode (though HashMap remains fundamentally not thread-safe for other reasons).
Q48. What is treeification in HashMap, and what are its exact thresholds?
A: Treeification converts a bucket's linked list of nodes into a red-black tree of TreeNode<K,V> objects when that bucket's chain reaches TREEIFY_THRESHOLD = 8 entries, but only if the overall table capacity is at least MIN_TREEIFY_CAPACITY = 64. This bounds worst-case lookup within that one bucket at O(log n) instead of O(n), primarily as a defense against pathological hash distributions or deliberate hash-flooding attacks that would otherwise degrade the whole map's performance.
Q49. What is the untreeify threshold, and when does a tree revert to a list?
A: UNTREEIFY_THRESHOLD = 6. A treeified bucket is converted back to a plain linked list if, during a resize split, one of the two resulting "lo"/"hi" buckets ends up with 6 or fewer entries — small buckets don't benefit from tree overhead, so shrinking back to a list avoids unnecessary red-black tree maintenance costs for a bucket that's no longer densely populated. Note that plain removal via remove() does not by itself trigger untreeification; it happens specifically during the resize split.
Q50. Why does HashMap only treeify when table capacity is at least 64, instead of at any capacity?
A: If the table is still small (capacity < 64), a long chain in one bucket usually signals that the table itself is simply too small and under-resized for its entry count, not that the hash distribution is inherently pathological — resizing the whole table (which redistributes entries across many more buckets) is a more effective fix than building a tree structure in one bucket. HashMap therefore prefers resizing over treeification while the table is small, and only treeifies once it's confident the table is already reasonably sized and the collision is a genuine hotspot.
Q51. What is HashMap's worst-case time complexity for get()/put(), before and after Java 8?
A: Before Java 8, a bucket was always a plain linked list, so a pathological hash distribution (or a deliberate hash-flooding attack) that funneled all n entries into one bucket degraded get()/put() to worst-case O(n). Since Java 8, once a bucket's chain reaches the treeify threshold in a sufficiently large table, it becomes a red-black tree, bounding that bucket's worst case at O(log n) — average-case performance for well-distributed keys remains O(1) in both versions.
Q52. What is the difference between Node<K,V> and TreeNode<K,V> internally?
A: Node<K,V> is the basic singly linked list element storing hash, key, value, and a next pointer, used for un-treeified buckets. TreeNode<K,V> extends a doubly-linked variant of Node (LinkedHashMap.Entry-like linkage) and additionally carries parent, left, right, and red/black color fields needed to implement a self-balancing red-black tree, letting a single treeified bucket support O(log n) search, insert, and delete instead of the O(n) linear scan a plain chain requires.
Q53. How does HashMap handle a null key?
A: HashMap permits exactly one null key, always stored at bucket index 0, because the internal hash() function explicitly special-cases null to return a hash of 0 (avoiding a NullPointerException from calling null.hashCode()). Looking up or removing the null key works the same as any other key, just skipping the equals() call and comparing for reference equality to null instead, since null.equals(...) would itself throw.
Q54. Is HashMap thread-safe? What can go wrong if it's used concurrently without synchronization?
A: HashMap is explicitly not thread-safe — none of its methods synchronize access. Concurrent modification without external synchronization can corrupt internal structure (dropped entries, `size` becoming inconsistent with actual contents), and in Java 7's head-insertion resize implementation, concurrent resizes could create a circular linked list, causing get() to loop forever and pin a CPU core. For concurrent use, the correct choices are ConcurrentHashMap, Collections.synchronizedMap(new HashMap<>()), or external locking — never a plain HashMap shared unsynchronized across threads.
Q55. Does HashMap guarantee any iteration order?
A: No — HashMap makes no guarantee about iteration order, and that order can change arbitrarily across resizes, even for the exact same set of entries, because entries are stored by bucket index, which is a function of the current table capacity. Code that depends on a stable or insertion-preserving order should use LinkedHashMap (insertion or access order) or TreeMap (sorted order) instead.
Q56. What is HashMap's fail-fast iterator, and when does it throw ConcurrentModificationException?
A: HashMap tracks a modCount field incremented on every structural modification (put of a new key, remove, clear — not a value update on an existing key). Its iterator captures the modCount at creation and checks it on every next() call; if the map was structurally modified outside the iterator itself since it was created, it throws ConcurrentModificationException as a best-effort safety check, not a hard guarantee (behavior is technically undefined if you ignore the exception, since detection isn't foolproof).
Map<String, Integer> map = new HashMap<>(Map.of("a", 1, "b", 2));
for (String key : map.keySet()) {
if (key.equals("a")) map.remove(key); // throws ConcurrentModificationException
}
// Safe alternative:
map.keySet().removeIf(key -> key.equals("a"));Q57. How does the constructor HashMap(int initialCapacity) actually determine the real table size?
A: HashMap doesn't use the requested capacity directly; it rounds up to the next power of two greater than or equal to the requested value, using an internal tableSizeFor() bit-manipulation routine, since the table must always be a power of two for the bitmask indexing trick to work. Requesting new HashMap<>(17), for example, actually allocates a table of capacity 32.
static final int tableSizeFor(int cap) {
int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
// tableSizeFor(17) -> 32, tableSizeFor(16) -> 16, tableSizeFor(1) -> 1Q58. Why does choosing a good initial capacity matter for performance-sensitive code?
A: If you know approximately how many entries a HashMap will hold, pre-sizing it (e.g., new HashMap<>((int)(expectedSize / 0.75f) + 1)) avoids one or more expensive resize operations, each of which allocates a new backing array and rehashes every existing entry into it — an O(n) operation that happens on top of the normal O(1) insertions. Under-sizing forces repeated doublings as the map grows organically; over-sizing wastes memory on mostly-empty buckets, so the goal is to size close to the actual expected entry count.
Q59. What is the amortized time complexity of a resize, spread across all the insertions that led to it?
A: A single resize touching n entries costs O(n), but because capacity doubles each time, resizes become exponentially less frequent as the map grows (much like ArrayList's doubling strategy) — the total cost of all resizes across n total insertions sums to O(n), the same order as a geometric series. Averaged (amortized) across all n insertions, each individual put() is still effectively O(1), even though any single call can occasionally trigger the O(n) resize.
Q60. What do computeIfAbsent(), compute(), and merge() do, and why are they useful for hashing-based workflows?
A: computeIfAbsent(key, mappingFunction) inserts a computed value only if the key is absent (or mapped to null), returning the existing or newly computed value — ideal for lazily initializing per-key collections. compute(key, remappingFunction) unconditionally recomputes the value based on the current mapping (or null if absent). merge(key, value, remappingFunction) combines a new value with any existing one, commonly used for counting/aggregation. All three perform their bucket lookup and mutation atomically-in-effect within a single call (though not thread-safe on plain HashMap), avoiding a separate containsKey()/get()/put() sequence that would otherwise hash and search the bucket multiple times.
Map<String, List<Integer>> groups = new HashMap<>();
groups.computeIfAbsent("even", k -> new ArrayList<>()).add(4);
Map<String, Integer> wordCounts = new HashMap<>();
for (String word : words) {
wordCounts.merge(word, 1, Integer::sum); // increment or initialize to 1
}Q61. What is the difference between HashMap and IdentityHashMap?
A: HashMap determines equality and hashing via each key's equals()/hashCode() methods (logical/value equality). IdentityHashMap deliberately violates the general Map contract by using == reference comparison and System.identityHashCode() instead, so two distinct objects that are .equals()-equal are still treated as different keys. It's a niche tool for topology-preserving object graph algorithms (e.g., serialization frameworks tracking already-visited objects) where you specifically want identity, not value, semantics.
Q62. What is HashMap's maximum possible capacity, and why is it capped there?
A: The maximum capacity is 1 << 30 (about 1.07 billion), one bit shy of overflowing a signed 32-bit int as the next power of two. It's capped there because Java array lengths are represented as signed 32-bit ints, and doubling beyond 1 << 30 would either overflow to a negative capacity or exceed the maximum array size the JVM can allocate; once this cap is hit, HashMap stops resizing and simply allows buckets to grow arbitrarily long (or tree) instead.
Q63. How is java.util.HashSet implemented internally?
A: HashSet is a thin wrapper around a HashMap instance; every element added to the set is actually stored as a key in an internal HashMap<E, Object>, paired with a shared dummy sentinel value. This means HashSet inherits essentially all of HashMap's internal characteristics — bucket array, load factor 0.75, resizing, treeification — and its performance guarantees are exactly HashMap's key-side guarantees.
Q64. What does HashSet.add() actually do under the hood?
A: add(element) delegates to the backing map's put(element, PRESENT), where PRESENT is a single shared static Object instance used as a placeholder value for every entry. It returns true if the map's put() indicates no prior mapping existed for that key (i.e., the element was genuinely new), and false if the element was already present, since put() on an existing key just overwrites the (identical, meaningless) value and returns the old one.
// Simplified real implementation
public class HashSet<E> {
private static final Object PRESENT = new Object();
private transient HashMap<E, Object> map = new HashMap<>();
public boolean add(E e) {
return map.put(e, PRESENT) == null;
}
public boolean contains(Object o) {
return map.containsKey(o);
}
}Q65. What is the time complexity of HashSet's core operations?
A: add(), contains(), and remove() are all O(1) average case, and O(log n) worst case within a treeified bucket (Java 8+) — identical to HashMap's key-side complexity, since HashSet is a HashMap wrapper. Iterating the full set is O(capacity + size), because iteration must walk every bucket slot (even empty ones) in the backing array plus every stored element, which is why an oversized, sparsely-filled HashSet iterates more slowly than a tightly-sized one holding the same number of elements.
Q66. What is LinkedHashSet and how does it maintain insertion order?
A: LinkedHashSet extends HashSet but is backed by a LinkedHashMap instead of a plain HashMap. Every entry additionally carries "before" and "after" pointers forming a doubly linked list across all entries in insertion order (independent of the bucket array's layout), so iteration walks that linked list rather than the bucket array, yielding predictable insertion-order iteration while keeping O(1) average hash-based lookup.
Q67. What is TreeSet and how does it maintain sorted order internally?
A: TreeSet is backed by a TreeMap, which implements a self-balancing red-black tree ordered by either the elements' natural ordering (Comparable) or an explicit Comparator supplied at construction. Because it's tree-based rather than hash-based, its core operations (add, remove, contains) are O(log n) rather than HashSet's O(1) average, but it gains sorted iteration order and range-query operations like headSet(), tailSet(), floor(), and ceiling() that a hash-based set cannot support efficiently.
Q68. What happens if you add elements to a TreeSet whose class implements neither Comparable nor supplies a Comparator?
A: The very first add() call throws a ClassCastException at runtime, because TreeSet has no way to determine ordering between elements — it always needs a natural ordering (the element class implementing Comparable<T>) or an explicit Comparator passed to its constructor, and there's no fallback to insertion order or hash-based bucketing the way HashSet has.
class Point { int x, y; } // no Comparable implemented
Set<Point> set = new TreeSet<>();
set.add(new Point()); // throws ClassCastException: Point cannot be cast to Comparable
// Fix: supply a Comparator explicitly
Set<Point> ordered = new TreeSet<>(Comparator.comparingInt(p -> p.x));Q69. How do HashSet, LinkedHashSet, and TreeSet compare in complexity and ordering?
A: HashSet offers O(1) average add/contains/remove with no ordering guarantee at all, and the lowest memory overhead of the three. LinkedHashSet matches HashSet's O(1) average complexity but adds a doubly linked list (extra per-entry pointer overhead) to guarantee stable insertion-order iteration. TreeSet trades speed for structure: O(log n) for add/contains/remove, but guarantees fully sorted iteration order and supports navigable range operations that neither hash-based set can offer.
Q70. When should you choose HashSet vs LinkedHashSet vs TreeSet?
A: Choose HashSet by default when you only need fast membership testing and don't care about order — it's the fastest and leanest of the three. Choose LinkedHashSet when you need predictable, reproducible iteration order (e.g., matching insertion order for deterministic output or caching with recency semantics) without paying tree-based O(log n) costs. Choose TreeSet when you need elements sorted at all times, or need range queries like "give me everything between X and Y" — accepting O(log n) operations as the cost of that ordering.
Q71. Can a HashSet contain duplicate elements? How does add() actually detect a duplicate?
A: No — a HashSet's core contract is that it contains no duplicate elements as determined by equals(). Internally, since elements are stored as keys of the backing HashMap, "detecting a duplicate" is exactly the same process as HashMap detecting an existing key during put(): compute the hash, find the bucket, and walk the bucket comparing hash codes and then equals() against existing entries — if a match is found, the new element is rejected (the map's value is overwritten but the key/element itself is unchanged) and add() returns false.
Q72. Does LinkedHashSet use more memory than HashSet for the same elements? Why?
A: Yes — each entry in a LinkedHashMap (and therefore LinkedHashSet) carries two additional object references (before and after) beyond what a plain HashMap/HashSet node needs, to maintain the doubly linked insertion-order list. For a set with n elements, that's 2n extra reference fields of overhead, a modest but real memory cost paid specifically for the guaranteed iteration order.
Q73. What navigable methods does TreeSet provide that HashSet cannot support efficiently?
A: As a NavigableSet, TreeSet provides floor(e) (largest element ≤ e), ceiling(e) (smallest element ≥ e), lower(e) (strictly less than e), higher(e) (strictly greater than e), plus range views like headSet(), tailSet(), and subSet() — all in O(log n), because the underlying red-black tree structure makes "nearby" elements directly discoverable through tree traversal. A HashSet has no notion of "nearby" at all since hash-based bucket placement is intentionally unrelated to element ordering.
TreeSet<Integer> ts = new TreeSet<>(List.of(10, 20, 30, 40));
ts.floor(25); // 20 - largest element <= 25
ts.ceiling(25); // 30 - smallest element >= 25
ts.higher(20); // 30 - strictly greater than 20
ts.lower(20); // 10 - strictly less than 20Q74. Can you store null elements in HashSet, TreeSet, and LinkedHashSet?
A: HashSet and LinkedHashSet both permit exactly one null element, since they delegate to a backing HashMap/LinkedHashMap that itself allows one null key. TreeSet does not permit null (it throws NullPointerException on add(null) in most configurations) because comparing null against other elements via compareTo() or a Comparator has no well-defined ordering result, unless a custom comparator is explicitly written to treat null as a sortable value.
Q75. Why is plain HashMap unsafe for concurrent use, at a mechanical level?
A: Every mutating operation touches shared mutable state — the bucket array, chain pointers, and the size counter — with no memory barriers or locks to make one thread's writes visible or atomic with respect to another thread's concurrent reads/writes. Two threads calling put() concurrently can race on appending to the same bucket's chain, silently losing one of the two insertions, and a thread iterating while another structurally modifies the map can observe a torn, partially-updated structure or throw ConcurrentModificationException.
Q76. How did Java 7's ConcurrentHashMap achieve thread safety, and what was its main limitation?
A: Java 7's ConcurrentHashMap partitioned the table into a fixed number of independent segments (16 by default), each an independently lockable mini hash table with its own lock. This allowed up to as many concurrent writers as there were segments (writes to different segments never blocked each other), but the segment count was fixed at construction, capping real-world write concurrency, and operations spanning multiple segments (like a global size()) still needed to coordinate across all of them.
Q77. How did Java 8 redesign ConcurrentHashMap's internal concurrency strategy?
A: Java 8 dropped the segment array entirely in favor of the same flat bucket-array structure as HashMap, synchronizing at the much finer granularity of individual bin (bucket) head nodes rather than whole segments, and using CAS (compare-and-swap) operations for lock-free insertion into an empty bucket. This allows far higher effective write concurrency than the fixed 16-segment scheme, since two threads writing to different buckets almost never contend, and it also brought treeification of large buckets, matching HashMap's Java 8 improvements.
Q78. What roles do volatile fields and CAS operations play in ConcurrentHashMap's put()?
A: The table array reference and each bucket's head-node reads are volatile, guaranteeing that a write by one thread (like publishing a newly allocated node) is immediately visible to other threads reading the same slot, without needing a lock just to read. When inserting into an empty bucket, ConcurrentHashMap uses Unsafe.compareAndSwapObject (or its VarHandle equivalent in modern versions) to atomically install the new head node — a lock-free fast path; only when a bucket already has a node does it fall back to a synchronized block on that bucket's head node for the append.
Q79. Does ConcurrentHashMap allow null keys or null values? Why not?
A: No — unlike HashMap, ConcurrentHashMap disallows both null keys and null values, throwing NullPointerException if attempted. The reason is concurrency-specific ambiguity: in a single-threaded HashMap, map.get(key) == null unambiguously combined with containsKey() tells you whether the key is absent versus mapped to null, but in a concurrently-modified map, a null return from get() could mean "absent" or "another thread just removed it" or "mapped to null" — that ambiguity is unacceptable for a structure designed around safe concurrent access, so nulls are disallowed entirely.
Q80. How does ConcurrentHashMap handle resizing while other threads may be reading or writing concurrently?
A: Once a resize begins, ConcurrentHashMap allows multiple threads to cooperatively help move (transfer) buckets from the old table to the new one in parallel chunks, rather than blocking all access during a single-threaded rehash. A thread that calls put() during an in-progress resize can detect this (via a special "forwarding node" marker left in already-migrated old buckets) and pitch in on the transfer work itself before completing its own operation, which both speeds up the resize and keeps the map usable throughout.
Q81. What's the trade-off behind ConcurrentHashMap's size() method?
A: Rather than maintaining one contended shared counter that every thread would need to synchronize on for every insert/remove, ConcurrentHashMap tracks size using a set of striped internal counter cells (similar in spirit to LongAdder), which different threads update independently to avoid contention. size() (and mappingCount()) sums these cells at call time, meaning the returned value is a best-effort approximation that can be stale the instant it's computed if the map is being concurrently modified — acceptable because an exact live count is not a meaningful concept for a data structure under concurrent mutation anyway.
Q82. How does ConcurrentHashMap differ from Collections.synchronizedMap(new HashMap<>())?
A: synchronizedMap wraps a HashMap and synchronizes on a single monitor for every single method call, serializing all access — only one thread can touch the map at any moment, even for reads. ConcurrentHashMap instead allows fully concurrent reads (no locking at all for reads in the common case) and fine-grained per-bucket locking for writes, giving dramatically higher throughput under contention; it also provides atomic compound operations (putIfAbsent, computeIfAbsent) that synchronizedMap cannot make atomic without external locking, since two separate synchronized calls aren't atomic together.
Q83. What atomic compound operations does ConcurrentHashMap provide, and why do they matter?
A: Methods like putIfAbsent(), computeIfAbsent(), compute(), and replace(key, oldValue, newValue) perform their check-then-act logic as a single atomic operation with respect to other threads, closing the race-condition window that exists if you manually write if (!map.containsKey(k)) map.put(k, v) using two separate calls (another thread could insert between the check and the put). These are essential for correct concurrent producer patterns like lazily-initialized shared caches.
ConcurrentHashMap<String, List<String>> index = new ConcurrentHashMap<>();
// Thread-safe: only one thread's supplier runs per key, even under contention
index.computeIfAbsent("errors", k -> new CopyOnWriteArrayList<>()).add("timeout");
AtomicInteger requestCount = new AtomicInteger();
ConcurrentHashMap<String, Integer> hits = new ConcurrentHashMap<>();
hits.merge("GET /api", 1, Integer::sum); // atomic increment-or-initializeQ84. Does ConcurrentHashMap's iterator throw ConcurrentModificationException?
A: No — ConcurrentHashMap's iterators are weakly consistent rather than fail-fast: they're guaranteed not to throw ConcurrentModificationException and will reflect the state of the map at some point during or after the iterator's creation, but they may or may not reflect modifications made concurrently while iteration is in progress. This is a deliberate design choice trading strict consistency for lock-free, non-blocking iteration.
Q85. How does ConcurrentHashMap's treeification behavior compare to HashMap's?
A: ConcurrentHashMap treeifies large buckets using the same TREEIFY_THRESHOLD (8) and MIN_TREEIFY_CAPACITY (64) constants as HashMap, converting an overloaded bucket into a red-black tree for the same O(log n) worst-case protection. The key difference is concurrency safety during the conversion itself — treeifying and untreeifying must be coordinated with the fine-grained per-bin locking scheme so that concurrent readers never observe a bucket in a half-converted, structurally inconsistent state.
Q86. When should you reach for ConcurrentHashMap versus a HashMap guarded by an external synchronized block?
A: Prefer ConcurrentHashMap whenever multiple threads read and write a shared map concurrently and you want good throughput — its fine-grained locking and lock-free reads scale far better under contention than a single external lock serializing every access. An externally synchronized HashMap can still make sense for very simple, low-contention cases, or when you need to atomically coordinate the map alongside other unrelated shared state under the same lock, something ConcurrentHashMap's own internal locking can't help with since it only protects itself.
Q87. How do you solve the classic Two Sum problem using hashing?
A: Iterate through the array once, and for each element check whether target - currentElement already exists in a HashMap of previously seen values mapped to their indices; if it does, you've found the pair in a single pass. This runs in O(n) time and O(n) space, versus O(n²) for the brute-force nested-loop comparison of every pair — the hashing trick converts a "does this value exist" check from an O(n) scan into an O(1) average lookup.
int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> seen = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (seen.containsKey(complement)) {
return new int[]{seen.get(complement), i};
}
seen.put(nums[i], i);
}
throw new IllegalArgumentException("No two sum solution");
}Q88. How do you find the first duplicate element in an array using hashing?
A: Scan the array left to right, adding each element to a HashSet; the first element that add() reports as already present (returns false) is the first duplicate encountered by scan order. This is O(n) time, O(n) space, and avoids the O(n log n) cost of sorting first just to compare adjacent elements.
Integer firstDuplicate(int[] nums) {
Set<Integer> seen = new HashSet<>();
for (int n : nums) {
if (!seen.add(n)) return n; // add() returns false if already present
}
return null;
}Q89. How do you check whether two arrays contain the same elements with the same frequencies, regardless of order?
A: Build a frequency map (HashMap<Integer, Integer>) by incrementing counts for each element of the first array, then decrement for each element of the second array, removing/zeroing entries as counts hit zero. If every count returns to exactly zero and both arrays had equal length, the arrays are frequency-equal; this is O(n) time and O(n) space, avoiding the O(n log n) cost of sorting both arrays to compare directly.
boolean sameFrequency(int[] a, int[] b) {
if (a.length != b.length) return false;
Map<Integer, Integer> counts = new HashMap<>();
for (int x : a) counts.merge(x, 1, Integer::sum);
for (int x : b) {
Integer c = counts.get(x);
if (c == null || c == 0) return false;
counts.put(x, c - 1);
}
return true;
}Q90. How do you find the longest substring without repeating characters using a HashMap?
A: Use a variable-size sliding window with a HashMap tracking each character's most recent index. Expand the window's right edge; whenever the incoming character was seen at an index inside the current window, jump the left edge to just past that previous occurrence instead of shrinking one step at a time, updating the max length as you go. This achieves O(n) time since each character is processed in O(1) amortized work, versus a naive O(n²) or O(n³) brute force checking every substring.
int lengthOfLongestSubstring(String s) {
Map<Character, Integer> lastIndex = new HashMap<>();
int left = 0, maxLen = 0;
for (int right = 0; right < s.length(); right++) {
char c = s.charAt(right);
if (lastIndex.containsKey(c) && lastIndex.get(c) >= left) {
left = lastIndex.get(c) + 1;
}
lastIndex.put(c, right);
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}Q91. How do you count the number of subarrays whose sum equals a target k, using hashing?
A: Maintain a running prefix sum while scanning left to right, and a HashMap counting how many times each prefix-sum value has occurred so far. At each position, the number of valid subarrays ending here equals the count of (runningSum - k) already seen, because if that earlier prefix sum recurs, the subarray between the two points sums to exactly k. This is O(n) time and O(n) space, a major improvement over the O(n²) brute force of summing every possible subarray directly.
int subarraySum(int[] nums, int k) {
Map<Integer, Integer> prefixCount = new HashMap<>();
prefixCount.put(0, 1); // empty prefix
int sum = 0, count = 0;
for (int n : nums) {
sum += n;
count += prefixCount.getOrDefault(sum - k, 0);
prefixCount.merge(sum, 1, Integer::sum);
}
return count;
}Q92. How do you find the intersection of two arrays using a HashSet?
A: Insert all elements of the smaller array into a HashSet, then iterate the other array and collect any element found in that set (optionally removing matched elements from the set to avoid duplicate results). This is O(m+n) time and O(min(m,n)) space, versus O(m×n) for a nested-loop comparison, or O((m+n)log(m+n)) if you sort both arrays first and merge-scan.
Set<Integer> intersect(int[] a, int[] b) {
Set<Integer> setA = new HashSet<>();
for (int x : a) setA.add(x);
Set<Integer> result = new HashSet<>();
for (int x : b) if (setA.contains(x)) result.add(x);
return result;
}Q93. How does a HashMap enable an O(1) LRU cache implementation alongside a doubly linked list?
A: An LRU cache pairs a HashMap (key → node reference) for O(1) lookup with a doubly linked list ordered by recency, where the HashMap's stored value is a direct pointer to that key's node in the list. On get(), the map locates the node in O(1), and the node is unlinked and relinked at the "most recently used" end of the list in O(1) (no traversal needed, since we already hold a direct reference); eviction on capacity overflow removes the list's "least recently used" tail node in O(1) and removes its key from the map in O(1). Java's LinkedHashMap actually implements exactly this pattern internally when constructed with access-order mode, which is why overriding removeEldestEntry() on a LinkedHashMap is a common one-line LRU cache implementation.
class LRUCache<K,V> extends LinkedHashMap<K,V> {
private final int capacity;
LRUCache(int capacity) {
super(16, 0.75f, true); // true = access-order, not insertion-order
this.capacity = capacity;
}
@Override protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return size() > capacity;
}
}Q94. How do you find the top K frequent elements in an array using hashing?
A: First build a frequency map with a HashMap in O(n). Then either use a min-heap of size k over the map's entries (push each entry, pop the smallest-frequency one when the heap exceeds size k), giving O(n log k) total, or use bucket sort where bucket index equals frequency (frequencies are bounded by n, so this works in O(n) since you never need comparison-based sorting for a bounded range of possible frequencies).
int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> freq = new HashMap<>();
for (int n : nums) freq.merge(n, 1, Integer::sum);
PriorityQueue<Integer> heap = new PriorityQueue<>(
Comparator.comparingInt(freq::get));
for (int key : freq.keySet()) {
heap.offer(key);
if (heap.size() > k) heap.poll();
}
int[] result = new int[k];
for (int i = k - 1; i >= 0; i--) result[i] = heap.poll();
return result;
}Q95. How do you detect a cycle in a linked list using a HashSet?
A: Traverse the list, adding each visited node reference (not value — reference identity matters here) to a HashSet; if you ever encounter a node already present in the set, a cycle exists. This is O(n) time, O(n) space. The more space-efficient alternative, Floyd's tortoise-and-hare (two pointers moving at different speeds), solves the same problem in O(n) time but O(1) space, and is the answer most interviewers actually want once you've mentioned the hashing approach.
boolean hasCycle(ListNode head) {
Set<ListNode> visited = new HashSet<>();
ListNode current = head;
while (current != null) {
if (!visited.add(current)) return true; // already seen this node
current = current.next;
}
return false;
}Q96. How would you design a HashSet without using Java's built-in hash table classes (LeetCode-style "Design HashSet")?
A: Allocate a fixed-size array of buckets, where each bucket is itself a small list (e.g., a linked list or ArrayList) holding the values that hash into it; use a simple modulo hash function (key % bucketCount) to pick the bucket. add() checks the target bucket for an existing equal value before appending; remove() scans the bucket and removes a match; contains() scans the bucket for a match — all O(bucketSize) on average, which stays close to O(1) as long as the bucket count is reasonably proportional to the expected number of stored elements.
class MyHashSet {
private final List<Integer>[] buckets;
private static final int SIZE = 769; // a prime bucket count
@SuppressWarnings("unchecked")
MyHashSet() {
buckets = new List[SIZE];
for (int i = 0; i < SIZE; i++) buckets[i] = new LinkedList<>();
}
private int hash(int key) { return key % SIZE; }
void add(int key) {
List<Integer> bucket = buckets[hash(key)];
if (!bucket.contains(key)) bucket.add(key);
}
void remove(int key) { buckets[hash(key)].remove((Integer) key); }
boolean contains(int key) { return buckets[hash(key)].contains(key); }
}Q97. How do you determine if two strings are isomorphic using hashing?
A: Two strings are isomorphic if there's a consistent one-to-one character mapping between them. Maintain two HashMaps — one mapping characters from string A to string B, and one mapping the reverse — and walk both strings in lockstep, checking that each character's mapping (if it already exists) matches the current pairing, and inserting new mappings otherwise; a mismatch in either direction fails the check. Using two maps (not one) is essential to enforce that the mapping is bijective, not just one-directional. This is O(n) time and O(1) space for a bounded alphabet.
boolean isIsomorphic(String s, String t) {
if (s.length() != t.length()) return false;
Map<Character, Character> sToT = new HashMap<>();
Map<Character, Character> tToS = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
char a = s.charAt(i), b = t.charAt(i);
if (sToT.containsKey(a) && sToT.get(a) != b) return false;
if (tToS.containsKey(b) && tToS.get(b) != a) return false;
sToT.put(a, b);
tToS.put(b, a);
}
return true;
}Q98. How do you solve the "word pattern" problem (does a pattern like "abba" match a word sequence structurally) using hashing?
A: Split the input string into words and, exactly like the isomorphic-strings problem, maintain two HashMaps enforcing a bijective mapping — one from pattern character to word, one from word to pattern character — walking the pattern and the word list in lockstep and rejecting any inconsistency in either direction. This is O(n) time where n is the number of words, and demonstrates that "isomorphism" style problems across characters, words, or any tokenizable sequence all reduce to the same bidirectional-hashmap technique.
Q99. How do you check for duplicates within a window of k indices in an array, using hashing?
A: Slide a window of size k across the array while maintaining a HashSet of the elements currently inside the window. For each new element, check if it's already in the set (a duplicate within the last k elements); then, if the window has grown past size k, remove the element that just fell out of the window's left edge from the set. This is O(n) time and O(k) space, versus O(n×k) for checking every pair within range directly.
boolean containsNearbyDuplicate(int[] nums, int k) {
Set<Integer> window = new HashSet<>();
for (int i = 0; i < nums.length; i++) {
if (window.contains(nums[i])) return true;
window.add(nums[i]);
if (window.size() > k) window.remove(nums[i - k]);
}
return false;
}Q100. How do you group an array of strings into anagram groups using a HashMap, and what makes a good grouping key?
A: Use a HashMap keyed by a canonical representation of each string — either its sorted character sequence, or a fixed-length character-frequency signature. All strings that map to the same canonical key are anagrams of one another and belong in the same group. Sorting-based keys cost O(n × k log k) total (k = average string length, since each string must be individually sorted); a frequency-count signature key avoids the per-string sort, costing O(n × k) total instead, which is preferable for long strings over a small fixed alphabet.
Q101. What problem does consistent hashing solve that simple modulo-based hashing does not?
A: With plain modulo hashing (hash(key) % numServers), adding or removing even a single server changes the divisor and therefore remaps almost every key to a different server — catastrophic for distributed caches or sharded databases, since it would trigger a near-total cache miss storm or full data reshuffle. Consistent hashing is designed so that adding or removing one node only remaps the keys that were mapped to that specific node, leaving the vast majority of key-to-node assignments undisturbed.
Q102. How does the hash-ring model of consistent hashing work?
A: Both server/node identifiers and keys are hashed onto the same circular numeric range (typically 0 to 2³²-1, visualized as a ring). Each key is assigned to the first node encountered walking clockwise from the key's position on the ring. Because only the segment of the ring between two adjacent nodes is affected when a node is added or removed, only the keys that fall within that specific arc need to be remapped, not the entire keyspace.
Q103. What are virtual nodes in consistent hashing, and why are they needed?
A: Placing each physical server at just one point on the hash ring can produce very uneven load distribution, since the arc lengths between randomly-placed points vary significantly, especially with few nodes. Virtual nodes solve this by hashing each physical server to many points on the ring (e.g., 100-200 virtual replicas per physical node), which averages out arc-length variance across many small segments, giving each physical server a load roughly proportional to its share of virtual nodes and smoothing distribution far more evenly than a single ring position per server.
Q104. Where is consistent hashing actually used in real distributed systems?
A: It's foundational to distributed caches like memcached client libraries, distributed databases such as Apache Cassandra and Amazon DynamoDB for partitioning data across nodes, and load balancers that need to route the same client or key consistently to the same backend (sticky routing) while tolerating backend pool changes gracefully. Its core value proposition — minimal key remapping on cluster resize — is exactly what's needed whenever nodes in a distributed, horizontally-scaled system are added or removed dynamically.
Q105. Quantitatively, how many keys get remapped when a node is added, under consistent hashing versus simple modulo hashing?
A: Under consistent hashing with n nodes, adding a new node remaps approximately 1/(n+1) of all keys on average — only the keys that fall in the arc now claimed by the new node. Under simple modulo hashing, changing the divisor from n to n+1 changes key % n to key % (n+1) for nearly every key, since the two moduli share little structural relationship, effectively remapping close to (n/(n+1)), i.e. nearly all keys — a dramatic difference that's the entire motivation for using consistent hashing in dynamically-scaled systems.
Q106. How would you design a basic hash map from scratch in Java? What's the core structure?
A: The core structure is an array of buckets, where each bucket is a simple linked list (or resizable list) of key-value entry nodes — the same conceptual design HashMap itself uses. You need: an array field for the buckets, a size counter, a load factor threshold, a hash function that maps a key to a bucket index, and put/get/remove methods that compute the target bucket and then search/mutate its chain.
class MyHashMap<K, V> {
static class Entry<K, V> {
K key; V value; Entry<K, V> next;
Entry(K key, V value) { this.key = key; this.value = value; }
}
private Entry<K, V>[] buckets;
private int size = 0;
private static final int DEFAULT_CAPACITY = 16;
private static final float LOAD_FACTOR = 0.75f;
@SuppressWarnings("unchecked")
MyHashMap() { buckets = new Entry[DEFAULT_CAPACITY]; }
private int indexFor(K key) {
int h = (key == null) ? 0 : key.hashCode();
h ^= (h >>> 16); // spread bits, same trick as java.util.HashMap
return (h & (buckets.length - 1));
}
}Q107. What would the put() implementation look like for a custom hash map?
A: Compute the target bucket index, walk that bucket's chain checking each entry's key with equals() — if found, overwrite the value and return the old one; if not found after reaching the end of the chain, insert a new entry node at the head or tail. Finally, increment the size and check whether a resize is now needed based on the load factor.
V put(K key, V value) {
int idx = indexFor(key);
Entry<K, V> e = buckets[idx];
while (e != null) {
if (Objects.equals(e.key, key)) {
V old = e.value;
e.value = value;
return old;
}
e = e.next;
}
Entry<K, V> newEntry = new Entry<>(key, value);
newEntry.next = buckets[idx]; // insert at head
buckets[idx] = newEntry;
size++;
if (size > buckets.length * LOAD_FACTOR) resize();
return null;
}Q108. What would the get() implementation look like for a custom hash map?
A: Compute the same bucket index using the identical hash function used by put(), then linearly scan that bucket's chain comparing each stored key against the lookup key with equals() (never with ==, except for a deliberate null shortcut), returning the corresponding value on a match or a defined "not found" sentinel (or null) if the chain is exhausted without one.
V get(K key) {
int idx = indexFor(key);
Entry<K, V> e = buckets[idx];
while (e != null) {
if (Objects.equals(e.key, key)) return e.value;
e = e.next;
}
return null;
}Q109. How would you implement resizing for a custom hash map?
A: Allocate a new, larger bucket array (typically double the old capacity), then iterate every entry in every old bucket and reinsert each one into the new array by recomputing its bucket index against the new capacity (since the index formula depends on capacity, every entry can potentially move). Swap the new array in as the active buckets field once the migration completes. A naive implementation recomputes each hash from scratch; a more optimized one (like java.util.HashMap's real approach) exploits the power-of-two capacity relationship to split each old bucket directly into two new buckets without recomputing hashes.
@SuppressWarnings("unchecked")
private void resize() {
Entry<K, V>[] oldBuckets = buckets;
buckets = new Entry[oldBuckets.length * 2];
for (Entry<K, V> head : oldBuckets) {
Entry<K, V> e = head;
while (e != null) {
Entry<K, V> next = e.next;
int idx = indexFor(e.key);
e.next = buckets[idx]; // reinsert into new array
buckets[idx] = e;
e = next;
}
}
}Q110. When designing a custom hash map, how do you decide between chaining and open addressing for collision resolution?
A: Chaining is simpler to implement correctly, especially for deletion (just unlink a node, no tombstones needed), and degrades more gracefully if the hash function turns out to be imperfect since buckets simply grow rather than the whole structure failing to find a free slot. Open addressing rewards you with better cache locality and lower per-entry memory overhead (no linked list pointers), but demands more careful load-factor management and correct tombstone handling for deletes — a reasonable default for an interview "design a hash map" question is chaining, escalating to open addressing only if the interviewer specifically probes for cache-efficiency trade-offs.
Q111. What edge cases must a correct custom hash map implementation handle?
A: Null keys (decide explicitly whether to support one, and route them to a fixed bucket like index 0 rather than calling hashCode() on null); negative hash codes (a raw hash % capacity can be negative in Java, so use a bitmask against a power-of-two capacity, or take Math.abs() carefully — note Math.abs(Integer.MIN_VALUE) famously overflows back to a negative number); resizing correctness when entries are re-hashed into the new table; and iterator behavior if modifications happen during iteration (decide on fail-fast detection or explicitly document undefined behavior).
Q112. How would you make a custom hash map implementation thread-safe, and what are the trade-offs of different approaches?
A: The simplest approach wraps every method in a single synchronized block or lock, guaranteeing correctness but serializing all access — reads block other reads, killing concurrency under load, exactly like Collections.synchronizedMap. A more scalable design follows ConcurrentHashMap's lead: lock at the granularity of individual buckets (an array of lock objects, one per bucket or per group of buckets) so that operations on different buckets can proceed in parallel, combined with volatile reads and CAS-based lock-free insertion into empty buckets for the common uncontended case, at the cost of significantly more implementation complexity and subtler correctness reasoning around resize coordination.
Post a Comment
Add