Interview Questions
The Java Collections Framework is a unified architecture for representing and manipulating collections. The hierarchy starts with the Collection interface, which branches into List (ordered), Set (unique elements), and Queue (ordered for processing) interfaces. Map interface is separate but related. Each interface has multiple implementations like ArrayList, HashSet, LinkedList, HashMap, etc., offering different performance characteristics and functionalities.
ArrayList uses a dynamic array with fast random access (O(1)) but slower insertions/deletions in the middle (O(n)). LinkedList uses doubly-linked list with O(1) insertions/deletions at known positions but O(n) random access. Use ArrayList for frequent random access and rare modifications, LinkedList for frequent insertions/deletions and sequential access. ArrayList is generally more memory-efficient due to less overhead per element.
HashSet offers O(1) operations using hash table, doesn't maintain insertion order. LinkedHashSet maintains insertion order using doubly-linked list while keeping O(1) operations. TreeSet maintains natural order or custom comparator order using Red-Black tree with O(log n) operations. Use HashSet for fastest performance, LinkedHashSet when order matters, TreeSet when sorted order is needed.
Main differences: 1) HashMap is non-synchronized while Hashtable is synchronized, 2) HashMap allows null keys and values, Hashtable doesn't, 3) HashMap is generally faster. In modern Java, HashMap is preferred with Collections.synchronizedMap() or ConcurrentHashMap for thread-safety. Hashtable is legacy and shouldn't be used in new code.
equals() determines object equality while hashCode() provides the hash value for hash-based collections. They must follow the contract: equal objects must have equal hash codes, but equal hash codes don't guarantee equal objects. When overriding one, always override both. Implementation should be consistent, use significant fields, and maintain symmetry and transitivity in equals().
ConcurrentHashMap uses segment-level locking (pre-Java 8) or node-level locking (Java 8+) allowing multiple threads to write simultaneously to different segments/nodes. Synchronized HashMap locks the entire map for each operation. ConcurrentHashMap provides better scalability, doesn't block reads, and offers atomic operations like putIfAbsent(). It never throws ConcurrentModificationException during iteration.
Fail-fast iterators (like in ArrayList, HashMap) throw ConcurrentModificationException if collection is modified while iterating, except through iterator's methods. Fail-safe iterators (like in CopyOnWriteArrayList, ConcurrentHashMap) work on a copy of collection, allowing modifications but potentially showing stale data. Fail-fast ensures data consistency, fail-safe prioritizes non-blocking iteration.
NavigableMap extends SortedMap to provide navigation methods: floorKey, ceilingKey, higherKey, lowerKey, etc. TreeMap implements it. Use cases include: range queries, finding closest matches, maintaining ordered key-value pairs with efficient navigation. Useful for applications like price ranges, time series data, or any ordered mapping requiring nearest-match queries.
PriorityQueue is a heap-based implementation maintaining elements in natural or custom order, offering O(log n) insertion and O(1) peek/poll of highest/lowest priority element. Deque (interface implemented by ArrayDeque, LinkedList) is a double-ended queue allowing insertion/removal at both ends in O(1). Use PriorityQueue for priority-based processing, Deque for stack/queue operations.
Methods include: 1) for-each loop (clean, preferred for simple iteration), 2) Iterator (allows removal, required for Map), 3) ListIterator (bidirectional for Lists), 4) traditional for loop (when index needed), 5) streams (functional approach, parallel processing). Performance varies: traditional for loop fastest for ArrayList, Iterator best for LinkedList, streams overhead justified by parallel processing or complex operations.
Load factor determines when HashMap resizes (default 0.75). Lower value means less collisions but more memory, higher means better memory usage but more collisions. Resize operation is expensive (O(n)). Change default when: 1) Memory critical (increase), 2) Many collisions expected (decrease), 3) Performance critical with known size (adjust initial capacity instead).
WeakHashMap allows keys to be garbage collected when no strong references exist. Entry is removed automatically during next operation. Use cases: 1) Implementing caches that shouldn't prevent garbage collection, 2) Storing metadata about objects without memory leaks, 3) Maintaining mappings that shouldn't affect object lifecycle. Important for memory management in long-running applications.
Immutable collections are unmodifiable after creation. Creation methods: 1) Collections.unmodifiableXXX() (wrapper, backing collection still mutable), 2) List.of(), Set.of(), Map.of() (Java 9+, truly immutable), 3) Collectors.toUnmodifiableXXX() (for streams), 4) ImmutableList etc. in Guava. Benefits include thread safety, security, and preventing accidental modifications.
BlockingQueue adds blocking operations to Queue: put() blocks when full, take() blocks when empty. Implementations (ArrayBlockingQueue, LinkedBlockingQueue) are thread-safe. Used in producer-consumer pattern where producers add items (blocking if full) and consumers remove items (blocking if empty). Provides built-in synchronization and eliminates need for explicit coordination.
Collections.sort() uses modified mergesort (Timsort since Java 7) for Objects, and quicksort for primitives. Time complexity O(n log n), space complexity O(n) for objects (due to merge sort's need for temporary array), O(log n) for primitives. Stable sort for objects, unstable for primitives. Elements must be Comparable or a Comparator must be provided.
Map provides three views: 1) keySet() returns Set of keys, 2) values() returns Collection of values, 3) entrySet() returns Set of key-value pairs. Views are backed by map - modifications reflect in original map. Useful for iteration, bulk operations, and stream operations. Performance varies by implementation (e.g., HashMap vs TreeMap).
EnumSet is specialized Set implementation for enum types using bit vector internally. Offers constant time operations, very memory efficient (one long per 64 enum constants). All operations are thread-safe due to atomic bit operations. Can't use with null values. Preferred over HashSet when working with enums due to superior performance and memory usage.
Concurrent collections (ConcurrentHashMap, CopyOnWriteArrayList, ConcurrentLinkedQueue) are thread-safe collections designed for concurrent access. Use when: 1) Multiple threads access collection, 2) Need better scalability than synchronized collections, 3) Want to avoid explicit synchronization. Trade-offs include slightly lower single-thread performance and possibly inconsistent iterations.
Custom objects must either implement Comparable or be used with a Comparator, otherwise ClassCastException is thrown. TreeSet/TreeMap use natural ordering (Comparable) or custom ordering (Comparator) to maintain sorted order. Comparison must be consistent with equals() to prevent unexpected behavior. Important for maintaining the collection's invariants.
Spliterator (Java 8+) is used for traversing and partitioning elements, especially in parallel streams. Provides estimates of size, characteristics (ORDERED, SORTED, etc.), and splitting capabilities. Each collection provides specialized implementation optimized for its structure. Important for parallel processing and stream operations performance.