Collection trong Java (Java Collections)

1. Java Collection là gì?

Java Collection là một framework trong Java dùng để quản lý và thao tác với các nhóm đối tượng. Nó cung cấp một tập hợp các cấu trúc dữ liệu và các thuật toán để xử lý dữ liệu như thêm, xóa, duyệt qua, và sắp xếp các phần tử. Java Collection bao gồm các giao diện và lớp giúp lập trình viên dễ dàng quản lý dữ liệu theo cách hiệu quả hơn.

1. Interfaces

• Collection: Interface cơ sở cho tất cả các tập hợp. Nó định nghĩa các phương thức cơ bản như add(), remove(), size(), iterator(),…
• List: Interface mở rộng từ Collection, đại diện cho một tập hợp có thứ tự và cho phép các phần tử trùng lặp. Ví dụ: ArrayList, LinkedList.
• Set: Interface không cho phép các phần tử trùng lặp. Ví dụ: HashSet, LinkedHashSet, TreeSet.
• Map: Interface cho phép lưu trữ các cặp khóa-giá trị, trong đó mỗi khóa là duy nhất. Ví dụ: HashMap, TreeMap, LinkedHashMap.
• Queue: Interface đại diện cho một tập hợp cho phép xử lý các phần tử theo thứ tự, thường theo nguyên tắc FIFO (First In First Out). Ví dụ: LinkedList, PriorityQueue.

3. Classes

• ArrayList: Một danh sách có thể thay đổi kích thước được triển khai dưới dạng mảng động.
• LinkedList: Một danh sách sử dụng cấu trúc dữ liệu danh sách liên kết cho phép thêm và xóa nhanh chóng.
• HashSet: Một tập hợp không cho phép các phần tử trùng lặp và không duy trì thứ tự.
• LinkedHashSet: Giống như HashSet nhưng duy trì thứ tự chèn các phần tử.
• TreeSet: Một tập hợp cho phép tự động sắp xếp các phần tử.
• HashMap: Một ánh xạ không duy trì thứ tự cho phép các cặp khóa-giá trị.
• LinkedHashMap: Giống như HashMap nhưng duy trì thứ tự chèn các mục.
• TreeMap: Một ánh xạ sắp xếp các khóa theo thứ tự tự nhiên hoặc theo trình soạn thảo của một Comparator.

4. Algorithms

JCF cũng cung cấp một số thuật toán hữu ích để thao tác với các cấu trúc dữ liệu như:

• sort(): Sắp xếp các phần tử trong một danh sách.
• shuffle(): Xáo trộn các phần tử trong một danh sách.
• reverse(): Đảo ngược thứ tự của các phần tử trong một danh sách.
• binarySearch(): Tìm kiếm nhị phân trong một danh sách đã được sắp xếp.

5. Generics

Java Collections Framework hỗ trợ generics cho phép bạn chỉ định loại dữ liệu mà tập hợp sẽ chứa. Điều này giúp tăng cường tính an toàn kiểu (type safety) và giảm thiểu lỗi runtime.

6. Sự khác biệt giữa các Collections

• List: Có thứ tự cho phép trùng lặp.
• Set: Không có thứ tự không cho phép trùng lặp.
• Map: Không có thứ tự (trong trường hợp của HashMap) cho phép khóa duy nhất và giá trị có thể trùng lặp.

import java.util.ArrayList;
import java.util.HashMap;

public class App {
    public static void main(String[] args) {
        // Sử dụng ArrayList
        List<String> fruits = new ArrayList<>();
        fruits.add("Táo");
        fruits.add("Chuối");
        fruits.add("Xoài");
        System.out.println("Fruits: " + fruits);

        // Sử dụng HashMap
        HashMap<String, Integer> map = new HashMap<>();
        ageMap.put("Dâu", 10);
        ageMap.put("Tây", 20);
        System.out.println("Tây: " + map.get("Tây") + " tuổi");
    }
}

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

I. Câu hỏi cơ bản:

1. Java Collections Framework là gì?

Trả lời:

