Collection (root interface)
├── List (순서 유지, 중복 허용)
│   ├── ArrayList
│   ├── LinkedList
│   └── Vector
├── Set (중복 불허)
│   ├── HashSet
│   ├── LinkedHashSet
│   └── TreeSet (SortedSet 구현)
└── Queue (FIFO/우선순위)
    ├── PriorityQueue
    └── Deque (양방향 큐)
        └── LinkedList

Map (별도 계층, Collection 미상속)
├── HashMap
├── LinkedHashMap
├── TreeMap (SortedMap 구현)
└── ConcurrentHashMap

// 내부 구조
Object[] elementData; // 실제 요소를 저장하는 배열
int size; // 현재 요소 개수

// Node 구조
private static class Node<E> {
    E item;
    Node<E> next;     // 다음 노드 참조
    Node<E> prev;     // 이전 노드 참조
}

transient Node<E> first;  // 첫 번째 노드
transient Node<E> last;   // 마지막 노드

transient Node<K,V>[] table;  // 버킷 배열

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;  // 다음 노드 (충돌 시)
}

static final int TREEIFY_THRESHOLD = 8;      // 트리로 변환되는 임계값
static final int UNTREEIFY_THRESHOLD = 6;    // 다시 리스트로 변환되는 임계값
static final int MIN_TREEIFY_CAPACITY = 64;  // 트리화 최소 용량

Linked List: O(n) 탐색
Red-Black Tree: O(log n) 탐색

최악의 경우 (모든 키가 같은 버킷):
- Java 7: O(n)
- Java 8+: O(log n)

public class HashSet<E> {
    private transient HashMap<E,Object> map;
    private static final Object PRESENT = new Object();  // 더미 값

    public HashSet() {
        map = new HashMap<>();
    }

    public boolean add(E e) {
        return map.put(e, PRESENT) == null;
    }

    public boolean contains(Object o) {
        return map.containsKey(o);
    }
}

public V get(Object key) {
    synchronized (mutex) { return m.get(key); }  // 전체 맵 락
}
public V put(K key, V value) {
    synchronized (mutex) { return m.put(key, value); }  // 전체 맵 락
}

// 읽기: volatile 읽기만 (락 없음)
public V get(Object key) { ... }

// 쓰기: CAS 시도 → 실패 시 해당 버킷만 synchronized
final V putVal(K key, V value, boolean onlyIfAbsent) {
    if (casTabAt(tab, i, null, newNode)) { /* 성공 */ }
    else { synchronized (existingNode) { /* 버킷 락 */ } }
}

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

Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
    String value = iterator.next();
    list.add("C");  // ConcurrentModificationException 발생
}

private class Itr implements Iterator<E> {
    int expectedModCount = modCount;

    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>();
list.add("A");
list.add("B");

Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
    String value = iterator.next();
    list.add("C");  // 예외 발생 안 함 (복사본에서 순회)
}

ConcurrentHashMap<String, String> map = new ConcurrentHashMap<>();
map.put("A", "1");
map.put("B", "2");

for (String key : map.keySet()) {
    if (key.equals("A")) {
        map.put("C", "3");  // 순회 중 추가해도 예외 없음
    }
    System.out.println(key);
}
// 출력: A, B (C는 안 나올 수도 있음)
// 또는: A, B, C (C가 나올 수도 있음)

// 컴파일 전
public class Box<T> {
    private T item;
}

// 컴파일 후 (T → Object)
public class Box {
    private Object item;
}

// 컴파일 전
public class NumberBox<T extends Number> {
    private T item;
}

// 컴파일 후 (T extends Number → Number)
public class NumberBox {
    private Number item;
}

// ? extends Number: Number 또는 그 하위(Integer, Double 등)
List<? extends Number> list1 = new ArrayList<Integer>();  // OK
List<? extends Number> list2 = new ArrayList<Object>();   // 컴파일 에러

// ? super Integer: Integer 또는 그 상위(Number, Object)
List<? super Integer> list3 = new ArrayList<Number>();    // OK
List<? super Integer> list4 = new ArrayList<Double>();    // 컴파일 에러

