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

Reading Time: 23 minutes

Collections Framework là một trong những API cốt lõi của Java và cũng là một chủ đề quan trọng thường xuất hiện trong các buổi phỏng vấn.

Trong bài viết này, chúng tôi sẽ liệt kê qua một số câu hỏi phỏng vấn về Java Collection quan trọng cùng với câu trả lời chi tiết. Chúng được đúc kết từ nhiều năm kinh nghiệm lập trình Java của chúng tôi, nhằm giúp các bạn chuẩn bị tốt hơn cho buổi phỏng vấn sắp tới.

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

1. Liệt kê các tính năng trên Java 8 có liên quang đến collection?

Java 8 đã mang đến nhiều thay đổi quan trọng cho Collection API:

1. Java Stream API cho các collection class hỗ trợ xử lý cả kiểu tuần tự cũng như song song.
2. Interface Iterable được mở rộng với phương thức mặc định forEach(). Ta có thể dùng nó để duyệt qua các phần tử của một collection. Phương thức này cũng rất hữu ích khi kết hợp với biểu thức lambda, vì tham số Consumer của nó là một functional interface (giao diện hàm).
3. Các cải tiến Collection API nhỏ khác, chẳng hạn như phương thức forEachRemaining(Consumer action) trong interface Iterator, và các phương thức replaceAll(), compute(), merge() trong Map.

2. Java Collections Framework là gì? Liệt kê một số lợi ích của nó?

Collection được sử dụng trong mọi ngôn ngữ lập trình. Những phiên bản Java đầu tiên chỉ chứa một vài class cho collection như: Vector, Stack, Hashtable, Array. Tuy nhiên, nếu xét rộng hơn về phạm vi và nhu cầu sử dụng, Java 1.2 đã giới thiệu Collections Framework dưới dạng một kiến trúc hợp nhất bao gồm tất cả các interface, implementation và thuật toán liên quan đến collection.

Kể từ đó, Java Collections đã phát triển thêm với việc áp dụng Generics và sự ra đời của các lớp Concurrent Collection để hỗ trợ các hoạt động an toàn luồng (thread-safe). Framework này cũng bao gồm các giao diện chặn (blocking interface) và các triển khai của chúng trong package java.util.concurrent.

Một số lợi ích của Collections Framework bao gồm:

• Giảm thiểu công sức lập trình khi ta có thể sử dụng các class collection có sẵn thay vì phải tự triển khai các class collection riêng.
• Nâng cao chất lượng code nhờ vào các class thuộc Collections Framework đã được kiểm thử kỹ lưỡng.
• Giảm thiểu công sức bảo trì code khi dùng các class collection đi kèm với JDK.
• Tăng khả năng tái sử dụng và tương tác.

3. Lợi ích của Generics trong Collections Framework là gì?

Java 1.5 đã ra mắt Generics, và kể từ đó tất cả các interface và implementation của collection đều sử dụng rộng rãi tính năng này.

Generics cho phép ta chỉ định kiểu đối tượng mà một collection có thể chứa. Do đó, nếu ta cố gắng thêm một phần tử thuộc kiểu khác, trình biên dịch sẽ báo lỗi ngay tại thời điểm biên dịch. Điều này giúp ta tránh được lỗi ClassCastException xảy ra lúc runtime vì nó đã được phát hiện ở bước biên dịch trước dó.

Ngoài ra, Generics còn giúp code trở nên mạch lạc hơn vì ta không cần phải dùng đến các phép ép kiểu (casting) và toán tử instanceof.

4. Các interface cơ bản của Java Collections Framework là gì?

Collection là interface gốc trong hệ thống phân cấp của Collections Framework. Một collection đại diện cho một nhóm các đối tượng, được gọi là các phần tử (element) của nó. Nền tảng Java không cung cấp bất kỳ implementation trực tiếp nào cho interface Collection. Set là một collection không cho phép chứa các phần tử trùng lặp. Interface này mô phỏng khái niệm tập hợp (set) trong toán học và được dùng để biểu diễn các tập hợp, ví dụ như các lá bài trong một bộ bài. List là một collection có thứ tự và cho phép chứa các phần tử trùng nhau. Ta có thể truy cập bất kỳ phần tử nào thông qua chỉ mục (index) của nó. List tương tự như một mảng nhưng có độ dài động. Map là một đối tượng dùng để ánh xạ các key (khóa) tới các value (giá trị). Một Map không thể chứa các key trùng lặp: mỗi key chỉ có thể ánh xạ tới tối đa một value mà thôi. Một số interface quan trọng khác bao gồm Queue, Dequeue, Iterator, SortedSet, SortedMap và ListIterator.

5. Tại sao interface Collection không kế thừa (extend) interface Cloneable và Serializable?

Interface Collection định nghĩa một nhóm các đối tượng (Object), gọi là các phần tử (element). Việc các phần tử này được lưu trữ và quản lý như thế nào hoàn toàn phụ thuộc vào các triển khai cụ thể của Collection. Ví dụ, một số Collection như List cho phép phần tử trùng lặp, trong khi các implementation khác như Set thì không.