Java Collections Framework là một tập hợp các cấu trúc dữ liệu (như List, Set, Map, Queue) và các lớp hỗ trợ quản lý dữ liệu (thêm, xóa, duyệt, tìm kiếm, sắp xếp).

2. Sự khác nhau giữa List, Set và Map là gì?

Trả lời:

• List: Lưu trữ các phần tử theo thứ tự và cho phép trùng lặp.
• Set: Không lưu trữ phần tử trùng lặp và không bảo đảm thứ tự.
• Map: Lưu trữ cặp khóa – giá trị và mỗi khóa là duy nhất.

3. ArrayList và LinkedList khác nhau như thế nào?

Trả lời:

• ArrayList: Dựa trên mảng động, có thể truy cập nhanh các phần tử bằng chỉ số, nhưng việc thêm/xóa phần tử ở giữa tốn thời gian.
• LinkedList: Dựa trên danh sách liên kết, thêm/xóa phần tử nhanh, nhưng truy cập ngẫu nhiên chậm.

4. HashMap và TreeMap khác nhau như thế nào?

Trả lời:

• HashMap: Không đảm bảo thứ tự của các phần tử, sử dụng hàm băm để lưu trữ và truy xuất dữ liệu nhanh.
• TreeMap: Duy trì thứ tự các phần tử theo thứ tự tự nhiên hoặc theo Comparator tùy chỉnh.

5. Iterator là gì? Sự khác nhau giữa Iterator và ListIterator?

Trả lời:

• Iterator: Dùng để duyệt qua các phần tử của Collection theo một chiều.
• ListIterator: Mở rộng từ Iterator, cho phép duyệt hai chiều và chỉnh sửa phần tử.

II. Câu hỏi nâng cao:

1. HashSet hoạt động như thế nào?

Trả lời:

HashSet sử dụng một HashMap bên trong để lưu trữ các phần tử. Mỗi phần tử trong HashSet là một khóa trong HashMap và giá trị luôn là một object mặc định.

2. Tại sao hashCode() và equals() lại quan trọng trong HashMap?

Trả lời:

hashCode() xác định vị trí (bucket) trong HashMap và equals() dùng để so sánh khóa khi có xung đột về hashCode. Việc cài đặt không đúng hai phương thức này có thể dẫn đến việc các phần tử trùng lặp không bị phát hiện.

3. Bạn có thể giải thích khái niệm “fail-fast” trong Java Collections không?

Trả lời:

Fail-fast là cơ chế mà khi một Collection bị thay đổi trong quá trình duyệt (ví dụ: thêm, xóa phần tử) sẽ ném ra một ConcurrentModificationException.

4. Sự khác biệt giữa ConcurrentHashMap và HashMap là gì?

Trả lời:

• HashMap: Không thread-safe, không thích hợp trong môi trường đa luồng.
• ConcurrentHashMap: Thread-safe, cho phép nhiều luồng có thể đọc và ghi mà không cần khóa toàn bộ Collection.

5. Bạn có thể nêu ví dụ về một số thuật toán có sẵn trong Java Collections?

Trả lời:

• Sắp xếp: Collections.sort(list)
• Đảo ngược: Collections.reverse(list)
• Tìm kiếm nhị phân: Collections.binarySearch(list, key)

6. Sự khác biệt giữa Synchronized Collection và Concurrent Collection là gì?

Trả lời:

• Synchronized Collection: Sử dụng khóa để đồng bộ hóa, ví dụ: Collections.synchronizedList(new ArrayList<>()). Cần khóa toàn bộ Collection để đảm bảo thread-safe.
• Concurrent Collection: Cho phép các thao tác đồng thời mà không cần khóa toàn bộ Collection, ví dụ: ConcurrentHashMap.

7. Tại sao Set không cho phép phần tử trùng lặp?

Trả lời:

Set sử dụng các thuật toán dựa trên hashing hoặc so sánh (Comparator) để đảm bảo không có phần tử trùng lặp. Khi phần tử mới thêm vào trùng với phần tử đã có, Set sẽ từ chối thêm.

8. WeakHashMap là gì? Tại sao nó lại hữu ích?