List<? extends Number> numbers = new ArrayList<Integer>();
Number num = numbers.get(0);  // OK: 읽기 가능
numbers.add(new Integer(1));  // 컴파일 에러: 쓰기 불가

List<? super Integer> integers = new ArrayList<Number>();
integers.add(new Integer(1)); // OK: 쓰기 가능
Integer i = integers.get(0);  // 컴파일 에러: Object로만 읽기 가능

List<String> strings = new ArrayList<>(); // 제네릭 타입 (명시적)
List raw = new ArrayList();               // Raw Type (비권장)

// 1. Primitive 타입 불가
Pair<int, char> p = new Pair<>(8, 'a');  // 컴파일 에러
Pair<Integer, Character> p = new Pair<>(8, 'a');  // OK

// 2. 타입 파라미터 인스턴스 생성 불가
E elem = new E();  // 컴파일 에러

// 3. 배열 생성 불가
new T[]  // 불가능
new List<String>[]  // 불가능

// 4. 정적 필드로 타입 파라미터 사용 불가
private static T os;  // 컴파일 에러

// 5. 제네릭 예외 클래스 불가
class MathException<T> extends Exception { }  // 컴파일 에러

// 6. 같은 raw 타입으로 소거되는 메서드 오버로드 불가
public void print(Set<String> strSet) { }
public void print(Set<Integer> intSet) { }  // 컴파일 에러

// 1. 인스턴스 메서드 = 'this' 락
public synchronized void method() {
    // 이 메서드를 호출한 '각 객체(this)' 기준으로 잠깁니다.
    // obj1.method()와 obj2.method()는 서로 다른 락을 쓰므로 동시에 실행 가능합니다.
}

// 2. 정적(static) 메서드 = 'Class' 락
public static synchronized void staticMethod() {
    // '클래스 그 자체(Class 객체)' 기준으로 잠깁니다.
    // 메모리에 클래스는 하나뿐이므로, 이 클래스의 모든 정적 동기화 메서드는 
    // 한 번에 하나의 스레드만 접근할 수 있는 '전역 락'처럼 동작합니다.
}

// 3. 블록 동기화
public void logData(String data) {
    // (A) 준비 작업: 오래 걸리지만 동시 실행 가능 (락 불필요)
    String formatted = complexPreparation(data); 

    // (B) 락 블록: 꼭 필요한 부분만 잠금 (성능 향상)
    synchronized(this) {
        // 'this'는 이 메서드를 호출한 '바로 그 객체'만 잠급니다. (다른 객체와 무관)
        list.add(formatted);
    }
}

MyClass a = new MyClass();
MyClass b = new MyClass();

// 1. 인스턴스 메서드 (this 락)
// 객체 a와 b는 서로 다른 락을 가지므로 '동시에' 실행됩니다.
new Thread(() -> a.method()).start();
new Thread(() -> b.method()).start(); 

// 2. 정적 메서드 (Class 락)
// MyClass의 락은 전역적으로 하나뿐이므로, 뒤에 온 스레드는 앞 스레드가 끝날 때까지 '대기'해야 합니다.
new Thread(() -> MyClass.staticMethod()).start();
new Thread(() -> MyClass.staticMethod()).start(); 

public synchronized void methodA() {
    // 락 획득!
    methodB(); 
}

public synchronized void methodB() {
    // 이미 methodA에서 락을 잡았지만, 
    // "어? 너 아까 그 스레드네? 열쇠 가지고 있지?" 하고 통과시켜줌.
    // 만약 재진입이 안 된다면 여기서 자기 자신 때문에 데드락에 걸림.
}

private boolean done = false;  // volatile 없음

// Thread 1
while (!done) { }  // done이 true로 변경되어도 못 볼 수 있음

// Thread 2
done = true;  // 다른 스레드에 즉시 보이지 않을 수 있음

private int count = 0;
count++;  // 읽기, 증가, 쓰기의 세 단계 - 원자적이지 않음

private volatile int count = 0;
count++;  // 여전히 race condition

