Collections Framework

1. How does HashMap handle bucket collisions starting in Java 8?

Answer: Starting in Java 8, when a bucket’s chain of colliding entries gets long enough, HashMap converts that linked list into a balanced Red-Black tree.

To understand why, you have to know how a HashMap stores data. Every key is hashed, and the hash decides which bucket (array slot) the entry lands in. If two different keys hash to the same bucket, they collide and get chained together in a linked list. A short list is fine, but a very long list turns what should be O(1) lookup into O(n) — the HashMap degrades to a linear scan.

Before Java 8, that was the end of the story. A badly distributed hash could make a HashMap as slow as a list. Java 8 fixed the worst case with a simple threshold rule:

• When the number of entries in a single bucket reaches 8 (the TREEIFY_THRESHOLD), and
• the total table capacity is at least 64,

the linked list in that bucket is converted into a Red-Black tree. Searching a balanced tree is O(log n), so even a pathological bucket stays fast. If the bucket shrinks back below 6 entries (the UNTREEIFY_THRESHOLD), it reverts to a plain linked list, because for small sizes a list is cheaper.

The two conditions matter — the tree only forms when both the bucket is long and the table is big enough. The capacity check keeps tiny maps from wasting effort on tree construction.

For interviews, the takeaway is the number to remember: 8. That is the threshold at which a HashMap bucket escalates from a linked list to a Red-Black tree, protecting against worst-case O(n) behavior.

Answer:

Starting in Java 8, when a bucket’s chain of colliding entries gets long enough, HashMap converts that linked list into a balanced Red-Black tree.

To understand why, you have to know how a HashMap stores data. Every key is hashed, and the hash decides which bucket (array slot) the entry lands in. If two different keys hash to the same bucket, they collide and get chained together in a linked list. A short list is fine, but a very long list turns what should be O(1) lookup into O(n) — the HashMap degrades to a linear scan.

Before Java 8, that was the end of the story. A badly distributed hash could make a HashMap as slow as a list. Java 8 fixed the worst case with a simple threshold rule:

• When the number of entries in a single bucket reaches 8 (the TREEIFY_THRESHOLD), and
• the total table capacity is at least 64,

the linked list in that bucket is converted into a Red-Black tree. Searching a balanced tree is O(log n), so even a pathological bucket stays fast. If the bucket shrinks back below 6 entries (the UNTREEIFY_THRESHOLD), it reverts to a plain linked list, because for small sizes a list is cheaper.

The two conditions matter — the tree only forms when both the bucket is long and the table is big enough. The capacity check keeps tiny maps from wasting effort on tree construction.

For interviews, the takeaway is the number to remember: 8. That is the threshold at which a HashMap bucket escalates from a linked list to a Red-Black tree, protecting against worst-case O(n) behavior.

2. Which condition must be met for a custom class to be used in a try-with-resources statement?

Answer: It must implement java.lang.AutoCloseable (or its sub-interface java.io.Closeable).

The try-with-resources statement is the modern way to manage resources that need closing:

try (MyResource r = new MyResource()) {
    r.use();
}

The compiler needs to know how to close the resource when the block exits — whether normally or via an exception. The contract that makes that possible is AutoCloseable, which declares the single method void close(). Any class implementing it can be used as a resource in try-with-resources, and the compiler generates the code to call close() automatically.

Closeable is a sub-interface of AutoCloseable, specialized for I/O streams. It throws IOException and is idempotent-friendly, but for the try-with-resources requirement, implementing either one is sufficient.

What you do not need: the class need not extend InputStream, need not be Serializable, and needs no particular constructor visibility beyond what you need to create it. The single condition is the AutoCloseable/Closeable contract, so the compiler can guarantee cleanup.

Answer:

It must implement java.lang.AutoCloseable (or its sub-interface java.io.Closeable).

The try-with-resources statement is the modern way to manage resources that need closing:

try (MyResource r = new MyResource()) {
    r.use();
}

The compiler needs to know how to close the resource when the block exits — whether normally or via an exception. The contract that makes that possible is AutoCloseable, which declares the single method void close(). Any class implementing it can be used as a resource in try-with-resources, and the compiler generates the code to call close() automatically.

Closeable is a sub-interface of AutoCloseable, specialized for I/O streams. It throws IOException and is idempotent-friendly, but for the try-with-resources requirement, implementing either one is sufficient.

What you do not need: the class need not extend InputStream, need not be Serializable, and needs no particular constructor visibility beyond what you need to create it. The single condition is the AutoCloseable/Closeable contract, so the compiler can guarantee cleanup.

