Question 1

Khi nào bạn chọn ArrayList, khi nào chọn LinkedList?

Accepted Answer

Thực tế là gần như luôn chọn ArrayList — LinkedList chỉ thắng đúng một tình huống hẹp là thêm/xoá ở đầu list, mà tình huống đó ArrayDeque còn làm tốt hơn. Lý do nằm ở memory layout: ArrayList giữ element trên một mảng liền kề nên CPU load một cache line 64 byte là có sẵn 8 reference, còn LinkedList bọc mỗi element trong một Node rải rác heap, mỗi lần đi next là một cache miss. Kèm theo đó mỗi node tốn khoảng 40 byte so với 8 byte một reference của ArrayList, tức gấp 5 lần bộ nhớ và tạo áp lực GC tương ứng. Ngay cả chèn giữa, nơi Big-O ngang nhau, ArrayList thường thắng vì System.arraycopy là JIT intrinsic ánh xạ thẳng sang lệnh copy bộ nhớ của CPU, trong khi LinkedList phải duyệt tới vị trí đó trước. Bẫy hay gặp nhất là gọi list.get(i) trong vòng lặp trên LinkedList — mỗi get là O(n) nên cả vòng lặp thành O(n²).

Question 2

ArrayList hết chỗ thì chuyện gì xảy ra bên trong?

Accepted Answer

ArrayList giữ một mảng Object[] elementData; khi size chạm elementData.length, grow() cấp một mảng mới rồi Arrays.copyOf toàn bộ phần tử sang. Capacity mới tính bằng oldCapacity + (oldCapacity >> 1), tức tăng 1.5 lần bằng một phép dịch bit chứ không phải nhân số thực. Mảng đầu tiên chỉ được cấp ở lần add() đầu tiên với DEFAULT_CAPACITY = 10 — list vừa khởi tạo mà chưa dùng thì không tốn bộ nhớ mảng. JDK source không ghi chính thức vì sao chọn 1.5x thay vì 2x; lập luận được trích dẫn nhiều nhất là bộ nhớ: lãng phí trung bình khoảng 17% thay vì 25%, và vì 1.5 nhỏ hơn tỉ lệ vàng φ xấp xỉ 1.618 nên tổng các block đã giải phóng đủ chỗ cho block mới, allocator tái sử dụng được. Mỗi lần copy là O(n) nhưng trung bình vẫn là O(1) amortized, và biết trước số phần tử thì new ArrayList<>(n) xoá sạch mọi lần grow.

Question 3

Giải thích cho tôi HashMap lưu và tìm một entry như thế nào.

Accepted Answer

HashMap là một mảng bucket Node<K,V>[] table có length luôn là luỹ thừa của 2. Khi put, nó lấy key.hashCode() rồi trộn bit cao xuống thấp bằng h ^ (h >>> 16), sau đó tính chỉ số bucket bằng (table.length - 1) & hash — phép AND bit rẻ hơn chia lấy dư và cho cùng kết quả nhờ capacity là luỹ thừa của 2. Bucket trống thì gắn Node mới vào là xong, đó là O(1) thật; bucket đã có entry thì duyệt linked list trong bucket, so hash (một phép so int rất rẻ) trước rồi mới gọi equals(). get đi đúng đường đó: tính bucket, duyệt chain, trả value khi khớp cả hash lẫn equals. Khi size vượt threshold = capacity × 0.75, table nhân đôi và phân bố lại toàn bộ entry.

Question 4

Vì sao class dùng làm key của HashMap phải override cả equals lẫn hashCode?

Accepted Answer

Vì HashMap dùng hai thứ cho hai việc khác nhau: hashCode để tìm ra bucket, equals để tìm đúng key bên trong bucket đó. Không override thì bản mặc định của Object so sánh theo identity, nên map.get với một object mới cùng nội dung sẽ trả null dù bạn vừa put nó vào. Ràng buộc bắt buộc là hai object equals nhau thì phải có cùng hashCode; chiều ngược lại không cần đúng, hai object khác nhau vẫn được phép trùng hash và khi đó chúng nằm chung một bucket. Cách an toàn là override cả hai trên cùng bộ field để hợp đồng không bị lệch. Bẫy nặng hơn là key mutable: nếu hashCode phụ thuộc field bị sửa sau khi put, entry kẹt lại ở bucket cũ nên get trả null và entry đó vĩnh viễn không tìm lại được — nên dùng field final hoặc record làm key.