AtomicInteger counter = new AtomicInteger(0);

// 원자적 증가
int newValue = counter.incrementAndGet();

// CAS(Compare-And-Set) 연산
boolean success = counter.compareAndSet(expectedValue, newValue);

public class AtomicInteger {
    private volatile int value;  // volatile로 선언

    public final int incrementAndGet() {
        int prev, next;
        do {
            prev = get();           // 1. 메인 메모리에서 현재 값 읽기 (volatile)
            next = prev + 1;        // 2. 새 값 계산
        } while (!compareAndSet(prev, next));  // 3. CAS 실패하면 재시도
        return next;
    }
}

private static final ThreadLocal<User> currentUser =
    ThreadLocal.withInitial(() -> new User());

public static User getCurrentUser() {
    return currentUser.get();
}

try {
    threadLocal.set(value);
    // 작업 수행
} finally {
    threadLocal.remove();  // 반드시 정리
}

// synchronized: 락을 얻을 때까지 무한 대기
synchronized (lock) { }

// ReentrantLock: 1초 기다려보고 안 되면 포기
if (lock.tryLock(1, TimeUnit.SECONDS)) { }

// ReentrantLock: 락이 가능하면 획득, 불가능하면 즉시 false 반환
if (lock.tryLock()) { }

// synchronized: 락을 얻을 때까지 무조건 대기. 중간에 깨울 방법 없음
synchronized (lock) { }

// ReentrantLock: 대기 중에 interrupt() 호출하면 대기를 멈추고 예외 발생
try {
    lock.lockInterruptibly();
} catch (InterruptedException e) {
    // 다른 스레드가 interrupt() 호출하면 여기로 옴
}

// 공유 버퍼 (생산자가 넣고, 소비자가 꺼내는 큐)
LinkedList<String> buffer = new LinkedList<>();

// synchronized: notifyAll()하면 모든 대기 스레드가 깨어남 (생산자/소비자 구분 불가)
synchronized (buffer) {
    while (buffer.isEmpty()) {
        buffer.wait();  // 버퍼가 비었으면 대기
    }
    // 소비
}
synchronized (buffer) {
    // 생산
    buffer.notifyAll();  // 누구를 깨우는지 구분 불가
}

// ReentrantLock: Condition으로 대기 큐를 분리
ReentrantLock lock = new ReentrantLock();
Condition notFull = lock.newCondition();   // 생산자용 대기 큐
Condition notEmpty = lock.newCondition();  // 소비자용 대기 큐

// 생산자
lock.lock();
try {
    while (buffer.isFull()) {
        notFull.await();  // "버퍼가 안 찼다" 조건 대기
    }
    buffer.add(item);
    notEmpty.signal();    // 소비자만 깨움
} finally {
    lock.unlock();
}

// 소비자
lock.lock();
try {
    while (buffer.isEmpty()) {
        notEmpty.await();  // "버퍼가 안 비었다" 조건 대기
    }
    item = buffer.remove();
    notFull.signal();      // 생산자만 깨움
} finally {
    lock.unlock();
}

// synchronized: 블록 끝나면 자동 unlock
synchronized (lock) { }

// ReentrantLock: 직접 unlock 호출 필수 (try-finally 패턴)
lock.lock();
try { } finally { lock.unlock(); }

ExecutorService executor = Executors.newFixedThreadPool(4);

Future<String> future = executor.submit(() -> "Task result");

executor.shutdown();
executor.awaitTermination(60, TimeUnit.SECONDS);

@Retention(RetentionPolicy.RUNTIME) // 실행 중에도 읽어야 하니까 RUNTIME 필수!
@Target(ElementType.METHOD)         // 메서드 위에만 붙이세요!
public @interface MyAnnotation { ... }

@Retention(RetentionPolicy.RUNTIME)
@Target(ElementType.METHOD)
public @interface PerformanceTest {
    int iterations() default 1;
    long timeout() default 1000L;
    String description() default "";
}

// 사용
@PerformanceTest(iterations = 1000, timeout = 5000L)
public void testMethod() { }