3. What is the time complexity of basic operations (add, remove, contains) in a TreeSet?

Answer: O(log n).

The answer comes from what is underneath. TreeSet is backed by a TreeMap, and a TreeMap is implemented as a self-balancing Red-Black tree.

The tree keeps elements in sorted order by arranging them in a structure where, from any node, you go left for smaller values and right for larger ones. Because the tree is self-balancing, its height stays proportional to log n rather than degenerating into a long chain. Searching for an element therefore discards roughly half the remaining elements at each level, giving O(log n) for add, remove, and contains.

Compare that to a HashSet, which is backed by a HashMap. A HashSet gives O(1) average for the same operations, because it uses hashing to jump straight to a bucket. But the trade-off is ordering: a HashSet iterates in no particular order, while a TreeSet always iterates in sorted order and offers sorted-related operations like first(), last(), and range views.

The interview answer: choose TreeSet when you need sorted iteration and are happy with O(log n) operations; choose HashSet when speed matters more and order is irrelevant.

Answer:

O(log n).

The answer comes from what is underneath. TreeSet is backed by a TreeMap, and a TreeMap is implemented as a self-balancing Red-Black tree.

The tree keeps elements in sorted order by arranging them in a structure where, from any node, you go left for smaller values and right for larger ones. Because the tree is self-balancing, its height stays proportional to log n rather than degenerating into a long chain. Searching for an element therefore discards roughly half the remaining elements at each level, giving O(log n) for add, remove, and contains.

Compare that to a HashSet, which is backed by a HashMap. A HashSet gives O(1) average for the same operations, because it uses hashing to jump straight to a bucket. But the trade-off is ordering: a HashSet iterates in no particular order, while a TreeSet always iterates in sorted order and offers sorted-related operations like first(), last(), and range views.

The interview answer: choose TreeSet when you need sorted iteration and are happy with O(log n) operations; choose HashSet when speed matters more and order is irrelevant.

4. What is the key difference between fail-fast and fail-safe iterators?

Answer: Fail-fast iterators throw ConcurrentModificationException when the collection is structurally modified during iteration. Fail-safe iterators iterate over a snapshot or copy, so they never throw — but they may not reflect the latest changes.

Both are about the same danger: modifying a collection while iterating over it. The two families answer that danger in opposite ways.

Fail-fast iterators — found on ArrayList, HashMap, and other regular collections — watch the collection’s modification counter (modCount). Every structural change bumps it. The iterator records the counter when it starts, and on each step checks whether the collection has moved on. If it has, the iterator concludes that someone modified the collection behind its back and throws ConcurrentModificationException. The behavior is fail-fast because the iterator fails immediately rather than producing unpredictable results.

Fail-safe iterators — found on CopyOnWriteArrayList, ConcurrentHashMap, and other concurrent collections — sidestep the problem entirely by iterating over a snapshot or a stable internal structure. CopyOnWriteArrayList, for example, iterates over the array as it existed when iteration began. Concurrent modifications create a new copy; the iterator keeps walking the old one. No exception, but the iterator does not see changes made after it started.

The trade-off is the natural one: fail-fast gives you protection at the cost of exceptions; fail-safe gives you stability at the cost of not seeing live updates. When you genuinely need to modify a collection during iteration, the modern Java answer is removeIf() or iterating with an explicit Iterator.remove() — both of which stay in sync with the collection.

Answer:

Fail-fast iterators throw ConcurrentModificationException when the collection is structurally modified during iteration. Fail-safe iterators iterate over a snapshot or copy, so they never throw — but they may not reflect the latest changes.

Both are about the same danger: modifying a collection while iterating over it. The two families answer that danger in opposite ways.

Fail-fast iterators — found on ArrayList, HashMap, and other regular collections — watch the collection’s modification counter (modCount). Every structural change bumps it. The iterator records the counter when it starts, and on each step checks whether the collection has moved on. If it has, the iterator concludes that someone modified the collection behind its back and throws ConcurrentModificationException. The behavior is fail-fast because the iterator fails immediately rather than producing unpredictable results.

Fail-safe iterators — found on CopyOnWriteArrayList, ConcurrentHashMap, and other concurrent collections — sidestep the problem entirely by iterating over a snapshot or a stable internal structure. CopyOnWriteArrayList, for example, iterates over the array as it existed when iteration began. Concurrent modifications create a new copy; the iterator keeps walking the old one. No exception, but the iterator does not see changes made after it started.

