Tìm Hiểu Sâu: Java Collections Framework

Collection (interface)
├── List (interface)
│   ├── ArrayList
│   ├── LinkedList
│   └── Vector (legacy, synchronized)
│
├── Set (interface)
│   ├── HashSet
│   ├── LinkedHashSet
│   └── TreeSet (SortedSet)
│
└── Queue (interface)
    ├── ArrayDeque
    ├── PriorityQueue
    └── LinkedList
 
Map (interface, separate from Collection)
├── HashMap
├── LinkedHashMap
├── TreeMap (SortedMap)
├── Hashtable (legacy, synchronized)
└── ConcurrentHashMap (thread-safe)

List<String> names = new ArrayList<>(100); // Initial capacity
 
// O(1) - Add to end (amortized)
names.add("Alice");
names.add("Bob");
 
// O(1) - Random access by index
String first = names.get(0);
 
// O(n) - Insert in middle (requires shifting)
names.add(1, "Charlie");
 
// O(n) - Search by value
boolean hasAlice = names.contains("Alice");
 
// O(n) - Remove by index (requires shifting)
names.remove(0);

// Simplified ArrayList internals
public class ArrayList<E> {
    private Object[] elementData;
    private int size;
    
    public boolean add(E e) {
        ensureCapacity(size + 1);
        elementData[size++] = e;
        return true;
    }
    
    private void ensureCapacity(int minCapacity) {
        if (minCapacity > elementData.length) {
            // Grow by ~50% (old capacity + old capacity >> 1)
            int newCapacity = elementData.length + (elementData.length >> 1);
            elementData = Arrays.copyOf(elementData, newCapacity);
        }
    }
}

// ✅ NÊN: Chỉ định capacity ban đầu nếu biết
List<Item> items = new ArrayList<>(expectedSize);
 
// ✅ NÊN: Sử dụng cho các scenario truy cập ngẫu nhiên
for (int i = 0; i < items.size(); i++) {
    process(items.get(i)); // O(1) access
}
 
// ❌ KHÔNG NÊN: Thường xuyên chèn vào giữa
for (int i = 0; i < 1000; i++) {
    items.add(0, newItem); // O(n) mỗi lần - chậm!
}

LinkedList<String> queue = new LinkedList<>();
 
// O(1) - Add to either end
queue.addFirst("First");
queue.addLast("Last");
 
// O(1) - Remove from either end
String first = queue.removeFirst();
String last = queue.removeLast();
 
// O(n) - Random access by index
String item = queue.get(5); // Traverses from head or tail
 
// O(n) - Search
boolean found = queue.contains("item");

// Simplified LinkedList node
private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;
}

// Sử dụng ArrayList khi:
// - Truy cập ngẫu nhiên thường xuyên
// - Thêm vào cuối là thao tác chính
// - Hiệu quả bộ nhớ quan trọng
// - Bạn iterate với vòng lặp dựa trên index
List<String> names = new ArrayList<>();
 
// Sử dụng LinkedList khi:
// - Implement queue/deque
// - Thường xuyên thêm/xóa ở đầu
// - Sử dụng iterator để xóa trong khi duyệt
Deque<Task> taskQueue = new LinkedList<>();

Set<String> uniqueUsers = new HashSet<>();
 
// O(1) - Add element
uniqueUsers.add("alice");
uniqueUsers.add("bob");
uniqueUsers.add("alice"); // Bị bỏ qua - đã tồn tại
 
// O(1) - Check membership
boolean hasAlice = uniqueUsers.contains("alice");
 
// O(1) - Remove
uniqueUsers.remove("bob");
 
// Unordered iteration
for (String user : uniqueUsers) {
    System.out.println(user); // Thứ tự không được đảm bảo
}

// Simplified HashSet internals
public class HashSet<E> {
    private transient HashMap<E, Object> map;
    private static final Object PRESENT = new Object();
    
    public boolean add(E e) {
        return map.put(e, PRESENT) == null;
    }
}

// ✅ NÊN: Sử dụng các đối tượng immutable hoặc effectively immutable
Set<String> names = new HashSet<>();
names.add("Alice");
 
// ❌ KHÔNG NÊN: Sửa đổi đối tượng sau khi thêm
class Person {
    String name;
    
    @Override
    public int hashCode() {
        return name.hashCode();
    }
}
 
Person p = new Person("Alice");
Set<Person> people = new HashSet<>();
people.add(p);
p.name = "Bob"; // ⚠️ PHÁ VỠ SET - không thể tìm thấy 'p' nữa!