Question 5

HashSet lưu dữ liệu bằng cấu trúc gì bên dưới?

Accepted Answer

HashSet không có logic lưu trữ riêng — bên trong nó giữ một HashMap<E, Object> và mọi add(e) thực chất là map.put(e, PRESENT) với PRESENT là một object hằng dùng chung. Vì vậy mọi đặc tính của HashSet đều thừa hưởng từ HashMap: add/contains/remove là O(1) trung bình, key phải có equals và hashCode đúng, và thứ tự iterate không xác định. Cùng kiểu quan hệ đó, LinkedHashSet bọc LinkedHashMap nên giữ thứ tự chèn, còn TreeSet bọc TreeMap nên sorted và mọi thao tác là O(log n). Một khác biệt hay bị hỏi thêm: HashSet cho phép một phần tử null, còn TreeSet thì không vì nó phải gọi compareTo.

Question 6

Vì sao xoá phần tử trong vòng for-each lại ném ConcurrentModificationException?

Accepted Answer

for-each chỉ là cú pháp đường cho Iterator, và ArrayList đếm mọi thay đổi cấu trúc bằng biến modCount. Lúc tạo iterator, nó chụp expectedModCount = modCount; mỗi lần next() gọi checkForComodification() để so hai giá trị, lệch là ném ConcurrentModificationException. Gọi list.remove(o) đi đường ngoài làm modCount tăng mà iterator không biết nên vòng kế tiếp là nổ — ngoại lệ tinh vi là xoá đúng phần tử kế cuối, khi đó hasNext() trả false nên vòng lặp thoát sớm và bug lọt lưới. Ngược lại it.remove() thì iterator tự gán lại expectedModCount = modCount nên an toàn. Cách viết nên dùng là list.removeIf(...), vì ArrayList override removeIf bằng thuật toán hai lượt với BitSet chạy O(n), trong khi it.remove() thủ công phải dịch mảng ở mỗi lần xoá. Lưu ý fail-fast chỉ là công cụ phát hiện bug: Javadoc ghi rõ nó là best-effort chứ không phải bảo đảm thread-safety.

Question 7

Comparable và Comparator khác nhau chỗ nào?

Accepted Answer

Comparable nằm bên trong class và định nghĩa thứ tự tự nhiên duy nhất qua compareTo, còn Comparator là hàm so sánh bên ngoài nên một class có bao nhiêu cách sắp xếp cũng được. Comparator là @FunctionalInterface nên viết được dạng lambda hoặc method reference, và có fluent API kiểu Comparator.comparingInt(User::getAge).thenComparing(User::getName).reversed(). Dùng Comparable khi class có thứ tự hiển nhiên như Integer hay LocalDate; dùng Comparator khi cần nhiều tiêu chí hoặc khi class thuộc thư viện ngoài không sửa được. Cả hai phải giữ cùng một hợp đồng: đối xứng dấu, bắc cầu, và khuyến nghị mạnh là nhất quán với equals. Lỗi kinh điển là viết return this.value - other.value — phép trừ int tràn số khi gặp Integer.MIN_VALUE, nên luôn dùng Integer.compare hoặc Double.compare.

Question 8

Khi nào bạn chọn TreeMap thay cho HashMap?

Accepted Answer

Chọn TreeMap khi cần thứ tự: duyệt key theo thứ tự sắp xếp, truy vấn khoảng bằng subMap/headMap/tailMap, hoặc tìm lân cận bằng ceilingKey/floorKey. Bên dưới nó là cây đỏ đen tự cân bằng nên mọi thao tác là O(log n) kể cả worst case, khác HashMap vốn O(1) trung bình nhưng suy biến khi hash xấu. Giá phải trả là bộ nhớ và tốc độ: mỗi entry của TreeMap mang thêm ba con trỏ left/right/parent cùng một cờ màu, và việc nhảy con trỏ giữa các node gây cache miss nên lookup thường chậm hơn HashMap khoảng 2 đến 10 lần. TreeMap cũng không nhận key null vì phải gọi compareTo, trong khi HashMap cho phép một key null. Nếu chỉ cần giữ thứ tự chèn chứ không cần sắp xếp thì LinkedHashMap nhẹ hơn TreeMap: vẫn O(1) như HashMap, chỉ trả thêm hai con trỏ prev/next mỗi entry.

