The Collections Framework is a unified architecture for storing and manipulating groups of objects, providing standard interfaces, implementations, and algorithms.

List<String> list = new ArrayList<>();
list.add('A');
list.add('B');

Set<String> set = new HashSet<>();
set.add('A');
set.add('A');  // ignored, duplicates not allowed

Map<String, Integer> map = new HashMap<>();
map.put('age', 30);
map.put('age', 31);  // overwrites previous value

System.out.println(list);  // [A, B]
System.out.println(set);   // [A]
System.out.println(map);   // {age=31}

List<Integer> arrayList = new ArrayList<>();
arrayList.add(1);
arrayList.add(2);
arrayList.get(0);  // O(1) - direct index access

List<Integer> linkedList = new LinkedList<>();
linkedList.add(1);
linkedList.add(2);
linkedList.get(0);  // O(n) - traverses from head

// LinkedList implements Deque - efficient at both ends
LinkedList<Integer> deque = new LinkedList<>();
deque.addFirst(1);   // O(1)
deque.addLast(2);     // O(1)
deque.removeFirst();  // O(1)

// Rule of thumb: ArrayList for frequent random access/reads,
// LinkedList for frequent insertions/deletions at the ends

HashMap stores key-value pairs in an array of buckets. A key's hashCode() determines which bucket it goes into, and equals() resolves collisions within that bucket.

Map<String, Integer> map = new HashMap<>();
map.put('apple', 10);
map.put('banana', 20);

// get() follows the same hashCode -> bucket -> equals() process
Integer value = map.get('apple');  // 10

// Collisions - two different keys can land in the same bucket
// if their hashCode() values collide; HashMap resolves this by
// storing entries as a linked list (or a balanced tree since Java 8
// when a bucket has 8+ entries, for better worst-case performance)

// Java 8+ resizing: default capacity 16, load factor 0.75
// When size exceeds capacity * loadFactor, the table doubles and rehashes

// A poor hashCode() implementation (e.g. always returning the same value)
// makes ALL keys collide into one bucket, degrading HashMap to O(n) lookups
class BadKey {
    public int hashCode() { return 1; }  // terrible - all keys collide
}

Map<String, Integer> hashMap = new HashMap<>();
hashMap.put('c', 3); hashMap.put('a', 1); hashMap.put('b', 2);
System.out.println(hashMap);  // order not guaranteed

Map<String, Integer> linkedMap = new LinkedHashMap<>();
linkedMap.put('c', 3); linkedMap.put('a', 1); linkedMap.put('b', 2);
System.out.println(linkedMap);  // {c=3, a=1, b=2} - insertion order preserved

Map<String, Integer> treeMap = new TreeMap<>();
treeMap.put('c', 3); treeMap.put('a', 1); treeMap.put('b', 2);
System.out.println(treeMap);  // {a=1, b=2, c=3} - sorted by key

// TreeMap with a custom Comparator
Map<String, Integer> reverseMap = new TreeMap<>(Comparator.reverseOrder());
reverseMap.putAll(treeMap);
System.out.println(reverseMap);  // {c=3, b=2, a=1}

All three implement the Set interface (no duplicates), but differ in ordering guarantees and underlying implementation, since Set implementations are typically backed by a corresponding Map.

Set<String> hashSet = new HashSet<>();
hashSet.add('cherry'); hashSet.add('apple'); hashSet.add('banana');
System.out.println(hashSet);  // order not guaranteed

Set<String> linkedSet = new LinkedHashSet<>();
linkedSet.add('cherry'); linkedSet.add('apple'); linkedSet.add('banana');
System.out.println(linkedSet);  // [cherry, apple, banana] - insertion order

Set<String> treeSet = new TreeSet<>();
treeSet.add('cherry'); treeSet.add('apple'); treeSet.add('banana');
System.out.println(treeSet);  // [apple, banana, cherry] - sorted

// TreeSet additional navigation methods
TreeSet<Integer> numbers = new TreeSet<>(Arrays.asList(10, 20, 30, 40));
System.out.println(numbers.first());       // 10
System.out.println(numbers.last());          // 40
System.out.println(numbers.higher(20));      // 30 - smallest element > 20
System.out.println(numbers.lower(20));       // 10 - largest element < 20

// Comparable - defines natural ordering INSIDE the class
class Employee implements Comparable<Employee> {
    String name;
    int age;
    Employee(String name, int age) { this.name = name; this.age = age; }

    @Override
    public int compareTo(Employee other) {
        return this.age - other.age;  // natural order = by age
    }
}

List<Employee> employees = new ArrayList<>();
employees.add(new Employee('John', 30));
employees.add(new Employee('Jane', 25));
Collections.sort(employees);  // uses compareTo() - sorted by age

// Comparator - defines ordering OUTSIDE the class, multiple possible
Comparator<Employee> byName = (e1, e2) -> e1.name.compareTo(e2.name);
Comparator<Employee> byAgeDesc = (e1, e2) -> e2.age - e1.age;