Nhiều triển khai của Collection có phương thức public clone(). Tuy nhiên, việc yêu cầu tất cả các triển khai đều phải có phương thức này là không hợp lý. Lý do là vì Collection chỉ là một đặc tả trừu tượng (abstract representation). Cách thức hoạt động cụ thể phụ thuộc vào từng triển khai.

Ý nghĩa và các hệ quả của việc cloning (sao chép) hay serializing (chuỗi hóa) chỉ thực sự có ý nghĩa đối với từng triển khai cụ thể. Do đó, mỗi triển khai cụ thể phải tự quyết định xem nó nên được clone hay serialize hay không, và nếu được thì làm như thế nào.

Việc bắt buộc tất cả các triển khai phải hỗ trợ cloning và serialization sẽ làm giảm tính linh hoạt và tăng sự ràng buộc. Quyết định nên thuộc về từng triển khai cụ thể.

6. Tại sao interface Map không kế thừa interface Collection?

Mặc dù interface này và các triển khi của nó là một phần của Collections Framework, Map không phải là một collection (theo đúng nghĩa đen) và ngược lại, một collection cũng không phải là một Map. Do đó, việc Map kế thừa Collection hay ngược lại là không hợp lý.

Nếu Map kế thừa interface Collection, thì đâu được coi là phần tử (element) của nó? Map chứa các cặp key-value và cung cấp các phương thức để truy xuất danh sách các Key hoặc danh sách các Value (dưới dạng một Collection). Nhưng bản thân cấu trúc key-value này không phù hợp với mô hình “một nhóm các phần tử” (group of element) của Collection.

7. Iterator là gì?

Interface Iterator cung cấp các phương thức để duyệt qua (iterate) bất kỳ Collection nào. Ta có thể lấy một instance của Iterator từ một Collection bằng cách sử dụng phương thức iterator().

Iterator đã thay thế Enumeration trong Java Collections Framework. Nó cho phép bên gọi (caller) xóa các phần tử khỏi collection gốc ngay trong quá trình duyệt. Iterator trong Java Collection cung cấp một cách chung để duyệt qua các phần tử của một collection và nó chính là một ví dụ của kiểu thiết kế Iterator.

8. Sự khác biệt giữa interface Enumeration và Iterator là gì?

Enumeration nhanh gấp đôi Iterator và sử dụng rất ít bộ nhớ. Enumeration có thiết kế rất cơ bản và chỉ đáp ứng được các nhu cầu đơn giản. Tuy nhiên, Iterator an toàn hơn nhiều so với Enumeration vì nó có cơ chế ngăn chặn các thread khác sửa đổi collection đang được duyệt.

Iterator đã thay thế Enumeration trong Java Collections Framework. Nó cho phép người gọi (caller) xóa các phần tử khỏi collection gốc, một tính năng mà Enumeration không có. Tên các phương thức của Iterator cũng đã được cải tiến để làm rõ hơn chức năng của chúng.

9. Tại sao Iterator không có phương thức kiểu add() để thêm phần tử vào collection?

Ngữ nghĩa (semantics) của thao tác này sẽ không rõ ràng, vì đặc tả (contract) của Iterator không đưa ra bất kỳ đảm bảo nào về thứ tự duyệt các phần tử. Tuy nhiên, cần lưu ý rằng ListIterator lại cung cấp thao tác add, bởi vì ListIterator đảm bảo về thứ tự khi duyệt.

10. Tại sao Iterator không có phương thức để lấy phần tử tiếp theo mà không di chuyển con trỏ?

Chức năng này có thể được xây dựng dựa trên interface Iterator hiện tại. Tuy nhiên, vì nhu cầu sử dụng chức năng này không thực sự cao, nên việc đưa nó vào interface Iterator trở nên không hợp lý (do sẽ bắt buộc mọi class triển khai Iterator đều phải cung cấp một phương thức đó).

11. Iterator và ListIterator khác nhau như thế nào?

• Ta có thể sử dụng Iterator để duyệt qua các collection Set và List, trong khi ListIterator chỉ có thể được sử dụng với các List.
• Iterator chỉ có thể duyệt theo chiều tiến (forward), trong khi ListIterator có thể duyệt theo cả chiều tiến và chiều lùi (backward).
• ListIterator kế thừa từ interface Iterator và cung cấp thêm các chức năng như thêm phần tử, thay thế phần tử, và lấy chỉ mục (index) của phần tử trước đó và phần tử kế tiếp.

12. Có những cách nào để duyệt qua một list?

Ta có thể duyệt qua một List theo hai cách khác nhau: sử dụng iterator và sử dụng vòng lặp for-each.

List<String> strList = new ArrayList<>();

//dùng for-each
for(String obj : strList){
    System.out.println(obj);
}

//dùng iterator
Iterator<String> it = strList.iterator();
while(it.hasNext()){
    String obj = it.next();
    System.out.println(obj);
}

Sử dụng iterator thì có tính an toàn luồng hơn vì nó đảm bảo rằng nếu các phần tử bên trong List bị thay đổi, một ConcurrentModificationException sẽ được ném ra.

13. Bạn hiểu thế nào về đặc tính fail-fast của iterator?