Trả lời:

WeakHashMap là một triển khai của Map trong đó các khóa là “weak references” (tham chiếu yếu). Điều này có nghĩa là nếu không có tham chiếu mạnh đến khóa, bộ dọn rác (GC) sẽ thu gom nó, giúp tránh tình trạng rò rỉ bộ nhớ.

import java.util.WeakHashMap;

public class App {
    public static void main(String[] args) {
        WeakHashMap<String, String> weakMap = new WeakHashMap<>();
        
        // Tạo một đối tượng khóa và thêm nó vào WeakHashMap
        String key1 = new String("Key1");
        String value1 = "Value1";
        weakMap.put(key1, value1);

        // Tạo một đối tượng khác và thêm vào WeakHashMap
        String key2 = new String("Key2");
        String value2 = "Value2";
        weakMap.put(key2, value2);

        // In WeakHashMap trước khi GC thu gom
        System.out.println("Before GC: " + weakMap);

        // Loại bỏ tham chiếu mạnh đến key1
        key1 = null; // gán giá trị rỗng cho key1

        // Yêu cầu bộ dọn rác chạy
        System.gc();

        // Đợi một thời gian để GC hoàn thành
        try {
            Thread.sleep(1000); // tạm dừng 1 giây
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

        // In WeakHashMap sau khi GC có thể đã thu gom key1
        System.out.println("After GC: " + weakMap);
    }
}

9. Sự khác biệt giữa TreeSet và TreeMap là gì?

Trả lời:

• TreeSet: Lưu trữ các phần tử không trùng lặp trong thứ tự tự nhiên hoặc theo Comparator tùy chỉnh.
• TreeMap: Lưu trữ các cặp khóa – giá trị theo thứ tự của khóa, giống như TreeSet nhưng với cặp khóa-giá trị.

10. Bạn có biết về các cấu trúc dữ liệu Immutable trong Java không?

Trả lời:

Immutable Collection là các Collection không thể thay đổi sau khi khởi tạo. Java 9 cung cấp các phương thức như List.of(), Set.of(), Map.of() để tạo các Collection immutable. Chúng giúp tránh tình trạng thay đổi bất ngờ trong môi trường đa luồng.

III. Câu hỏi thực hành:

1. Viết một đoạn code để duyệt qua tất cả các phần tử của một HashMap mà không sử dụng Iterator.

import java.util.HashMap;
import java.util.Map;

public class App {
    public static void main(String[] args) {
        // Tạo một HashMap và thêm một vài phần tử
        HashMap<String, Integer> map = new HashMap<>();
        map.put("Cam", 3);
        map.put("Quýt", 2);
        map.put("Mít", 5);
        map.put("Dừa", 7);

        // Duyệt qua tất cả các phần tử của HashMap bằng for-each
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            String key = entry.getKey();
            Integer value = entry.getValue();
            System.out.println("Key: " + key + ", Value: " + value);
        }
    }
}

2. Làm thế nào để kiểm tra xem một List có chứa các phần tử trùng lặp không?

Trả lời:

Để kiểm tra xem một List có chứa các phần tử trùng lặp hay không, bạn có thể sử dụng một số phương pháp trong đó cách phổ biến nhất là sử dụng một Set. Vì Set không cho phép các phần tử trùng lặp, bạn có thể thêm tất cả các phần tử từ List vào Set, sau đó so sánh kích thước của List và Set. Nếu kích thước của List lớn hơn Set, nghĩa là List có chứa các phần tử trùng lặp.
– Ví dụ:

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class App {
    public static void main(String[] args) {
        // Tạo một List
        List list = new ArrayList<>();
        list.add("Táo");
        list.add("Ổi");
        list.add("Xoài");  // Phần tử trùng lặp
        list.add("Lê");

        // Sử dụng Set để kiểm tra trùng lặp
        Set set = new HashSet<>(list);
        if (set.size() < list.size()) {
            System.out.println("List có phần tử trùng lặp.");
        } else {
            System.out.println("List không có phần tử trùng lặp.");
        }
    }
}