Set<String> orderedUsers = new LinkedHashSet<>();
orderedUsers.add("charlie");
orderedUsers.add("alice");
orderedUsers.add("bob");
 
// Iteration theo thứ tự chèn
for (String user : orderedUsers) {
    System.out.println(user); // charlie, alice, bob
}

Set<Integer> scores = new TreeSet<>();
scores.add(85);
scores.add(92);
scores.add(78);
 
// Iteration theo thứ tự đã sắp xếp
for (int score : scores) {
    System.out.println(score); // 78, 85, 92
}
 
// Range operations
SortedSet<Integer> highScores = ((TreeSet<Integer>) scores).tailSet(80);
System.out.println(highScores); // [85, 92]

// Các phần tử phải là Comparable HOẶC cung cấp Comparator
Set<Person> people = new TreeSet<>(
    Comparator.comparing(Person::getLastName)
        .thenComparing(Person::getFirstName)
);

Map<String, Integer> ages = new HashMap<>();
 
// O(1) - Put key-value
ages.put("Alice", 30);
ages.put("Bob", 25);
ages.put("Alice", 31); // Ghi đè giá trị trước
 
// O(1) - Get by key
Integer aliceAge = ages.get("Alice");
 
// O(1) - Check key existence
boolean hasAlice = ages.containsKey("Alice");
 
// O(n) - Check value existence (không hiệu quả!)
boolean hasAge30 = ages.containsValue(30);
 
// O(1) - Remove by key
ages.remove("Bob");
 
// Iterate over entries
for (Map.Entry<String, Integer> entry : ages.entrySet()) {
    System.out.println(entry.getKey() + ": " + entry.getValue());
}

// Simplified HashMap internals
public class HashMap<K, V> {
    transient Node<K, V>[] table; // Array of buckets
    
    static class Node<K, V> {
        final int hash;
        final K key;
        V value;
        Node<K, V> next; // Chain for collisions
    }
    
    public V put(K key, V value) {
        int hash = hash(key);
        int bucket = hash & (table.length - 1);
        // Handle collision with chaining or tree
        // ...
    }
}

// ✅ NÊN: Chỉ định capacity ban đầu cho các map lớn
Map<String, User> users = new HashMap<>(10000);
 
// ✅ NÊN: Sử dụng compute methods để cập nhật atomic
map.compute("key", (k, v) -> v == null ? 1 : v + 1);
 
// ✅ NÊN: Sử dụng getOrDefault để tránh kiểm tra null
int count = map.getOrDefault("key", 0);
 
// ❌ KHÔNG NÊN: Sử dụng containsKey + get (hai lần tra cứu)
if (map.containsKey("key")) {
    return map.get("key"); // Tra cứu lần thứ hai!
}
 
// ✅ NÊN: Tra cứu một lần
String value = map.get("key");
if (value != null) {
    return value;
}

Map<String, Integer> scores = new HashMap<>();
 
// putIfAbsent - chỉ thêm nếu key không tồn tại
scores.putIfAbsent("Alice", 100);
 
// computeIfAbsent - khởi tạo lazy
Map<String, List<String>> groups = new HashMap<>();
groups.computeIfAbsent("admin", k -> new ArrayList<>()).add("Alice");
 
// merge - kết hợp các giá trị
scores.merge("Bob", 10, Integer::sum); // Thêm 10 vào giá trị hiện có

Map<String, Integer> cache = new LinkedHashMap<>();
cache.put("first", 1);
cache.put("second", 2);
cache.put("third", 3);
 
// Iteration theo thứ tự chèn
cache.forEach((k, v) -> System.out.println(k + ": " + v));
// Output: first: 1, second: 2, third: 3

// LinkedHashMap theo access-order (LRU cache)
Map<String, String> lruCache = new LinkedHashMap<>(16, 0.75f, true) {
    @Override
    protected boolean removeEldestEntry(Map.Entry<String, String> eldest) {
        return size() > MAX_ENTRIES;
    }
};
 
lruCache.put("A", "1");
lruCache.put("B", "2");
lruCache.put("C", "3");
lruCache.get("A"); // Di chuyển A đến cuối (được sử dụng gần đây nhất)
lruCache.put("D", "4"); // Loại bỏ B (ít được sử dụng gần đây nhất)

TreeMap<Integer, String> sortedMap = new TreeMap<>();
sortedMap.put(3, "three");
sortedMap.put(1, "one");
sortedMap.put(2, "two");
 
// Iteration theo thứ tự key
sortedMap.forEach((k, v) -> System.out.println(k + ": " + v));
// Output: 1: one, 2: two, 3: three
 