Đặc tính fail-fast của Iterator kiểm tra bất kỳ thay đổi nào trong cấu trúc của collection bên dưới mỗi khi ta cố gắng lấy phần tử tiếp theo. Nếu phát hiện bất kỳ thay đổi nào, nó sẽ cho ra lỗi ConcurrentModificationException. Tất cả các triển khai của Iterator trong các class Collection đều được thiết kế fail-fast, ngoại trừ các class của concurrent collection như ConcurrentHashMap và CopyOnWriteArrayList.

14. Sự khác biệt giữa fail-fast và fail-safe là gì?

Đặc tính fail-safe của Iterator làm việc trên một bản sao của collection bên dưới, do đó nó không bị ảnh hưởng bởi bất kỳ thay đổi nào trong collection đó. Theo thiết kế, tất cả các class collection trong package java.util là fail-fast, trong khi đó các class collection trong java.util.concurrent là fail-safe.

Các iterator kiểu fail-fast sẽ cho ra lỗi ConcurrentModificationException, còn iterator fail-safe thì không bao giờ ném ra lỗi này.

15. Làm thế nào để tránh lỗi ConcurrentModificationException khi duyệt một collection?

Ta có thể sử dụng các class của concurrent collection để tránh ConcurrentModificationException khi duyệt qua một collection, ví dụ dùng CopyOnWriteArrayList thay vì ArrayList.

16. Tại sao không có triển khai cụ thể nào của interface Iterator?

Interface Iterator khai báo các phương thức để duyệt một collection, nhưng việc triển khai chúng cụ thể là trách nhiệm của các class triển khai Collection. Mỗi class Collection mà trả về một iterator để duyệt đều có một lớp duyệt lồng của riêng nó. Điều này cho phép các class collection lựa chọn iterator là fail-fast hay fail-safe. Ví dụ, iterator của ArrayList là fail-fast, trong khi đó iterator của CopyOnWriteArrayList là fail-safe.

17. Lỗi UnsupportedOperationException là gì?

UnsupportedOperationException là một loại exception được sử dụng để thông báo rằng một thao tác nào đó không được hỗ trợ. Nó được sử dụng rộng rãi trong các class của JDK. Ví dụ trong trong collections framework, java.util.Collections.UnmodifiableCollection sẽ ném ra lỗi này đối với tất cả các thao tác add và remove.

18. HashMap hoạt động như thế nào trong Java?

HashMap lưu trữ các cặp key-value trong một triển khai Map.Entrysử dụng lớp lồng static. Nó hoạt động dựa trên thuật toán hashing, đồng thời sử dụng các phương thức hashCode() và equals() trong các phương thức put và get của nó.

Khi ta gọi phương thức put bằng cách truyền vào cặp key-value, HashMap sử dụng hashCode() của Key cùng với thuật toán hashing để xác định index nơi cặp key-value này sẽ được lưu trữ. Các Entry trong một bucket của HashMap được tổ chức dưới dạng một LinkedList. Do đó, nếu một bucket (tại index được tính toán) đã có sẵn một entry, HashMap sẽ dùng phương thức equals() để kiểm tra xem key được truyền vào có trùng với key của các entry đã có trong bucket đó không. Nếu trùng, giá trị sẽ được ghi đè. Nếu không trùng, một entry mới sẽ được tạo và thêm vào LinkedList của bucket đó.

Khi ta gọi phương thức get bằng cách truyền vào Key, HashMap lại sử dụng hashCode() để tìm index trong mảng, sau đó dùng phương thức equals() để xác định đúng Entry và trả về giá trị của nó.

Hình bên dưới diễn tả cơ chế này chi tiết hơn:

Những yếu tố quan trọng khác cần biết về HashMap là capacity (dung lượng), load factor (hệ số tải), và threshold resizing (thay đổi kích thước khi đạt ngưỡng). Capacity mặc định ban đầu của HashMap là 16 và load factor là 0.75. Threshold được tính bằng cách lấy capacity nhân với load factor.

Bất cứ khi nào ta cố gắng thêm một entry mới, nếu kích thước của map lớn hơn ngưỡng, HashMap sẽ thực hiện rehash (băm lại) toàn bộ nội dung của map vào một mảng mới với capacity lớn hơn.

Capacity của HashMap luôn là một lũy thừa của 2. Do đó, nếu bạn biết trước rằng mình cần lưu trữ một số lượng lớn các cặp key-value (ví dụ như khi caching dữ liệu từ database), thì nên cân nhắc khởi tạo HashMap với giá trị capacity và load factor phù hợp.

19. Tầm quan trọng của các phương thức hashCode() và equals()?

HashMap sử dụng các phương thức hashCode() và equals() của đối tượng Key để xác định index (chỉ mục) nơi lưu trữ cặp key-value. Các phương thức này cũng được sử dụng khi ta cố gắng lấy giá trị từ HashMap.

Nếu các phương thức này không được triển khai một cách chính xác, hai đối tượng Key khác nhau có thể tạo ra cùng một kết quả cho hashCode() và equals(). Trong trường hợp đó, thay vì được lưu trữ ở các vị trí riêng biệt, HashMap sẽ coi chúng là một và giá trị trước đó sẽ bị ghi đè.