The trade-off is the natural one: fail-fast gives you protection at the cost of exceptions; fail-safe gives you stability at the cost of not seeing live updates. When you genuinely need to modify a collection during iteration, the modern Java answer is removeIf() or iterating with an explicit Iterator.remove() — both of which stay in sync with the collection.

5. What happens if two distinct keys produce the SAME hash code in a HashMap?

Answer: Both key-value pairs are stored in the same bucket, chained together as a linked list (or a Red-Black tree in heavy-collision cases), and equals() is used to tell the keys apart.

A HashMap works by hashing each key to an array index — the “bucket.” Two keys landing in the same bucket is a collision, and it is completely normal. The map does not panic or overwrite; it stores both entries in that one bucket.

The bucket holds a chain of entries. When a new key arrives, the HashMap computes its hash, jumps to the bucket, and then walks the chain. At each entry it checks equals(): is this new key the same as an existing key? If yes — same key, same hash — the value is replaced. If no — a distinct key that merely collides — the new entry is appended to the chain.

So the two properties work together: hashCode() decides which bucket to search, and equals() decides which entry within the bucket matches. A good hashCode() distributes keys so buckets stay short; a bad one (all keys returning the same hash) piles everything into one bucket, degrading lookup from O(1) to O(n).

When a bucket grows long enough — 8 entries with a table capacity of at least 64 — Java 8 converts that chain into a Red-Black tree to keep lookups at O(log n). But the principle is unchanged: collisions share a bucket, and equals() is the arbiter inside it.

Answer:

Both key-value pairs are stored in the same bucket, chained together as a linked list (or a Red-Black tree in heavy-collision cases), and equals() is used to tell the keys apart.

A HashMap works by hashing each key to an array index — the “bucket.” Two keys landing in the same bucket is a collision, and it is completely normal. The map does not panic or overwrite; it stores both entries in that one bucket.

The bucket holds a chain of entries. When a new key arrives, the HashMap computes its hash, jumps to the bucket, and then walks the chain. At each entry it checks equals(): is this new key the same as an existing key? If yes — same key, same hash — the value is replaced. If no — a distinct key that merely collides — the new entry is appended to the chain.

So the two properties work together: hashCode() decides which bucket to search, and equals() decides which entry within the bucket matches. A good hashCode() distributes keys so buckets stay short; a bad one (all keys returning the same hash) piles everything into one bucket, degrading lookup from O(1) to O(n).

When a bucket grows long enough — 8 entries with a table capacity of at least 64 — Java 8 converts that chain into a Red-Black tree to keep lookups at O(log n). But the principle is unchanged: collisions share a bucket, and equals() is the arbiter inside it.

6. What is the default initial capacity and load factor for a standard HashMap?

Answer: Initial capacity 16, load factor 0.75.

The HashMap has two tuning dials.

Initial capacity is the number of buckets (the size of the internal array) created when the map is first built. The default is 16.

Load factor is the measure of how full the map is allowed to get before it resizes. The default is 0.75, meaning: when the map holds 75% of its capacity in entries — 12 entries for a 16-bucket map — it grows. On resize, the map typically doubles its capacity, rehashing and redistributing existing entries into the new buckets.

The trade-off behind the default is the usual one. A lower load factor (say 0.5) means fewer collisions and faster lookups, but more memory wasted and more frequent resizing. A higher load factor (say 0.9) uses memory more tightly but increases collision rates and slows lookups. 0.75 is the standard compromise, and in practice the JVM’s own HashMap-based structures — like HashSet and HashTable — use the same default.

The interview answer: capacity 16, load factor 0.75, resizing by doubling when 75% full.

Answer:

Initial capacity 16, load factor 0.75.

The HashMap has two tuning dials.

Initial capacity is the number of buckets (the size of the internal array) created when the map is first built. The default is 16.

Load factor is the measure of how full the map is allowed to get before it resizes. The default is 0.75, meaning: when the map holds 75% of its capacity in entries — 12 entries for a 16-bucket map — it grows. On resize, the map typically doubles its capacity, rehashing and redistributing existing entries into the new buckets.

The trade-off behind the default is the usual one. A lower load factor (say 0.5) means fewer collisions and faster lookups, but more memory wasted and more frequent resizing. A higher load factor (say 0.9) uses memory more tightly but increases collision rates and slows lookups. 0.75 is the standard compromise, and in practice the JVM’s own HashMap-based structures — like HashSet and HashTable — use the same default.

The interview answer: capacity 16, load factor 0.75, resizing by doubling when 75% full.

7. Which interface does TreeSet rely on to maintain sorted order when elements do NOT implement Comparable?

Answer: java.util.Comparator.