// Range queries
SortedMap<Integer, String> subMap = sortedMap.subMap(1, 3); // [1, 3)
Map.Entry<Integer, String> firstEntry = sortedMap.firstEntry();
Map.Entry<Integer, String> lastEntry = sortedMap.lastEntry();
 
// Ceiling/Floor operations
Integer ceiling = sortedMap.ceilingKey(2); // Key nhỏ nhất >= 2
Integer floor = sortedMap.floorKey(2);     // Key lớn nhất <= 2

Map<String, Integer> concurrentMap = new ConcurrentHashMap<>();
 
// Các thao tác an toàn luồng không cần synchronization bên ngoài
concurrentMap.put("key", 1);
concurrentMap.compute("key", (k, v) -> v == null ? 1 : v + 1);
 
// Bulk operations
concurrentMap.forEach(10, (k, v) -> {
    // Parallel forEach với ngưỡng parallelism
    System.out.println(k + ": " + v);
});
 
// Atomic updates
concurrentMap.computeIfAbsent("counter", k -> 0);
concurrentMap.computeIfPresent("counter", (k, v) -> v + 1);

// ConcurrentHashMap scale tốt hơn với nhiều thread
// Single thread: HashMap ~= ConcurrentHashMap
// Multiple threads: ConcurrentHashMap >> Collections.synchronizedMap(HashMap)

Deque<String> deque = new ArrayDeque<>();
 
// Sử dụng như Queue (FIFO)
deque.offer("first");
deque.offer("second");
String first = deque.poll(); // "first"
 
// Sử dụng như Stack (LIFO)
deque.push("A");
deque.push("B");
String top = deque.pop(); // "B"
 
// Thao tác hai đầu
deque.addFirst("head");
deque.addLast("tail");
String head = deque.removeFirst();
String tail = deque.removeLast();

// Ưu điểm của ArrayDeque:
// 1. Memory overhead thấp hơn (không có con trỏ node)
// 2. Locality cache tốt hơn (mảng liên tiếp)
// 3. Chèn/xóa nhanh hơn ở các đầu
 
Deque<Integer> deque = new ArrayDeque<>(); // ✅ Được ưu tiên
LinkedList<Integer> list = new LinkedList<>(); // ❌ Ít hiệu quả hơn với vai trò deque

// Min-heap mặc định (phần tử nhỏ nhất trước)
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.offer(5);
minHeap.offer(1);
minHeap.offer(3);
 
System.out.println(minHeap.poll()); // 1
System.out.println(minHeap.poll()); // 3
System.out.println(minHeap.poll()); // 5
 
// Max-heap với comparator tùy chỉnh
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(
    Comparator.reverseOrder()
);
 
// Đối tượng tùy chỉnh với priority
class Task implements Comparable<Task> {
    String name;
    int priority;
    
    @Override
    public int compareTo(Task other) {
        return Integer.compare(this.priority, other.priority);
    }
}
 
PriorityQueue<Task> taskQueue = new PriorityQueue<>();
taskQueue.offer(new Task("Low", 3));
taskQueue.offer(new Task("High", 1));
taskQueue.offer(new Task("Medium", 2));
 
Task urgent = taskQueue.poll(); // Trả về "High" (priority 1)

// ❌ BẪY: Thứ tự iteration KHÔNG phải thứ tự ưu tiên!
PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(5);
pq.offer(1);
pq.offer(3);
 
for (Integer i : pq) {
    System.out.println(i); // KHÔNG được đảm bảo là 1, 3, 5!
}
 
// ✅ ĐÚNG: Sử dụng poll() cho thứ tự ưu tiên
while (!pq.isEmpty()) {
    System.out.println(pq.poll()); // 1, 3, 5 (được đảm bảo)
}

import java.util.concurrent.*;
 
// Bounded queue - block khi đầy
BlockingQueue<String> queue = new ArrayBlockingQueue<>(10);
 
// Producer thread
new Thread(() -> {
    try {
        queue.put("item"); // Block nếu queue đầy
    } catch (InterruptedException e) {
        Thread.currentThread().interrupt();
    }
}).start();
 
// Consumer thread
new Thread(() -> {
    try {
        String item = queue.take(); // Block nếu queue rỗng
    } catch (InterruptedException e) {
        Thread.currentThread().interrupt();
    }
}).start();

