Iterable
                       │
                   Collection
                  /    |     \
               List   Set    Queue
              / | \    |  \     |  \
     ArrayList  |  Vector  HashSet  TreeSet  PriorityQueue  ArrayDeque
          LinkedList    Stack   LinkedHashSet

                    Map (separate hierarchy)
                   / | \
            HashMap  TreeMap  Hashtable
               |
         LinkedHashMap
               |
      ConcurrentHashMap

Key interfaces:
- Collection → root interface (add, remove, contains)
- List → ordered, allows duplicates, index access
- Set → no duplicates
- Queue → FIFO ordering
- Map → key-value pairs (NOT part of Collection interface)

// This hierarchy question is asked in 80% of interviews.
// Draw it from memory.

Feature        ArrayList       LinkedList      Vector
──────────     ──────────      ──────────      ──────────
Internal       Dynamic array   Doubly linked   Dynamic array
                               list
Access         O(1) random     O(n) random     O(1) random
Insert/Delete  O(n) middle     O(1) if at node O(n) middle
Thread-safe    No              No              Yes (synchronized)
Growth         50% increase    N/A             100% increase
Memory         Less overhead   More (pointers) Less overhead
Iterator       Fail-fast       Fail-fast       Fail-fast

// When to use:
// ArrayList → default choice (95% of cases)
// LinkedList → frequent insert/delete at both ends (Queue)
// Vector → legacy, use Collections.synchronizedList() instead

// ArrayList internal working:
// Default capacity: 10
// When full: creates new array of size (old * 1.5)
// Copies all elements to new array
// This is why add() is amortized O(1) but worst case O(n)

ArrayList<String> list = new ArrayList<>(50); // set initial capacity
// If you know the size, set initial capacity to avoid resizing

// Method 1: Collections.synchronizedList()
List<String> syncList = Collections.synchronizedList(
    new ArrayList<>()
);
// Wraps every method with synchronized block
// Must manually synchronize during iteration:
synchronized (syncList) {
    for (String s : syncList) {
        System.out.println(s);
    }
}

// Method 2: CopyOnWriteArrayList (preferred for read-heavy)
List<String> cowList = new CopyOnWriteArrayList<>();
// Creates a new copy of array on every write
// Reads are lock-free (fast)
// Writes are expensive (copies entire array)
// Best for: read-heavy, write-rare scenarios (listeners)

// Method 3: Vector (legacy — avoid)
Vector<String> vector = new Vector<>();
// Every method is synchronized — too much overhead

// HashMap = array of buckets (Node<K,V>[])
// Each bucket = linked list (or tree if > 8 nodes)

// PUT operation:
// 1. key.hashCode() → raw hash
// 2. hash = hash ^ (hash >>> 16) → spread bits
// 3. index = hash & (capacity - 1) → bucket index
// 4. If bucket empty → store Node directly
// 5. If bucket has nodes:
//    a. Check each node: if key.equals(existingKey)
//       → update value (replace)
//    b. If no match → add to end of linked list
//    c. If list length > 8 → convert to red-black tree

// GET operation:
// 1. Calculate hash → find bucket index
// 2. Traverse bucket (list or tree)
// 3. Use equals() to find exact key match

// Key constants:
// Default capacity: 16
// Load factor: 0.75 (resize when 75% full)
// Treeify threshold: 8 (list → tree)
// Untreeify threshold: 6 (tree → list)

// Resize (rehashing):
// When size > capacity * loadFactor
// New capacity = old capacity * 2
// ALL entries are rehashed to new buckets
// This is expensive — set initial capacity if possible

HashMap<String, Integer> map = new HashMap<>(100, 0.75f);

Feature          HashMap         Hashtable       ConcurrentHashMap
──────────       ──────────      ──────────      ──────────────────
Thread-safe      No              Yes (all sync)  Yes (segment-level)
Null keys        1 null key      No null keys    No null keys
Null values      Multiple        No null values  No null values
Performance      Fastest         Slowest         Fast (concurrent)
Iterator         Fail-fast       Fail-fast       Weakly consistent
Since            Java 1.2        Java 1.0        Java 1.5

// ConcurrentHashMap internal (Java 8+):
// Uses CAS (Compare-And-Swap) + synchronized blocks
// Only locks the specific bucket being modified
// Multiple threads can read/write different buckets simultaneously
// Much better than Hashtable which locks the entire map

// When to use:
// HashMap → single-threaded (default choice)
// ConcurrentHashMap → multi-threaded
// Hashtable → never (legacy)

// Comparable — natural ordering (inside the class)
class Student implements Comparable<Student> {
    String name;
    int marks;
    
    @Override
    public int compareTo(Student other) {
        return this.marks - other.marks; // ascending by marks
    }
}
Collections.sort(students); // uses compareTo()

// Comparator — custom ordering (outside the class)
Comparator<Student> byName = (s1, s2) -> 
    s1.name.compareTo(s2.name);
Collections.sort(students, byName);

// Multiple sort criteria:
Comparator<Student> byMarksDesc = 
    Comparator.comparingInt(Student::getMarks).reversed();
Comparator<Student> byNameThenMarks = 
    Comparator.comparing(Student::getName)
              .thenComparingInt(Student::getMarks);

// Key difference:
// Comparable = single natural order, modifies the class
// Comparator = multiple custom orders, external to class

// Fail-fast: throws ConcurrentModificationException
// if collection is modified during iteration
// ArrayList, HashMap, HashSet use fail-fast iterators

List<String> list = new ArrayList<>(Arrays.asList("a","b","c"));
for (String s : list) {
    list.remove(s); // ConcurrentModificationException!
}

// Safe way to remove during iteration:
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    if (it.next().equals("b")) {
        it.remove(); // safe — uses iterator's remove()
    }
}

// Fail-safe: works on a COPY of the collection
// CopyOnWriteArrayList, ConcurrentHashMap use fail-safe
// No exception, but may not reflect latest changes

CopyOnWriteArrayList<String> cowList = new CopyOnWriteArrayList<>();
// Iterating while modifying is safe here