Tương tự, tất cả các class collection không cho phép lưu trữ dữ liệu trùng lặp (ví dụ như Set) đều sử dụng hashCode() và equals() để phát hiện các phần tử trùng lặp. Do đó, việc triển khai đúng các phương thức này có tác dụng rất quan trọng.

Việc triển khai equals() và hashCode() cần tuân theo các quy tắc sau:

• Nếu o1.equals(o2) trả về true, thì o1.hashCode() == o2.hashCode() phải luôn là true.
• Nếu o1.hashCode() == o2.hashCode() là true, điều đó không có nghĩa là o1.equals(o2) cũng sẽ trả về true.

20. Chúng ta có thể sử dụng bất kỳ class nào làm Key cho Map hay không?

Ta có thể sử dụng bất kỳ class nào làm Key cho Map. Tuy nhiên, cần xem xét các điểm sau đây trước khi dùng chúng:

• Nếu class đó ghi đè phương thức equals(), nó cũng nên ghi đè hashCode().
• Class đó phải tuân theo các quy tắc liên quan đến equals() và hashCode() cho tất cả các instance của nó (tham khảo các quy tắc này ở câu hỏi phía trên).
• Nếu một trường (field) của class không được sử dụng trong phương thức equals(), ta cũng không nên sử dụng trường đó trong phương thức hashCode().
• Với một class Key do người dùng định nghĩa, ta nên cho nó immutable (bất biến). Điều này giúp giá trị hashCode() được cache lại để đạt hiệu suất cao hơn. Các class bất biến cũng đảm bảo rằng kết quả của hashCode() và equals() sẽ không thay đổi trong tương lai và giúp tránh các vấn đề phát sinh do tính mutability (khả biến). Đây cũng là lý do tại sao các class như String và Integer (vốn mang tính immutable) thường được sử dụng làm Key cho HashMap.

Ví dụ giả sử ta có một class tên MyKey được dùng làm key cho HashMap:

// Đối số name của MyKey được dùng cho equals() và hashCode()
MyKey key = new MyKey("Pankaj"); // giả sử hashCode=1234
myHashMap.put(key, "Value");

// Đoạn code dưới đây sẽ thay đổi hashCode() và equals() của key
// nhưng vị trí lưu trữ của nó trong HashMap không thay đổi.
key.setName("Amit"); // giả sử hashCode mới=7890

// Lệnh get dưới đây sẽ trả về null. Lý do là HashMap sẽ cố gắng tìm key
// tại cùng một index nơi nó được lưu ban đầu. Nhưng vì key đã bị thay đổi (mutated),
// nên sẽ không có sự trùng khớp nào, dẫn đến việc get trả về null.
myHashMap.get(new MyKey("Pankaj"));

21. Map interface cung cấp những Collection view nào?

Interface Map cung cấp ba collection view:

1. Set<K> keySet(): Trả về một Set view của các key chứa trong map này. Set này liên kết trực tiếp với map, do đó các thay đổi trên map sẽ được thay đổi theo trong set, và ngược lại. Nếu map bị thay đổi trong khi quá trình duyệt qua set đang diễn ra (ngoại trừ thông qua thao tác remove của iterator), kết quả của việc duyệt sẽ không được xác định rõ ràng (undefined). Set này hỗ trợ việc xóa phần tử. Việc này sẽ xóa ánh xạ (mapping) tương ứng khỏi map, thông qua các thao tác Iterator.remove, Set.remove, removeAll, retainAll, và clear. Nó không hỗ trợ các thao tác add hay addAll.
2. Collection<V> values(): Trả về một Collection view của các value chứa trong map này. Collection này liên kết trực tiếp với map, do đó các thay đổi trên map sẽ được phản ánh trong collection, và ngược lại. Nếu map bị thay đổi trong khi quá trình duyệt qua collection đang diễn ra (ngoại trừ thông qua thao tác remove của iterator), kết quả của việc duyệt sẽ là undefined. Collection này hỗ trợ việc xóa phần tử, việc này sẽ xóa mapping tương ứng khỏi map, thông qua các thao tác Iterator.remove, Collection.remove, removeAll, retainAll, và clear. Nó không hỗ trợ các thao tác add hay addAll.
3. Set<Map.Entry<K, V>> entrySet(): Trả về một Set view của các ánh xạ (entry dạng Map.Entry) chứa trong map này. Set này liên kết trực tiếp với map, do đó các thay đổi trên map sẽ được phản ánh trong set, và ngược lại. Nếu map bị thay đổi trong khi quá trình duyệt qua set đang diễn ra (ngoại trừ thông qua thao tác remove của iterator, hoặc thao tác setValue trên một map entry được trả về bởi iterator), kết quả của việc duyệt sẽ là undefined. Set này hỗ trợ việc xóa phần tử, việc này sẽ xóa ánh xạ (mapping) tương ứng khỏi map, thông qua các thao tác Iterator.remove, Set.remove, removeAll, retainAll, và clear. Nó không hỗ trợ các thao tác add hay addAll.

22. Đâu là sự khác biệt giữa HashMap và Hashtable?