Cần cặp key-value?
├─ CÓ → Map
│  ├─ Cần sắp xếp? → TreeMap
│  ├─ Cần thứ tự chèn? → LinkedHashMap
│  ├─ Thread-safe? → ConcurrentHashMap
│  └─ Mặc định → HashMap
│
└─ KHÔNG → Collection
   ├─ Cần tính duy nhất?
   │  ├─ CÓ → Set
   │  │  ├─ Cần sắp xếp? → TreeSet
   │  │  ├─ Cần thứ tự chèn? → LinkedHashSet
   │  │  └─ Mặc định → HashSet
   │  │
   │  └─ KHÔNG → List hoặc Queue
   │     ├─ Cần FIFO/LIFO? → Queue
   │     │  ├─ Dựa trên priority? → PriorityQueue
   │     │  ├─ Thread-safe? → BlockingQueue
   │     │  └─ Mặc định → ArrayDeque
   │     │
   │     └─ Collection có thứ tự? → List
   │        ├─ Truy cập ngẫu nhiên thường xuyên? → ArrayList
   │        └─ Thao tác head/tail thường xuyên? → LinkedList

// 1. User session cache (bounded, access-order)
Map<String, Session> sessions = new LinkedHashMap<>(1000, 0.75f, true) {
    protected boolean removeEldestEntry(Map.Entry<String, Session> eldest) {
        return size() > 1000;
    }
};
 
// 2. Unique visitor tracking (fast membership)
Set<String> uniqueVisitors = new HashSet<>();
 
// 3. Leaderboard (sorted scores)
TreeMap<Integer, String> leaderboard = new TreeMap<>(Comparator.reverseOrder());
 
// 4. Task queue (priority-based)
PriorityQueue<Task> taskQueue = new PriorityQueue<>(
    Comparator.comparing(Task::getPriority)
);
 
// 5. Event processing (FIFO)
Deque<Event> eventQueue = new ArrayDeque<>();
 
// 6. Thread-safe counter
Map<String, AtomicInteger> counters = new ConcurrentHashMap<>();
counters.computeIfAbsent("requests", k -> new AtomicInteger()).incrementAndGet();
 
// 7. Sorted time-series data
TreeMap<Instant, Double> timeSeries = new TreeMap<>();
SortedMap<Instant, Double> lastHour = timeSeries.tailMap(
    Instant.now().minus(1, ChronoUnit.HOURS)
);
 
// 8. Batch processing (ArrayList cho hiệu suất iteration)
List<Record> batch = new ArrayList<>(1000);
for (Record record : batch) {
    process(record); // Truy cập tuần tự nhanh
}

// ✅ TỐT: Tránh overhead resize
List<String> items = new ArrayList<>(expectedSize);
Map<String, Integer> map = new HashMap<>(expectedSize);
 
// ❌ TỆ: Nhiều lần resize khi phát triển
List<String> items = new ArrayList<>(); // Mặc định 10
for (int i = 0; i < 10000; i++) {
    items.add(String.valueOf(i)); // Resize ~14 lần!
}

// ✅ TỐT: Linh hoạt, cho phép thay đổi implementation
List<String> names = new ArrayList<>();
Set<Integer> ids = new HashSet<>();
Map<String, User> users = new HashMap<>();
 
// ❌ TỆ: Gắn chặt với implementation
ArrayList<String> names = new ArrayList<>();
HashSet<Integer> ids = new HashSet<>();

// ❌ BẪY: ConcurrentModificationException
List<String> list = new ArrayList<>(Arrays.asList("A", "B", "C"));
for (String item : list) {
    if (item.equals("B")) {
        list.remove(item); // ❌ Ném exception!
    }
}
 
// ✅ GIẢI PHÁP 1: Sử dụng Iterator.remove()
Iterator<String> it = list.iterator();
while (it.hasNext()) {
    String item = it.next();
    if (item.equals("B")) {
        it.remove(); // ✅ An toàn
    }
}
 
// ✅ GIẢI PHÁP 2: Sử dụng removeIf (Java 8+)
list.removeIf(item -> item.equals("B"));
 
// ✅ GIẢI PHÁP 3: Thu thập và xóa (cho logic phức tạp)
List<String> toRemove = new ArrayList<>();
for (String item : list) {
    if (shouldRemove(item)) {
        toRemove.add(item);
    }
}
list.removeAll(toRemove);

// ✅ Immutable collections (Java 9+)
List<String> immutable = List.of("A", "B", "C");
Set<Integer> immutableSet = Set.of(1, 2, 3);
Map<String, Integer> immutableMap = Map.of("A", 1, "B", 2);
 
// Immutable collections:
// - Thread-safe mặc định
// - Không có rủi ro sửa đổi vô tình
// - Bộ nhớ hiệu quả hơn (không có capacity không sử dụng)
// - Ném UnsupportedOperationException khi cố sửa đổi
 