Question 9

Java 8 thay đổi gì trong HashMap để chống hash collision, và vì sao ngưỡng là 8?

Accepted Answer

Java 8 (JEP 180) cho phép biến một bucket thành cây đỏ đen khi chain quá dài, đưa worst case lookup từ O(n) xuống O(log n). Điều kiện là kép: chain phải đạt TREEIFY_THRESHOLD = 8 và table phải có từ MIN_TREEIFY_CAPACITY = 64 bucket trở lên; table nhỏ hơn thì HashMap gọi resize() vì nhân đôi số bucket để phân tán key rẻ hơn là dựng cây. Ngưỡng 8 lấy từ phân phối Poisson tham số khoảng 0.5 với load factor 0.75 — xác suất một bucket chứa đúng 8 entry nhỏ hơn một phần mười triệu, nên chạm ngưỡng gần như chắc chắn là hash bị lạm dụng chứ không phải workload bình thường. Chiều ngược lại dùng UNTREEIFY_THRESHOLD = 6 để tạo hysteresis, tránh dựng rồi phá cây liên tục khi size dao động quanh ngưỡng. Đây là phòng thủ chống hash-collision DoS chứ không phải tối ưu: attacker vẫn ép được O(log n) nên tầng giới hạn số key trong request và rate limiting vẫn phải đứng trước.

Chỉ nhớ mỗi con số 8 mà quên điều kiện 64 — nói "cứ đủ 8 phần tử là bucket thành cây" là sai, dưới 64 bucket thì HashMap chọn resize.

Học sâu hơn

HashMap treeify — phòng thủ hash-collision DoS từ Java 8Collections Internals · ~11 phút Map và Set — HashMap, TreeMap, HashSet bên dướiGenerics & Collections · ~22 phút

Question 10

HashMap resize thế nào, và vì sao nói get là O(1) chỉ đúng ở mức amortized?

Accepted Answer

Resize kích hoạt khi size vượt threshold = capacity × 0.75: cấp một table mới gấp đôi rồi phân bố lại toàn bộ entry. Java 8 phân bố lại rất rẻ vì nhân đôi capacity chỉ thêm đúng một bit vào bitmask chỉ số — kiểm tra (hash & oldCap) bằng 0 thì entry ở nguyên bucket cũ, khác 0 thì sang bucket cũ + oldCap, không phải gọi lại hashCode() lần nào. Nhưng cái put nào chạm ngưỡng thì chính nó gánh cả O(n) rehash, nên O(1) là con số trung bình trên cả chuỗi thao tác chứ không phải bảo đảm cho từng thao tác. Với đường đi nhạy độ trễ, đó là lý do phải pre-size bằng HashMap.newHashMap(n) từ Java 19, hoặc new HashMap<>((int)(n / 0.75 + 1)) ở bản cũ hơn. Truyền thẳng n làm initial capacity là bẫy, vì threshold khi đó chỉ bằng n × 0.75 nên map vẫn resize trước khi chứa đủ n entry.

Question 11

Vì sao List không gán được cho List, trong khi Integer[] lại gán được cho Number[]?

Accepted Answer

Generics của Java là invariant: List và List là hai kiểu độc lập, dù Integer là subtype của Number. Nếu cho phép gán, bạn sẽ add được một Double vào list thực chất chỉ chứa Integer, và cú nổ ClassCastException xảy ra tận lúc đọc ra — đúng thứ generics sinh ra để chặn. Mảng thì ngược lại, covariant từ Java 1.0 khi chưa có generics, nên gán Number[] nums = ints biên dịch được và nums[0] = 3.14 ném ArrayStoreException lúc chạy. Nói cách khác cùng một lỗi: mảng bắt ở runtime bằng arraystore check tốn chi phí mỗi lần ghi, còn generics bắt ngay lúc biên dịch và không tốn gì lúc chạy. Khi thật sự cần nhận mọi list số, ký hiệu đúng là wildcard List — nhận được cả List lẫn List nhưng chỉ đọc, không ghi.