A TreeSet keeps its elements sorted at all times. But “sorted” is meaningless without a definition of ordering — some way to say which of two elements comes first. TreeSet gets that ordering from one of two sources:

1. Natural ordering — the elements implement Comparable (for example, String and the boxed number types do), and compareTo defines the order.
2. A supplied Comparator — when the elements don’t implement Comparable (or you want a different order than natural), you pass a Comparator to the TreeSet constructor. It then uses that comparator for every insertion, removal, and lookup.

So the answer is Comparator. It’s the mechanism of last resort and of customization: without Comparable on the elements and without a Comparator in the constructor, a TreeSet will throw a ClassCastException the moment it tries to insert an element, because it has no way to order anything.

Answer:

java.util.Comparator.

A TreeSet keeps its elements sorted at all times. But “sorted” is meaningless without a definition of ordering — some way to say which of two elements comes first. TreeSet gets that ordering from one of two sources:

1. Natural ordering — the elements implement Comparable (for example, String and the boxed number types do), and compareTo defines the order.
2. A supplied Comparator — when the elements don’t implement Comparable (or you want a different order than natural), you pass a Comparator to the TreeSet constructor. It then uses that comparator for every insertion, removal, and lookup.

So the answer is Comparator. It’s the mechanism of last resort and of customization: without Comparable on the elements and without a Comparator in the constructor, a TreeSet will throw a ClassCastException the moment it tries to insert an element, because it has no way to order anything.

8. What is the initial default capacity of an ArrayList created via new ArrayList<>()?

Answer: It’s created with an empty array buffer (capacity 0), and the array grows to the default capacity of 10 only on the first element insertion.

ArrayList is backed by an internal array, and it uses lazy initialization. When you write new ArrayList<>(), the constructor points the internal buffer at a shared empty array. No real backing storage of size 10 is allocated at construction time.

The capacity grows to 10 — the default initial capacity — on the first add() call. From there it keeps growing by roughly 1.5× whenever it fills up, copying elements into the larger array.

The distinction is subtle but real, and it’s a classic follow-up: the default capacity is 10, but the initial allocation is empty. new ArrayList<>() doesn’t hand you a 10-slot array; it gives you a lazily-grown structure that starts at 0 and jumps to 10 at first use.

Answer:

It’s created with an empty array buffer (capacity 0), and the array grows to the default capacity of 10 only on the first element insertion.

ArrayList is backed by an internal array, and it uses lazy initialization. When you write new ArrayList<>(), the constructor points the internal buffer at a shared empty array. No real backing storage of size 10 is allocated at construction time.

The capacity grows to 10 — the default initial capacity — on the first add() call. From there it keeps growing by roughly 1.5× whenever it fills up, copying elements into the larger array.

The distinction is subtle but real, and it’s a classic follow-up: the default capacity is 10, but the initial allocation is empty. new ArrayList<>() doesn’t hand you a 10-slot array; it gives you a lazily-grown structure that starts at 0 and jumps to 10 at first use.

9. Which set operation guarantees maintaining insertion order?

Answer: LinkedHashSet.

The three common Set implementations differ in one key dimension: ordering.

• HashSet — backed by a hash table. Fast O(1) lookups, but the iteration order is essentially arbitrary; it depends on hash codes and can change when the table resizes.
• TreeSet — backed by a Red-Black tree. Keeps elements in sorted order, whether by natural ordering or a supplied comparator. Not insertion order.
• LinkedHashSet — a HashSet augmented with a doubly linked list running through the entries. This records the order in which elements were inserted, so iteration yields them in insertion order — with the same hash-table performance.
• ConcurrentSkipListSet — a concurrent sorted set, also ordered, not insertion-ordered.

The answer is LinkedHashSet, the hybrid: hash-table speed plus deterministic, insertion-ordered iteration.

Answer:

LinkedHashSet.

The three common Set implementations differ in one key dimension: ordering.

• HashSet — backed by a hash table. Fast O(1) lookups, but the iteration order is essentially arbitrary; it depends on hash codes and can change when the table resizes.
• TreeSet — backed by a Red-Black tree. Keeps elements in sorted order, whether by natural ordering or a supplied comparator. Not insertion order.
• LinkedHashSet — a HashSet augmented with a doubly linked list running through the entries. This records the order in which elements were inserted, so iteration yields them in insertion order — with the same hash-table performance.
• ConcurrentSkipListSet — a concurrent sorted set, also ordered, not insertion-ordered.

The answer is LinkedHashSet, the hybrid: hash-table speed plus deterministic, insertion-ordered iteration.