HashMap và Hashtable đều triển khai Map interface và trông có vẻ tương tự nhau, Tuy nhiên, giữa chúng có những điểm khác biệt sau:

1. HashMap cho phép key và value mang giá trị null, trong khi Hashtable không cho phép điều này.
2. Hashtable được đồng bộ hóa còn HashMap thì không. Do đó, HashMap phù hợp hơn cho môi trường đơn luồng, còn Hashtable thích hợp cho môi trường đa luồng.
3. LinkedHashMap được thêm vào Java 1.4 như một subclass của HashMap. Vì vậy, nếu muốn duy trì thứ tự khi duyệt, bạn có thể dễ dàng chuyển từ HashMap sang LinkedHashMap. Điều này không thể thực hiện với Hashtable vì thứ tự duyệt của nó không thể đoán trước.
4. HashMap cung cấp một Set chứa các key để duyệt và do đó nó mang tính fail-fast. Ngược lại, Hashtable cung cấp Enumeration các key, vốn không hỗ trợ tính năng này.
5. Hashtable được coi là một class đã lỗi thời (legacy). Nếu bạn cần sửa đổi Map trong khi duyệt, hãy sử dụng ConcurrentHashMap.

23. Làm thế nào để quyết định giữa HashMap và TreeMap?

Để chèn, xóa, và định vị các phần tử trong một Map, HashMap là lựa chọn thay thế tốt nhất. Tuy nhiên, nếu bạn cần duyệt qua các key theo thứ tự đã sắp xếp, TreeMap là phương án tốt hơn.

Tùy thuộc vào kích thước của collection, có thể sẽ nhanh hơn nếu ta thêm các phần tử vào HashMap rồi sau đó chuyển đổi Map đó thành TreeMap để duyệt key theo thứ tự đã sắp xếp.

24. Đâu là những điểm tương đồng và khác biệt giữa ArrayList và Vector?

ArrayList và Vector là các class tương tự nhau về nhiều mặt:

1. Cả hai đều hoạt động dựa trên chỉ mục (index-based) và bên trong sử dụng bởi một array.
2. Cả hai đều duy trì thứ tự chèn và chúng ta có thể lấy các phần tử theo thứ tự đã chèn.
3. Các triển khai của iterator cho ArrayList và Vector đều được thiết kế là fail-fast.
4. ArrayList và Vector đều cho phép giá trị null và truy cập ngẫu nhiên vào phần tử bằng chỉ mục.

Dưới đây là những điểm khác biệt giữa ArrayList và Vector:

1. Vector được đồng bộ hóa trong khi ArrayList thì không. Tuy nhiên, nếu bạn cần sửa đổi list trong khi duyệt, bạn nên sử dụng CopyOnWriteArrayList.
2. ArrayList nhanh hơn Vector vì nó không có gánh nặng xử lý do việc đồng bộ hóa.
3. ArrayList linh hoạt hơn vì chúng ta có thể dễ dàng lấy list synchronized (đồng bộ) hoặc read-only (chỉ đọc) từ nó bằng cách sử dụng utility class Collections.

25. Đâu là sự khác biệt giữa Array và ArrayList? Khi nào bạn sẽ sử dụng Array thay vì ArrayList?

Array có thể chứa kiểu dữ liệu nguyên thủy (primitive) hoặc Object, trong khi ArrayList chỉ có thể chứa Object. Array có kích thước cố định, còn ArrayList có kích thước động.

Array không cung cấp nhiều tính năng như ArrayList, ví dụ như addAll, removeAll, iterator, v.v. Mặc dù ArrayList là lựa chọn hiển nhiên khi làm việc với list, có một vài trường hợp sử dụng array sẽ tốt hơn:

• Nếu list có kích thước cố định và chủ yếu được dùng để lưu trữ và duyệt qua các phần tử.
• Khi list chứa các kiểu dữ liệu primitive. Mặc dù Collections có sử dụng autoboxing (đóng gói tự động) để giảm thiểu công sức code, điều này vẫn làm chậm nó đi khi làm việc với các dữ liệu primitive có kích thước cố định.
• Nếu bạn làm việc với tình huống đa chiều cố định, việc sử dụng [][] sẽ dễ dàng hơn nhiều so với List<List<>>.

26. Đâu là sự khác biệt giữa ArrayList và LinkedList?

ArrayList và LinkedList đều triển khai List interface. Tuy nhiên, có một số khác biệt giữa chúng:

1. ArrayList là một cấu trúc dữ liệu dựa trên chỉ mục (index-based) được hỗ trợ bởi Array, do đó nó cung cấp khả năng truy cập ngẫu nhiên vào các phần tử với hiệu suất O(1). Ngược lại, LinkedList lưu trữ dữ liệu dưới dạng một danh sách các node, trong đó mỗi node được liên kết với node trước và node sau nó. Vì vậy, mặc dù có phương thức để lấy phần tử bằng chỉ mục, bên trong nó phải duyệt từ đầu để đến được node tại chỉ mục đó rồi mới trả về phần tử. Do đó hiệu suất hoạt động của LinkedList là O(n), chậm hơn ArrayList.
2. Việc chèn, thêm hoặc xóa một phần tử trong LinkedList nhanh hơn so với ArrayList vì không có khái niệm thay đổi kích thước array hoặc cập nhật chỉ mục khi phần tử được thêm vào giữa.
3. LinkedList tiêu tốn nhiều bộ nhớ hơn ArrayList vì mỗi node trong LinkedList lưu trữ tham chiếu đến phần tử trước và sau nó.