Question 12

PECS là gì? Cho tôi một ví dụ trong JDK.

Accepted Answer

PECS là Producer Extends, Consumer Super: tham số mà bạn lấy dữ liệu ra thì khai wildcard extends, tham số mà bạn đẩy dữ liệu vào thì khai super. List khai extends chỉ đọc được, vì compiler không biết kiểu thật là Integer hay Double nên cấm mọi add trừ null; list khai super thì ngược lại, add một T luôn hợp lệ nhưng lấy phần tử ra chỉ chắc chắn được kiểu Object. Ví dụ chuẩn trong JDK là chữ ký Collections.copy(List<? super T> dest, List<? extends T> src) — nguồn src sản xuất nên dùng extends, đích dest tiêu thụ nên dùng super, còn type parameter <T> làm cầu nối để compiler chứng minh mọi thứ đọc từ src đều ghi được vào dest. Effective Java Item 31 khuyên API public dùng wildcard cho mềm dẻo, còn bên trong thì chuyển về type parameter qua một helper method.

Đọc thuộc chữ viết tắt nhưng không giải thích được vì sao ? extends lại cấm add — đó mới là phần chứng tỏ bạn hiểu cơ chế chứ không học vẹt.

Học sâu hơn

Wildcard `? extends`, `? super` — PECS ruleGenerics & Collections · ~18 phút

Question 13

Type erasure là gì, và nó chặn bạn làm những gì?

Accepted Answer

Compiler xoá type parameter khi biên dịch: T bị thay bằng Object, hoặc bằng bound nếu khai T extends Number, rồi tự chèn cast ở mọi chỗ caller lấy giá trị ra. Hệ quả trực tiếp là runtime không còn thông tin kiểu: không viết được new T(), obj instanceof T, new T[10], và không cho generic trên Throwable. Hai method process(List<String>) và process(List<Integer>) cũng không cùng tồn tại được vì erase ra cùng một chữ ký. Kẽ hở đi kèm là heap pollution: qua một reference raw type có thể nhét Integer vào List<String>, và ClassCastException nổ ở dòng get() chứ không phải dòng gây lỗi. Workaround quen thuộc là truyền Class<T> token rồi dùng type.isInstance/type.cast, hoặc Supplier<T> thay cho new T(); lý do Java chọn erasure là để code viết trước Java 5 chạy tiếp mà không phải biên dịch lại.

Trả lời "generics bị xoá lúc runtime" rồi hết — không nêu được hệ quả cụ thể lẫn lý do lịch sử là tương thích ngược, vốn cũng là lý do Java khác C#.

Học sâu hơn

Type erasure — sự thật không dễ chịu của generics JavaGenerics & Collections · ~18 phút

Question 14

List.of, List.copyOf và Collections.unmodifiableList khác nhau thế nào?

Accepted Answer

List.of(...) (Java 9, JEP 269) tạo list bất biến thật, không có collection mutable nào bên dưới và không nhận phần tử null. List.copyOf(coll) sao chép sang một list bất biến độc lập nên sửa collection nguồn sau đó không ảnh hưởng gì; nếu đầu vào vốn đã bất biến thì nó trả lại chính reference đó thay vì copy. Collections.unmodifiableList chỉ là lớp bọc chỉ-đọc trên list gốc — ai còn giữ reference gốc vẫn add được và view phản ánh thay đổi đó ngay, nên nó không phải bất biến. Vì vậy pattern bảo vệ state là defensive copy ngay trong constructor bằng List.copyOf, và Effective Java Item 50 nhấn mạnh phải copy trước rồi mới validate để tránh lỗ hổng TOCTOU. Hai cách đầu chỉ bất biến ở tầng cấu trúc: list chứa object mutable thì nội dung của object đó vẫn sửa được, đây là shallow immutability.