// ❌ BẪY: Collections.unmodifiableList() chỉ là một view
List<String> original = new ArrayList<>(Arrays.asList("A", "B"));
List<String> unmodifiable = Collections.unmodifiableList(original);
original.add("C"); // ⚠️ Cũng ảnh hưởng unmodifiable!

// ✅ PHẢI implement cả equals() và hashCode() cho hash-based collections
class User {
    private String id;
    private String name;
    
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof User)) return false;
        User user = (User) o;
        return Objects.equals(id, user.id);
    }
    
    @Override
    public int hashCode() {
        return Objects.hash(id);
    }
}
 
// ❌ BẪY: Vi phạm contract equals/hashCode
Set<User> users = new HashSet<>();
users.add(new User("1", "Alice"));
users.contains(new User("1", "Alice")); // Có thể trả về false nếu không có equals/hashCode đúng!

// Collections cho phép null
List<String> list = new ArrayList<>();
list.add(null); // ✅ OK
 
Map<String, Integer> map = new HashMap<>();
map.put(null, 1); // ✅ Một null key được phép
map.put("key", null); // ✅ Null values được phép
 
// Collections KHÔNG cho phép null
TreeSet<String> treeSet = new TreeSet<>();
treeSet.add(null); // ❌ NullPointerException
 
TreeMap<String, Integer> treeMap = new TreeMap<>();
treeMap.put(null, 1); // ❌ NullPointerException
 
ConcurrentHashMap<String, Integer> concurrent = new ConcurrentHashMap<>();
concurrent.put(null, 1); // ❌ NullPointerException
concurrent.put("key", null); // ❌ NullPointerException

// ❌ Hiệu suất kém - coarse-grained locking
Map<String, Integer> syncMap = Collections.synchronizedMap(new HashMap<>());
 
// Phải synchronize thủ công cho iteration
synchronized (syncMap) {
    for (Map.Entry<String, Integer> entry : syncMap.entrySet()) {
        // Process entry
    }
}

// ✅ Hiệu suất tốt hơn - fine-grained locking
ConcurrentHashMap<String, Integer> concurrentMap = new ConcurrentHashMap<>();
CopyOnWriteArrayList<String> cowList = new CopyOnWriteArrayList<>();
BlockingQueue<Task> queue = new LinkedBlockingQueue<>();
 
// Không cần synchronization bên ngoài
concurrentMap.put("key", 1);
cowList.add("item");

// ✅ Thread-safe tự nhiên (không thể sửa đổi)
List<String> immutable = List.of("A", "B", "C");
// An toàn để chia sẻ giữa các thread mà không cần synchronization

List<String> list = Arrays.asList("A", "B", "C");
list.add("D"); // ❌ UnsupportedOperationException - fixed-size!
 
// ✅ Tạo bản sao có thể thay đổi
List<String> mutableList = new ArrayList<>(Arrays.asList("A", "B", "C"));
mutableList.add("D"); // ✅ OK

List<String> original = new ArrayList<>(Arrays.asList("A", "B", "C", "D"));
List<String> sublist = original.subList(1, 3); // ["B", "C"] - một view!
 
sublist.clear(); // Xóa sublist
System.out.println(original); // ["A", "D"] - ⚠️ Original bị sửa đổi!

// ❌ Không thể tạo mảng generic
List<String>[] arrayOfLists = new ArrayList<String>[10]; // Lỗi compile
 
// ✅ Sử dụng List của Lists thay thế
List<List<String>> listOfLists = new ArrayList<>();

// ❌ BẪY: Comparator không nhất quán với equals
class Person {
    String name;
    int age;
    
    @Override
    public boolean equals(Object o) {
        // So sánh cả name và age
    }
}
 
// TreeSet sử dụng comparator chỉ so sánh age
TreeSet<Person> people = new TreeSet<>(Comparator.comparing(Person::getAge));
people.add(new Person("Alice", 30));
people.add(new Person("Bob", 30)); // ⚠️ Không được thêm - cùng age!
// TreeSet nghĩ chúng bằng nhau, nhưng equals() nói chúng khác nhau

ArrayList.get(index):          ~2 ns
LinkedList.get(index):         ~100 ns (chậm hơn 50 lần!)
 
HashMap.get(key):              ~10 ns
TreeMap.get(key):              ~30 ns
ConcurrentHashMap.get(key):    ~15 ns
 
ArrayList.add(end):            ~5 ns
LinkedList.add(end):           ~20 ns
ArrayDeque.add(end):           ~5 ns
 
HashSet.contains():            ~10 ns
TreeSet.contains():            ~30 ns