27. Những lớp collection nào cung cấp khả năng truy cập ngẫu nhiên vào các phần tử của nó?

Các class ArrayList, HashMap, TreeMap, Hashtable, và Vector cung cấp khả năng truy cập ngẫu nhiên vào các phần tử của chúng. Xem thêm file này để biết hiểu rõ hơn.

28. EnumSet là gì?

java.util.EnumSet là một triển khai của Set được sử dụng với các kiểu enum. Tất cả các phần tử trong một enum set phải thuộc về một kiểu enum duy nhất được chỉ định (tường minh hoặc ngầm định) khi set được tạo.

EnumSet không được đồng bộ và không cho phép phần tử null. Nó cũng cung cấp một số phương thức hữu ích như copyOf(Collection c), of(E first, E… rest) và complementOf(EnumSet s).

29. Những lớp collection có tính an toàn luồng?

Vector, Hashtable, Properties và Stack là các class được đồng bộ, do đó chúng mang tính thread-safe và có thể được sử dụng trong môi trường đa luồng.

Concurrent API trong Java 1.5 bao gồm một số class collection cho phép sửa đổi collection trong khi duyệt vì chúng làm việc trên một bản sao (clone) của collection. Do đó chúng hoạt động an toàn trong môi trường đa luồng.

30. Lớp Concurrent Collection là gì?

Gói java.util.concurrent trong Java 1.5 chứa các class collection mang tính thread-safe và cho phép sửa đổi collection trong khi duyệt.

Theo thiết kế, các triển khai của Iterator trong gói java.util là fail-fast và sẽ cho ra lỗi ConcurrentModificationException. Tuy nhiên, các triển khai của Iterator trong gói java.util.concurrent là fail-safe và chúng ta có thể sửa đổi collection trong khi duyệt. Một số class này là CopyOnWriteArrayList, ConcurrentHashMap, CopyOnWriteArraySet.

31. BlockingQueue là gì?

java.util.concurrent.BlockingQueue là một Queue hỗ trợ các hoạt động chờ cho đến khi queue không còn trống lúc lấy hoặc xóa một phần tử, và chờ cho đến khi có không gian trống trong queue lúc thêm một phần tử.

Interface BlockingQueue là một phần của Java Collections Framework và chủ yếu được sử dụng để triển khai bài toán sản xuất-tiêu thụ (producer-consumer). Chúng ta không cần lo lắng về việc phải chờ không gian trống cho producer hay chờ đối tượng cho consumer trong BlockingQueue .

Lý do là vì các class triển khai của BlockingQueue đã xử lý việc này. Java cung cấp một số triển khai BlockingQueue như ArrayBlockingQueue, LinkedBlockingQueue, PriorityBlockingQueue, SynchronousQueue, v.v.

32. Queue và Stack là gì, hãy liệt kê sự khác biệt của chúng?

Cả Queue và Stack đều được dùng để lưu trữ dữ liệu trước khi xử lý. java.util.Queue là một interface mà các class triển khai của nó nằm trong package java.util.concurrent. Queue thường cho phép lấy phần tử theo thứ tự FIFO (First-In-First-Out, vào trước ra trước), nhưng không phải lúc nào cũng vậy. Còn có interface Deque cho phép lấy phần tử từ cả hai đầu của queue.

Stack tương tự như Queue, ngoại trừ việc nó cho phép lấy phần tử theo thứ tự LIFO (Last-In-First-Out, vào sau ra trước). Stack là một class kế thừa từ Vector, trong khi Queue là một interface.

33. Lớp Collections là gì?

java.util.Collections là một class tiện ích chỉ bao gồm các phương thức static hoạt động trên hoặc trả về các collection. Nó chứa các thuật toán đa hình (polymorphic algorithm) hoạt động trên collection, các wrapper (trả về một collection mới được hỗ trợ bởi một collection được chỉ định), và một vài tiện ích khác.

Class này chứa các phương thức cho các thuật toán của Collection Framework, chẳng hạn như tìm kiếm nhị phân (binary search), sắp xếp (sorting), xáo trộn (shuffling), đảo ngược (reverse), v.v.

34. Các interface Comparable và Comparator là gì?

Bất kỳ class tùy chỉnh nào cũng nên triển khai interface Comparable nếu chúng ta muốn sử dụng các phương thức sắp xếp của Arrays hoặc Collections. Interface này có một phương thức compareTo(T obj) được các phương thức sắp xếp sử dụng. Chúng ta nên ghi đè (override) phương thức này sao cho nó trả về một số nguyên âm, không, hoặc một số nguyên dương nếu đối tượng “this” lần lượt nhỏ hơn, bằng, hoặc lớn hơn đối tượng được truyền vào làm tham số.