employees.sort(byName);      // sort by name
employees.sort(byAgeDesc);   // sort by age, descending

// Chaining comparators (Java 8+)
Comparator<Employee> byNameThenAge = Comparator
    .comparing((Employee e) -> e.name)
    .thenComparing(e -> e.age);

Map<String, Integer> map = new HashMap<>();
map.put('apple', 10);
map.put('banana', 20);
map.put('cherry', 30);

// Method 1: entrySet() - most efficient, gets key AND value together
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    System.out.println(entry.getKey() + ': ' + entry.getValue());
}

// Method 2: keySet() - iterate keys, then look up values (extra lookup cost)
for (String key : map.keySet()) {
    System.out.println(key + ': ' + map.get(key));  // extra get() call per key
}

// Method 3: values() - iterate values only, no keys
for (Integer value : map.values()) {
    System.out.println(value);
}

// Method 4: forEach with lambda (Java 8+) - concise
map.forEach((key, value) -> System.out.println(key + ': ' + value));

// Method 5: Iterator - useful when you need to REMOVE entries during iteration
Iterator<Map.Entry<String, Integer>> it = map.entrySet().iterator();
while (it.hasNext()) {
    Map.Entry<String, Integer> entry = it.next();
    if (entry.getValue() < 15) {
        it.remove();  // safe removal during iteration
    }
}

// NEVER use map.remove() inside a for-each loop directly - causes
// ConcurrentModificationException; use Iterator.remove() instead

// Fail-fast example - throws exception
List<String> list = new ArrayList<>(Arrays.asList('A', 'B', 'C'));
for (String item : list) {
    if (item.equals('B')) {
        list.remove(item);  // ConcurrentModificationException!
    }
}
// Fail-fast iterators use a 'modCount' internally - if it changes
// unexpectedly during iteration, the exception is thrown

// SAFE alternative using Iterator.remove()
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    String item = it.next();
    if (item.equals('B')) {
        it.remove();  // safe - the iterator itself tracks this modification
    }
}

// Fail-safe example - no exception, but may miss recent updates
List<String> safeList = new CopyOnWriteArrayList<>(Arrays.asList('A', 'B', 'C'));
for (String item : safeList) {
    if (item.equals('B')) {
        safeList.remove(item);  // no exception - operates on a snapshot copy
    }
}
System.out.println(safeList);  // [A, C]

// ConcurrentHashMap - fail-safe for concurrent read/write scenarios
Map<String, Integer> concurrentMap = new ConcurrentHashMap<>();
concurrentMap.put('a', 1);
// safe to modify while another thread iterates, unlike HashMap

// Collection - the interface
Collection<String> collection = new ArrayList<>();
collection.add('A');
collection.size();

// Collections - the utility class, static methods
List<Integer> numbers = new ArrayList<>(Arrays.asList(5, 3, 1, 4, 2));

Collections.sort(numbers);              // [1, 2, 3, 4, 5]
Collections.reverse(numbers);           // [5, 4, 3, 2, 1]
Collections.max(numbers);               // 5
Collections.min(numbers);               // 1
Collections.shuffle(numbers);           // random order
int idx = Collections.binarySearch(numbers, 3);  // requires sorted list

// Creating immutable/unmodifiable collections
List<Integer> unmodifiable = Collections.unmodifiableList(numbers);
// unmodifiable.add(6);  // UnsupportedOperationException

List<Integer> emptyList = Collections.emptyList();
List<Integer> singleton = Collections.singletonList(42);

// Synchronized wrapper for thread-safety
List<Integer> syncList = Collections.synchronizedList(new ArrayList<>());

To use a custom class as a HashMap key correctly, you must override both hashCode() and equals() consistently - HashMap relies on both to locate and match keys.

class Point {
    int x, y;
    Point(int x, int y) { this.x = x; this.y = y; }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (!(obj instanceof Point)) return false;
        Point other = (Point) obj;
        return this.x == other.x && this.y == other.y;
    }

    @Override
    public int hashCode() {
        return Objects.hash(x, y);  // must be consistent with equals()
    }
}

Map<Point, String> map = new HashMap<>();
map.put(new Point(1, 2), 'First');

// Even though this is a DIFFERENT object, equals()/hashCode() make it match
System.out.println(map.get(new Point(1, 2)));  // 'First'

// WITHOUT overriding equals()/hashCode() (using default Object identity):
class BadPoint {
    int x, y;
    BadPoint(int x, int y) { this.x = x; this.y = y; }
    // uses default Object.equals() (reference equality) and hashCode()
}
Map<BadPoint, String> badMap = new HashMap<>();
badMap.put(new BadPoint(1, 2), 'First');
System.out.println(badMap.get(new BadPoint(1, 2)));  // null! different object, no match

// GOLDEN RULE: equal objects (per equals()) MUST have equal hashCode()
// values. Violating this breaks HashMap/HashSet lookups silently.