Question 15

Làm sao dựng một LRU cache chỉ bằng thư viện chuẩn của Java?

Accepted Answer

Dùng LinkedHashMap với constructor ba tham số new LinkedHashMap<>(16, 0.75f, true): cờ accessOrder = true khiến mỗi lần get hay put đẩy entry vừa chạm xuống cuối danh sách liên kết, nên đầu danh sách luôn là entry ít dùng gần đây nhất. Sau đó override removeEldestEntry trả size() > maxSize — hook này được gọi ngay sau mỗi put, trả true thì entry đầu bị evict, thế là xong LRU trong vài dòng. Cạm bẫy lớn nhất là thread-safety: với accessOrder = true, get không còn là thao tác chỉ đọc mà sửa con trỏ prev/next của danh sách bên trong. Vì vậy không được dùng read lock của ReentrantReadWriteLock cho get — nhiều thread đọc song song sẽ phá cấu trúc danh sách, hậu quả là dữ liệu sai hoặc CPU treo 100% vì duyệt phải một vòng lặp, nên mọi thao tác phải đi qua một lock ghi duy nhất. Hệ thống chịu tải cao thì nên dùng thư viện như Caffeine thay vì tự chế, vì nó tối ưu sẵn cho đa luồng và có cả TTL.

Câu hỏi phỏng vấn Java Collections

Khi nào bạn chọn ArrayList, khi nào chọn LinkedList?

ArrayList hết chỗ thì chuyện gì xảy ra bên trong?

Giải thích cho tôi HashMap lưu và tìm một entry như thế nào.

Vì sao class dùng làm key của HashMap phải override cả equals lẫn hashCode?

HashSet lưu dữ liệu bằng cấu trúc gì bên dưới?

Vì sao xoá phần tử trong vòng for-each lại ném ConcurrentModificationException?

Comparable và Comparator khác nhau chỗ nào?

Khi nào bạn chọn TreeMap thay cho HashMap?

Java 8 thay đổi gì trong HashMap để chống hash collision, và vì sao ngưỡng là 8?

HashMap resize thế nào, và vì sao nói get là O(1) chỉ đúng ở mức amortized?

Vì sao `List<Integer>` không gán được cho `List<Number>`, trong khi `Integer[]` lại gán được cho `Number[]`?

PECS là gì? Cho tôi một ví dụ trong JDK.

Type erasure là gì, và nó chặn bạn làm những gì?

List.of, List.copyOf và Collections.unmodifiableList khác nhau thế nào?

Làm sao dựng một LRU cache chỉ bằng thư viện chuẩn của Java?

Trả lời trôi chảy bắt đầu từ hiểu cơ chế

Câu hỏi phỏng vấn Java Collections

Khi nào bạn chọn ArrayList, khi nào chọn LinkedList?

ArrayList hết chỗ thì chuyện gì xảy ra bên trong?

Giải thích cho tôi HashMap lưu và tìm một entry như thế nào.

Vì sao class dùng làm key của HashMap phải override cả equals lẫn hashCode?

HashSet lưu dữ liệu bằng cấu trúc gì bên dưới?

Vì sao xoá phần tử trong vòng for-each lại ném ConcurrentModificationException?

Comparable và Comparator khác nhau chỗ nào?

Khi nào bạn chọn TreeMap thay cho HashMap?

Java 8 thay đổi gì trong HashMap để chống hash collision, và vì sao ngưỡng là 8?

HashMap resize thế nào, và vì sao nói get là O(1) chỉ đúng ở mức amortized?

Vì sao List<Integer> không gán được cho List<Number>, trong khi Integer[] lại gán được cho Number[]?

PECS là gì? Cho tôi một ví dụ trong JDK.

Type erasure là gì, và nó chặn bạn làm những gì?

List.of, List.copyOf và Collections.unmodifiableList khác nhau thế nào?

Làm sao dựng một LRU cache chỉ bằng thư viện chuẩn của Java?

Trả lời trôi chảy bắt đầu từ hiểu cơ chế

Vì sao `List<Integer>` không gán được cho `List<Number>`, trong khi `Integer[]` lại gán được cho `Number[]`?