Tuy nhiên, hầu hết trong thực tế, chúng ta muốn sắp xếp dựa trên các tham số khác nhau. Ví dụ, một CEO có thể muốn sắp xếp nhân viên dựa trên Lương, trong khi một HR lại muốn sắp xếp họ dựa trên tuổi.

Đây là tình huống mà chúng ta cần sử dụng interface Comparator. Lý do là vì việc triển khai phương thức Comparable.compareTo(Object o) chỉ có thể sắp xếp dựa trên một trường duy nhất và chúng ta không thể chọn trường mà mình muốn dùng để sắp xếp đối tượng.

Phương thức compare(Object o1, Object o2) của interface Comparator cần được triển khai để nhận hai tham số Object. Nó nên được triển khai để trả về số nguyên âm nếu tham số đầu tiên nhỏ hơn tham số thứ hai, trả về không nếu chúng bằng nhau, và trả về số nguyên dương nếu tham số đầu tiên lớn hơn tham số thứ hai.

35. Sự khác biệt giữa interface Comparable và Comparator là gì?

Interface Comparable và Comparator được sử dụng để sắp xếp một collection hoặc mảng chứa các object (đối tượng). Interface Comparable được dùng để cung cấp cách sắp xếp tự nhiên cho các object và chúng ta có thể sử dụng nó để sắp xếp dựa trên một logic duy nhất. Interface Comparator được dùng để cung cấp các thuật toán sắp xếp khác nhau và chúng ta có thể chọn Comparator mà mình muốn sử dụng để sắp xếp một collection object nhất định.

36. Làm thế nào để chúng ta có thể sắp xếp một danh sách các Object?

Nếu chúng ta cần sắp xếp một mảng chứa các object, ta có thể sử dụng Arrays.sort(). Nếu chúng ta cần sắp xếp một danh sách các object, ta có thể sử dụng Collections.sort().

Cả hai class này đều có các phương thức sort() được nạp chồng (overloaded) cho việc sắp xếp tự nhiên (sử dụng Comparable) hoặc sắp xếp dựa trên tiêu chí (sử dụng Comparator). Vì bên trong Collections sử dụng phương thức sắp xếp của Arrays, cả hai đều có hiệu suất tương tự, ngoại trừ việc Collections mất một chút thời gian để chuyển đổi List thành Array.

37. Khi truyền một Collection làm tham số cho một hàm, làm thế nào chúng ta có thể đảm bảo hàm đó không thể sửa đổi nó?

Chúng ta có thể tạo một collection chỉ đọc (read-only) bằng cách sử dụng phương thức Collections.unmodifiableCollection(Collection c) trước khi truyền nó làm tham số. Điều này sẽ đảm bảo rằng bất kỳ thao tác nào nhằm thay đổi collection sẽ cho ra lỗi UnsupportedOperationException.

38. Làm thế nào chúng ta có thể tạo một collection được đồng bộ hóa từ một collection đã cho?

Chúng ta có thể sử dụng Collections.synchronizedCollection(Collection c) để lấy một collection được đồng bộ hóa (an toàn luồng) từ một collection đã chỉ định.

39. Các thuật toán phổ biến nào được triển khai trong Collections Framework?

Java Collections Framework cung cấp các thuật toán thường được sử dụng như sắp xếp (sorting) và tìm kiếm (searching). Cụ thể, class Collections chứa các phương thức triển khai của chúng.

Hầu hết các thuật toán này hoạt động trên List, nhưng một số cũng áp dụng được cho tất cả các loại collection. Một vài ví dụ trong số đó là sắp xếp, tìm kiếm, xáo trộn (shuffling), tìm giá trị min-max.

40. Ký hiệu Big-O là gì? Cho một vài ví dụ.

Ký hiệu Big-O (Big-O notation) mô tả hiệu suất của một thuật toán dựa trên số lượng phần tử trong một cấu trúc dữ liệu. Vì các class Collection là các cấu trúc dữ liệu, chúng ta thường có xu hướng sử dụng Big-O để chọn triển khai collection phù hợp dựa trên thời gian, bộ nhớ và hiệu suất.

Ví dụ 1: ArrayList get(index i) là một thao tác có thời gian hằng số và không phụ thuộc vào số lượng phần tử trong danh sách. Vì vậy, hiệu suất của nó theo Big-O là O(1). Ví dụ 2: Hiệu suất của một tìm kiếm tuyến tính (linear search) trên mảng hoặc danh sách là O(n) vì chúng ta cần duyệt qua toàn bộ danh sách phần tử để tìm thấy phần tử mong muốn.

41. Nêu những nguyên tắc khi làm việc với Collections Framework?

• Chọn đúng loại collection dựa trên nhu cầu. Ví dụ, nếu cần kích thước cố định, có thể dùng Array thay vì ArrayList. Nếu phải duyệt qua Map theo thứ tự chèn, bạn sẽ cần LinkedHashMap. Nếu không muốn có phần tử trùng lặp, nên dùng Set.
• Một số class collection cho phép chỉ định dung lượng khởi tạo (initial capacity). Vì vậy, nếu ước tính được số lượng phần tử sẽ lưu trữ, có thể sử dụng nó để tránh việc băm lại (rehashing) hoặc thay đổi kích thước.
• Viết chương trình dựa trên interface chứ không phải triển khai (implementation). Điều này cho phép chúng ta dễ dàng thay đổi triển khai sau này.
• Luôn sử dụng Generics để đảm bảo an toàn kiểu (type-safety) và tránh lỗi ClassCastException lúc runtime.
• Sử dụng các class bất biến (immutable) do JDK cung cấp làm key trong Map để tránh việc phải tự triển khai hashCode() và equals() cho class tùy chỉnh của chúng ta.
• Thay vì tự viết triển khai riêng, hãy sử dụng class tiện ích Collections có sẵn nhiều nhất có thể cho các thuật toán hoặc để lấy các collection chỉ đọc, đồng bộ hóa hoặc rỗng. Điều này sẽ tăng cường khả năng tái sử dụng code, mang lại sự ổn định cao hơn và chi phí bảo trì thấp.

42. Java Priority Queue là gì?

PriorityQueue là một queue (hàng đợi) không giới hạn (unbounded) dựa trên một heap ưu tiên. Các phần tử trong đó được sắp xếp theo thứ tự tự nhiên của chúng, hoặc chúng ta có thể cung cấp một Comparator để định nghĩa thứ tự sắp xếp tại thời điểm tạo queue.

PriorityQueue không cho phép giá trị null. Chúng ta cũng không thể thêm bất kỳ đối tượng nào không cung cấp thứ tự tự nhiên (natural ordering) hoặc không có Comparator tương ứng để sắp xếp chúng.

Java PriorityQueue không có tính an toàn luồng (thread-safe) và có hiệu suất thời gian O(log n) cho các thao tác enqueue và dequeue.

43. Tại sao chúng ta không thể viết code dạng List<Number> numbers = new ArrayList<Integer>();?

Generics không hỗ trợ sub-typing (kiểu con) vì sẽ gây ra các vấn đề trong việc đảm bảo an toàn kiểu. Đó là lý do tại sao List<T> không được coi là một kiểu con của List<S>, ngay cả khi S là kiểu cha (super-type) của T.

Để hiểu tại sao điều này không được cho phép trong Java, hãy xem thử điều gì có thể xảy ra nếu nó được hỗ trợ:

List<Long> listLong = new ArrayList<Long>();
listLong.add(Long.valueOf(10));
List<Number> listNumbers = listLong; // lỗi biên dịch
listNumbers.add(Double.valueOf(1.23));

Nếu generics hỗ trợ sub-typing, chúng ta có thể dễ dàng thêm một đối tượng Double vào một danh sách List<Integer>. Điều này sẽ dẫn đến lỗi ClassCastException lúc runtime khi chúng ta cố gắng lấy một phần tử từ danh sách đó và ép kiểu nó thành Integer.

44. Tại sao chúng ta không thể tạo mảng generic? Hoặc viết code như List<Integer>[] array = new ArrayList<Integer>[10];

Chúng ta không được phép tạo mảng generic vì mảng (array) mang thông tin kiểu của các phần tử của nó vào lúc runtime. Thông tin này được sử dụng lúc runtime để cho ra ArrayStoreException nếu kiểu của phần tử không khớp với kiểu đã được định nghĩa cho mảng.

Vì thông tin kiểu của generics bị xóa bỏ vào lúc biên dịch bởi cơ chế Type Erasure, nên việc kiểm tra khi lưu trữ vào mảng sẽ diễn ra thành công, trong khi đáng lẽ nó phải thất bại.

Hãy xem ví dụ sau để hiểu thêm điều này:

List<Integer>[] intList = new List<Integer>[5]; // lỗi biên dịch
Object[] objArray = intList;
List<Double> doubleList = new ArrayList<Double>();
doubleList.add(Double.valueOf(1.23));
objArray[0] = doubleList; // Điều này lẽ ra phải gây ra lỗi nhưng nó vẫn thành công vì tại thời điểm chạy (runtime), intList và doubleList cả hai đều là kiểu List

Mảng có tính hiệp biến (covariant) tự nhiên, tức là S[] là một kiểu con của T[] bất cứ khi nào S là một kiểu con của T. Tuy nhiên, generics không hỗ trợ tính hiệp biến hay sub-typing, như chúng ta đã thấy ở câu hỏi trước.

Do đó, nếu chúng ta được phép tạo mảng generic, thì do Type Erasure, chúng ta sẽ không nhận được ArrayStoreException ngay cả khi các kiểu không tương thích với nhau. Điều này phá vỡ tính an toàn kiểu của mảng.

Tổng kết

Chúng tôi sẽ cố gắng tiếp tục bổ sung thêm các câu hỏi khác về Java Collections Framework vào bài này trong tương lai. Nếu bạn thấy bài viết này hữu ích, đừng ngần ngại chia sẻ nó cho mọi người nhé. Nếu bạn cảm thấy có câu hỏi quan trọng nào đã bị bỏ sót, hãy báo cho chúng tôi qua phần comment bên dưới. Chúng tôi sẽ cố gắng trả lời và cập nhật chúng để bài hướng dẫn này được hoàn thiện hơn.