1-1. Tìm kiếm nhị phân

Mô tả thuật toán

Tìm kiếm nhị phân là một thuật toán hiệu quả để tìm kiếm một giá trị cụ thể trong một mảng đã được sắp xếp. Nguyên tắc hoạt động của nó dựa trên việc liên tục chia đôi không gian tìm kiếm. Các bước cơ bản bao gồm:

1. **Điều kiện tiên quyết**: Mảng đầu vào phải được sắp xếp (ví dụ, theo thứ tự tăng dần).
2. **Xác định phạm vi tìm kiếm**: Bắt đầu với một chỉ số trái (low) và một chỉ số phải (high) đại diện cho phạm vi tìm kiếm hiện tại.
3. **Lặp lại quá trình tìm kiếm**: Trong khi low nhỏ hơn hoặc bằng high, thực hiện các bước sau:
1. **Tính chỉ số giữa**: Tìm chỉ số giữa (mid) của phạm vi hiện tại (mid = low + (high - low) / 2).
2. **So sánh giá trị**: So sánh phần tử tại mid với giá trị mục tiêu (target):
• Nếu arr[mid] == target: Tìm thấy phần tử, trả về chỉ số mid.
• Nếu arr[mid] > target: Giá trị mục tiêu nhỏ hơn phần tử giữa. Loại bỏ nửa phải của phạm vi, cập nhật high = mid - 1.
• Nếu arr[mid] < target: Giá trị mục tiêu lớn hơn phần tử giữa. Loại bỏ nửa trái của phạm vi, cập nhật low = mid + 1.
4. **Kết thúc**: Nếu vòng lặp kết thúc mà không tìm thấy phần tử (tức là low > high), trả về -1 để chỉ ra rằng phần tử không có trong mảng.

Triển khai thuật toán

public class BinarySearchUtility {

    public static void main(String[] args) {
        int[] sortedArray = {24, 33, 45, 56, 58, 62, 74, 89, 102};
        int targetValue = 74;

        int foundIndex = performBinarySearch(sortedArray, targetValue);

        if (foundIndex != -1) {
            System.out.println("Giá trị " + targetValue + " được tìm thấy tại chỉ số: " + foundIndex);
        } else {
            System.out.println("Giá trị " + targetValue + " không có trong mảng.");
        }
    }

    private static int performBinarySearch(int[] arr, int target) {
        int leftPointer = 0;
        int rightPointer = arr.length - 1;

        while (leftPointer <= rightPointer) {
            // Tính chỉ số giữa, sử dụng phép dịch bit để tránh tràn số và tăng hiệu suất
            int middleIndex = (leftPointer + rightPointer) >>> 1;

            if (arr[middleIndex] == target) {
                return middleIndex; // Tìm thấy
            } else if (arr[middleIndex] > target) {
                rightPointer = middleIndex - 1; // Tìm ở nửa trái
            } else {
                leftPointer = middleIndex + 1; // Tìm ở nửa phải
            }
        }
        return -1; // Không tìm thấy
    }
}

Các trường hợp đặc biệt

Khi tìm kiếm nhị phân, số lần so sánh phụ thuộc vào vị trí của phần tử và kích thước mảng. Ví dụ:

1. Với mảng {1, 5, 8, 11, 19, 22, 31, 35, 40, 45, 48, 49, 50}, tìm giá trị 48 cần 4 lần so sánh.
2. Trong mảng 128 phần tử, số lần so sánh tối đa không quá 7 (log₂128 = 7).

1-2. Sắp xếp nổi bọt (Bubble Sort)

Mô tả thuật toán

Sắp xếp nổi bọt là một thuật toán sắp xếp đơn giản hoạt động bằng cách lặp đi lặp lại việc đi qua danh sách, so sánh từng cặp phần tử liền kề và hoán đổi chúng nếu chúng sai thứ tự. Quá trình này được lặp lại cho đến khi không có cặp nào cần hoán đổi, cho thấy danh sách đã được sắp xếp.

1. **So sánh và hoán đổi**: Bắt đầu từ đầu danh sách, so sánh phần tử hiện tại với phần tử kế tiếp. Nếu phần tử hiện tại lớn hơn phần tử kế tiếp, hoán đổi vị trí của chúng.
2. **Vòng lặp**: Lặp lại bước 1 cho tất cả các cặp phần tử liền kề trong danh sách. Sau mỗi lần đi qua toàn bộ danh sách (một "lượt nổi bọt"), phần tử lớn nhất còn lại sẽ "nổi" lên vị trí cuối cùng của phần chưa được sắp xếp.
3. **Lặp lại các lượt**: Lặp lại quá trình này cho phần còn lại của danh sách (không bao gồm các phần tử đã được sắp xếp ở cuối) cho đến khi không còn phần tử nào để so sánh hoặc danh sách đã được sắp xếp hoàn toàn.

Triển khai thuật toán (có tối ưu)

import java.util.Arrays;

public class BubbleSortAlgorithm {

    public static void main(String[] args) {
        int[] dataSet = {5, 1, 4, 2, 8};
        System.out.println("Mảng gốc: " + Arrays.toString(dataSet));
        optimizedBubbleSort(dataSet);
        System.out.println("Mảng đã sắp xếp: " + Arrays.toString(dataSet));
    }

    // Phương thức trợ giúp để hoán đổi hai phần tử
    private static void swapElements(int[] arr, int idx1, int idx2) {
        int temp = arr[idx1];
        arr[idx1] = arr[idx2];
        arr[idx2] = temp;
    }

    /**
     * Triển khai sắp xếp nổi bọt với hai tối ưu hóa:
     * 1. Giảm phạm vi vòng lặp bên trong sau mỗi lượt.
     * 2. Dừng sớm nếu không có hoán đổi nào xảy ra trong một lượt.
     */
    private static void optimizedBubbleSort(int[] arr) {
        int n = arr.length;
        boolean swappedOccurred; // Cờ theo dõi việc hoán đổi
        
        for (int i = 0; i < n - 1; i++) {
            swappedOccurred = false; // Đặt lại cờ cho mỗi lượt
            for (int j = 0; j < n - 1 - i; j++) { // Phạm vi giảm dần
                if (arr[j] > arr[j + 1]) {
                    swapElements(arr, j, j + 1);
                    swappedOccurred = true; // Đánh dấu đã có hoán đổi
                }
            }
            System.out.println("Sau lượt " + (i + 1) + ": " + Arrays.toString(arr));
            if (!swappedOccurred) {
                // Nếu không có hoán đổi nào trong lượt này, mảng đã sắp xếp
                break; 
            }
        }
    }
}

Các điểm tối ưu hóa

1. **Giảm phạm vi lặp**: Sau mỗi lượt nổi bọt, phần tử lớn nhất đã được đưa về đúng vị trí cuối cùng của phạm vi chưa sắp xếp. Do đó, ở lượt tiếp theo, vòng lặp bên trong có thể chạy ít hơn một lần.
2. **Dừng sớm**: Nếu trong một lượt quét toàn bộ danh sách mà không có bất kỳ cặp nào được hoán đổi, điều đó có nghĩa là danh sách đã được sắp xếp hoàn toàn và thuật toán có thể dừng lại.

1-3. Sắp xếp chọn (Selection Sort)

Mô tả thuật toán

Sắp xếp chọn là một thuật toán sắp xếp tại chỗ (in-place) hoạt động bằng cách chia mảng thành hai phần: một phần đã được sắp xếp ở bên trái và một phần chưa được sắp xếp ở bên phải. Thuật toán liên tục tìm phần tử nhỏ nhất (hoặc lớn nhất) từ phần chưa được sắp xếp và đưa nó vào cuối phần đã được sắp xếp.

1. **Phân chia mảng**: Chia mảng thành hai vùng: vùng đã sắp xếp (ban đầu rỗng) và vùng chưa sắp xếp (ban đầu là toàn bộ mảng).
2. **Tìm kiếm và hoán đổi**: Trong mỗi bước lặp, tìm phần tử nhỏ nhất (giả sử sắp xếp tăng dần) trong vùng chưa sắp xếp.
3. **Chèn vào vùng đã sắp xếp**: Hoán đổi phần tử nhỏ nhất tìm được với phần tử đầu tiên của vùng chưa sắp xếp (tức là phần tử ngay sau vùng đã sắp xếp).
4. **Lặp lại**: Lặp lại quá trình này cho đến khi vùng chưa sắp xếp trở nên rỗng, lúc đó toàn bộ mảng đã được sắp xếp.

Triển khai thuật toán

import java.util.Arrays;

public class SelectionSortAlgorithm {

    public static void main(String[] args) {
        int[] dataSet = {64, 25, 12, 22, 11};
        System.out.println("Mảng gốc: " + Arrays.toString(dataSet));
        performSelectionSort(dataSet);
        System.out.println("Mảng đã sắp xếp: " + Arrays.toString(dataSet));
    }

    // Phương thức trợ giúp để hoán đổi hai phần tử
    private static void swapElements(int[] arr, int idx1, int idx2) {
        int temp = arr[idx1];
        arr[idx1] = arr[idx2];
        arr[idx2] = temp;
    }

    /**
     * Triển khai sắp xếp chọn.
     */
    private static void performSelectionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i; // Giả sử phần tử hiện tại là nhỏ nhất
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j; // Tìm thấy phần tử nhỏ hơn
                }
            }
            // Hoán đổi phần tử nhỏ nhất tìm được với phần tử tại vị trí i
            if (minIndex != i) {
                swapElements(arr, i, minIndex);
            }
            System.out.println("Sau lượt " + (i + 1) + ": " + Arrays.toString(arr));
        }
    }
}

So sánh với Sắp xếp nổi bọt

1. **Độ phức tạp thời gian**: Cả hai đều có độ phức tạp thời gian trung bình là O(n²).
2. **Số lần hoán đổi**: Sắp xếp chọn thường nhanh hơn sắp xếp nổi bọt vì nó thực hiện ít hoán đổi hơn (chỉ một hoán đổi mỗi lượt).
3. **Hiệu suất với mảng gần sắp xếp**: Nếu mảng đã gần sắp xếp, sắp xếp nổi bọt có thể có hiệu suất tốt hơn (với tối ưu hóa dừng sớm) so với sắp xếp chọn, vì sắp xếp chọn luôn quét toàn bộ phần chưa sắp xếp.
4. **Tính ổn định**:
   • **Sắp xếp nổi bọt** là một thuật toán sắp xếp **ổn định**. Điều này có nghĩa là nếu có hai phần tử có giá trị bằng nhau, thứ tự tương đối của chúng sẽ được giữ nguyên sau khi sắp xếp.
   • **Sắp xếp chọn** là một thuật toán sắp xếp **không ổn định**. Thứ tự tương đối của các phần tử có giá trị bằng nhau có thể bị thay đổi.

1-4. Sắp xếp chèn (Insertion Sort)

Mô tả thuật toán

Sắp xếp chèn là một thuật toán sắp xếp đơn giản, hiệu quả cho các tập dữ liệu nhỏ hoặc tập dữ liệu gần như đã được sắp xếp. Nó hoạt động tương tự như cách chúng ta sắp xếp các quân bài trong tay.

1. **Phân vùng**: Chia mảng thành hai vùng ảo: một vùng đã sắp xếp (ban đầu chỉ chứa phần tử đầu tiên) và một vùng chưa sắp xếp (phần còn lại của mảng).
2. **Chèn phần tử**: Lặp qua từng phần tử trong vùng chưa sắp xếp. Lấy phần tử hiện tại và chèn nó vào đúng vị trí trong vùng đã sắp xếp.
3. **Dịch chuyển**: Để tạo chỗ cho phần tử đang chèn, các phần tử trong vùng đã sắp xếp lớn hơn phần tử đang chèn sẽ được dịch chuyển sang phải.
4. **Lặp lại**: Tiếp tục quá trình này cho đến khi tất cả các phần tử từ vùng chưa sắp xếp đã được chèn vào vùng đã sắp xếp.

Triển khai thuật toán

import java.util.Arrays;

public class InsertionSortAlgorithm {

    public static void main(String[] args) {
        int[] sampleArray = {12, 11, 13, 5, 6};
        System.out.println("Mảng ban đầu: " + Arrays.toString(sampleArray));
        performInsertionSort(sampleArray);
        System.out.println("Mảng đã sắp xếp: " + Arrays.toString(sampleArray));
    }

    /**
     * Triển khai sắp xếp chèn.
     */
    private static void performInsertionSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int key = arr[i]; // Phần tử cần chèn
            int j = i - 1; // Chỉ số của phần tử cuối cùng trong vùng đã sắp xếp

            // Dịch chuyển các phần tử lớn hơn key sang phải để tạo chỗ
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = key; // Chèn key vào đúng vị trí
            System.out.println("Sau lượt " + i + ": " + Arrays.toString(arr));
        }
    }
}

So sánh với Sắp xếp chọn

1. **Độ phức tạp thời gian**: Cả hai đều có độ phức tạp thời gian trung bình là O(n²).
2. **Hiệu suất thực tế**: Trong hầu hết các trường hợp, sắp xếp chèn thường hoạt động tốt hơn sắp xếp chọn (và sắp xếp nổi bọt) vì nó thực hiện ít phép so sánh và hoán đổi hơn khi dữ liệu đã gần sắp xếp.
3. **Độ phức tạp thời gian tốt nhất**: Sắp xếp chèn có độ phức tạp thời gian O(n) khi mảng đã được sắp xếp (vì vòng lặp while sẽ không chạy nhiều). Sắp xếp chọn luôn có O(n²) ngay cả với mảng đã sắp xếp.
4. **Tính ổn định**:
   • **Sắp xếp chèn** là một thuật toán sắp xếp **ổn định**.
   • **Sắp xếp chọn** là một thuật toán sắp xếp **không ổn định**.

Lưu ý

Sắp xếp chèn rất quan trọng và thường được ưu tiên cho việc sắp xếp các tập dữ liệu nhỏ do hiệu quả của nó trong những trường hợp này.

1-5. Sắp xếp Shell (Shell Sort)

Mô tả thuật toán

Sắp xếp Shell, còn được gọi là sắp xếp chèn giảm dần, là một cải tiến của thuật toán sắp xếp chèn. Thay vì so sánh và hoán đổi các phần tử liền kề, Shell Sort cho phép hoán đổi các phần tử ở xa nhau, giúp các phần tử nhỏ/lớn di chuyển nhanh hơn đến vị trí gần đúng của chúng. Thuật toán hoạt động bằng cách sắp xếp các "nhóm" con của mảng bằng sắp xếp chèn, với các khoảng cách (gap) giảm dần, cho đến khi khoảng cách bằng 1 (trở thành sắp xếp chèn thông thường).

1. **Chọn dãy khoảng cách (gap sequence)**: Bắt đầu với một khoảng cách lớn (ví dụ: n/2, trong đó n là độ dài mảng).
2. **Sắp xếp chèn trên các nhóm**: Với mỗi khoảng cách gap, chia mảng thành nhiều nhóm con. Mỗi nhóm con bao gồm các phần tử cách nhau một khoảng gap. Thực hiện sắp xếp chèn trên từng nhóm con này. Điều này giúp các phần tử lớn/nhỏ di chuyển nhanh chóng đến vị trí gần đúng.
3. **Giảm khoảng cách**: Giảm khoảng cách gap (ví dụ: gap = gap / 2) và lặp lại bước 2.
4. **Hoàn tất**: Khi gap trở thành 1, thuật toán trở thành sắp xếp chèn thông thường trên toàn bộ mảng. Ở giai đoạn này, mảng đã gần như được sắp xếp, nên sắp xếp chèn sẽ rất hiệu quả.

Triển khai thuật toán

import java.util.Arrays;

public class ShellSortAlgorithm {

    public static void main(String[] args) {
        int[] dataset = {12, 34, 54, 2, 3, 10, 8, 20};
        System.out.println("Mảng ban đầu: " + Arrays.toString(dataset));
        performShellSort(dataset);
        System.out.println("Mảng đã sắp xếp: " + Arrays.toString(dataset));
    }

    /**
     * Triển khai sắp xếp Shell.
     */
    private static void performShellSort(int[] arr) {
        int n = arr.length;

        // Bắt đầu với khoảng cách lớn và giảm dần
        for (int gap = n / 2; gap > 0; gap /= 2) {
            // Thực hiện sắp xếp chèn cho các phần tử trong mỗi nhóm
            for (int i = gap; i < n; i++) {
                int temp = arr[i]; // Phần tử cần chèn
                int j;
                // Dịch chuyển các phần tử của nhóm con lớn hơn temp sang phải
                for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                    arr[j] = arr[j - gap];
                }
                arr[j] = temp; // Chèn temp vào đúng vị trí
                System.out.println("Sau khi xử lý gap " + gap + " và chỉ số " + i + ": " + Arrays.toString(arr));
            }
        }
    }
}

1-6. Sắp xếp nhanh (Quick Sort)

Mô tả thuật toán

Sắp xếp nhanh là một thuật toán sắp xếp dựa trên so sánh và thuộc loại "chia để trị" (divide-and-conquer). Nó hoạt động bằng cách chọn một phần tử làm "chốt" (pivot) và chia mảng thành hai mảng con: một mảng chứa các phần tử nhỏ hơn chốt và một mảng chứa các phần tử lớn hơn chốt. Quá trình này được lặp lại đệ quy trên các mảng con cho đến khi toàn bộ mảng được sắp xếp.

1. **Chọn chốt (Pivot)**: Chọn một phần tử từ mảng làm chốt. Việc chọn chốt ảnh hưởng lớn đến hiệu suất.
2. **Phân hoạch (Partition)**: Sắp xếp lại mảng sao cho tất cả các phần tử nhỏ hơn chốt nằm ở bên trái chốt, và tất cả các phần tử lớn hơn chốt nằm ở bên phải. Các phần tử bằng chốt có thể nằm ở bất kỳ bên nào. Sau bước này, chốt sẽ nằm ở vị trí cuối cùng của nó.
3. **Đệ quy**: Đệ quy áp dụng quá trình sắp xếp nhanh cho mảng con bên trái (các phần tử nhỏ hơn chốt) và mảng con bên phải (các phần tử lớn hơn chốt).
4. **Điều kiện dừng**: Quá trình đệ quy dừng lại khi một mảng con chỉ còn một phần tử hoặc không có phần tử nào (vì mảng một phần tử đã được sắp xếp).

Có nhiều cách để thực hiện bước phân hoạch, phổ biến nhất là phương pháp Lomuto và Hoare.

Sắp xếp nhanh với phân hoạch Lomuto (đơn biên)

Phương pháp này thường chọn phần tử cuối cùng làm chốt. Nó sử dụng một con trỏ i để theo dõi ranh giới của các phần tử nhỏ hơn chốt.

1. Chọn phần tử cuối cùng của mảng con làm chốt.
2. Duy trì một chỉ số i, bắt đầu từ low - 1, đại diện cho ranh giới giữa các phần tử nhỏ hơn chốt và các phần tử lớn hơn/bằng chốt.
3. Lặp qua mảng con bằng con trỏ j từ low đến high - 1. Nếu arr[j] nhỏ hơn chốt, tăng i và hoán đổi arr[i] với arr[j].
4. Sau khi vòng lặp kết thúc, hoán đổi chốt (arr[high]) với arr[i + 1]. Vị trí i + 1 là vị trí cuối cùng của chốt.

Triển khai thuật toán (phân hoạch Lomuto)

import java.util.Arrays;

public class QuickSortLomuto {

    public static void main(String[] args) {
        int[] data = {5, 3, 7, 2, 9, 8, 1, 4};
        System.out.println("Mảng ban đầu: " + Arrays.toString(data));
        quickSort(data, 0, data.length - 1);
        System.out.println("Mảng đã sắp xếp: " + Arrays.toString(data));
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            // pi là chỉ số phân hoạch, arr[pi] hiện tại ở đúng vị trí
            int pi = lomutoPartition(arr, low, high);

            // Sắp xếp riêng biệt các phần tử trước và sau phân hoạch
            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
    }

    private static int lomutoPartition(int[] arr, int low, int high) {
        int pivot = arr[high]; // Chọn phần tử cuối cùng làm chốt
        int i = (low - 1); // Chỉ số của phần tử nhỏ hơn

        for (int j = low; j < high; j++) {
            // Nếu phần tử hiện tại nhỏ hơn hoặc bằng chốt
            if (arr[j] <= pivot) {
                i++; // Tăng chỉ số của phần tử nhỏ hơn
                if (i != j) { // Tránh hoán đổi với chính nó
                    swap(arr, i, j);
                }
            }
        }

        // Hoán đổi arr[i+1] và arr[high] (chốt)
        // để đưa chốt vào đúng vị trí của nó
        if (i + 1 != high) { // Tránh hoán đổi với chính nó
            swap(arr, i + 1, high);
        }
        System.out.println("Phân hoạch Lomuto: " + Arrays.toString(arr));
        return i + 1;
    }
}

Sắp xếp nhanh với phân hoạch Hoare (song biên)

Phương pháp này thường chọn phần tử đầu tiên làm chốt và sử dụng hai con trỏ di chuyển từ hai phía của mảng.

1. Chọn phần tử đầu tiên của mảng con làm chốt.
2. Sử dụng hai con trỏ, i (bắt đầu từ low) và j (bắt đầu từ high).
3. Con trỏ j di chuyển từ phải sang trái để tìm phần tử nhỏ hơn chốt.
4. Con trỏ i di chuyển từ trái sang phải để tìm phần tử lớn hơn chốt.
5. Nếu i < j, hoán đổi arr[i] và arr[j].
6. Quá trình dừng khi i >= j. Sau đó, hoán đổi chốt (arr[low]) với arr[j] (hoặc arr[i] tùy trường hợp cụ thể).

Triển khai thuật toán (phân hoạch Hoare)

import java.util.Arrays;

public class QuickSortHoare {

    public static void main(String[] args) {
        int[] data = {5, 3, 7, 2, 9, 8, 1, 4};
        System.out.println("Mảng ban đầu: " + Arrays.toString(data));
        quickSort(data, 0, data.length - 1);
        System.out.println("Mảng đã sắp xếp: " + Arrays.toString(data));
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pi = hoarePartition(arr, low, high);

            // Sắp xếp đệ quy các mảng con
            // Lưu ý: pi có thể không phải là vị trí cuối cùng của chốt trong Hoare,
            // nên ta không dùng pi-1 và pi+1 trực tiếp như Lomuto
            quickSort(arr, low, pi);
            quickSort(arr, pi + 1, high);
        }
    }

    private static int hoarePartition(int[] arr, int low, int high) {
        int pivot = arr[low]; // Chọn phần tử đầu tiên làm chốt
        int i = low - 1;
        int j = high + 1;

        while (true) {
            // Tìm phần tử bên trái lớn hơn hoặc bằng chốt
            do {
                i++;
            } while (arr[i] < pivot);

            // Tìm phần tử bên phải nhỏ hơn hoặc bằng chốt
            do {
                j--;
            } while (arr[j] > pivot);

            // Nếu các con trỏ giao nhau hoặc vượt qua nhau, dừng
            if (i >= j) {
                System.out.println("Phân hoạch Hoare: " + Arrays.toString(arr));
                return j; // Trả về chỉ số phân hoạch
            }

            // Hoán đổi các phần tử sai vị trí
            swap(arr, i, j);
        }
    }
}

Đặc điểm của Sắp xếp nhanh

1. **Độ phức tạp thời gian**:
   • **Trung bình**: O(n log n). Đây là một trong những thuật toán sắp xếp nhanh nhất trên thực tế.
   • **Tệ nhất**: O(n²), xảy ra khi việc chọn chốt luôn dẫn đến các phân hoạch mất cân bằng (ví dụ: mảng đã sắp xếp hoặc sắp xếp ngược và chọn chốt là phần tử nhỏ nhất/lớn nhất).
2. **Hiệu quả**: Rất hiệu quả với các tập dữ liệu lớn.
3. **Tính ổn định**: Sắp xếp nhanh là một thuật toán sắp xếp **không ổn định**.

1-7. Tập hợp ArrayList

Quy tắc mở rộng dung lượng

ArrayList trong Java là một triển khai của List sử dụng mảng động. Khi số lượng phần tử vượt quá dung lượng hiện tại của mảng, ArrayList sẽ tự động tăng kích thước mảng. Các quy tắc mở rộng dung lượng bao gồm:

1. **Khởi tạo mặc định**: Khi tạo một ArrayList không có tham số (new ArrayList()), nó sẽ sử dụng một mảng nội bộ có kích thước ban đầu là 0. Khi phần tử đầu tiên được thêm vào, mảng sẽ được mở rộng thành dung lượng 10.
2. **Khởi tạo với dung lượng cụ thể**: new ArrayList(int initialCapacity) tạo một mảng với dung lượng được chỉ định.
3. **Khởi tạo từ Collection**: new ArrayList(Collection<? extends E> c) tạo một mảng với dung lượng đủ để chứa tất cả các phần tử của c.
4. **Phương thức add(E e)**:
   • Lần mở rộng đầu tiên: Nếu mảng ban đầu rỗng (từ constructor mặc định), dung lượng sẽ được mở rộng thành 10.
   • Các lần mở rộng tiếp theo: Dung lượng mới thường được tính bằng 1.5 lần dung lượng cũ (oldCapacity + oldCapacity / 2).
5. **Phương thức addAll(Collection<? extends E> c)**:
   • Nếu ArrayList hiện tại không có phần tử: Dung lượng mới là giá trị lớn nhất giữa 10 và số lượng phần tử cần thêm từ c.
   • Nếu ArrayList hiện tại đã có phần tử: Dung lượng mới là giá trị lớn nhất giữa 1.5 lần dung lượng hiện tại và số lượng phần tử cần thêm.

1-8. Tập hợp LinkedList

So sánh LinkedList và ArrayList

LinkedList và ArrayList là hai triển khai chính của giao diện List trong Java, nhưng chúng có cấu trúc dữ liệu cơ bản và đặc điểm hiệu suất khác nhau:

LinkedList

• **Cấu trúc dữ liệu**: Dựa trên danh sách liên kết đôi (doubly linked list). Mỗi phần tử (Node) lưu trữ dữ liệu, một con trỏ tới phần tử kế tiếp và một con trỏ tới phần tử trước đó.
• **Bộ nhớ liên tục**: Không yêu cầu bộ nhớ liên tục. Các phần tử có thể phân tán trong bộ nhớ.
• **Truy cập ngẫu nhiên (theo chỉ số)**: Chậm. Để truy cập một phần tử tại chỉ số k, cần duyệt qua danh sách từ đầu hoặc cuối cho đến khi đến vị trí đó (O(n)).
• **Chèn/Xóa**:
  • **Đầu/cuối danh sách**: Rất nhanh (O(1)) vì chỉ cần cập nhật vài con trỏ.
  • **Giữa danh sách**: Nhanh (O(1)) sau khi đã tìm được vị trí chèn/xóa, nhưng việc tìm vị trí đó mất O(n).
• **Tiêu thụ bộ nhớ**: Tiêu thụ nhiều bộ nhớ hơn ArrayList vì mỗi Node phải lưu trữ thêm hai con trỏ.

ArrayList

• **Cấu trúc dữ liệu**: Dựa trên mảng động (resizable array).
• **Bộ nhớ liên tục**: Yêu cầu các ô nhớ liên tục cho các phần tử của nó.
• **Truy cập ngẫu nhiên (theo chỉ số)**: Rất nhanh (O(1)) vì có thể truy cập trực tiếp bằng chỉ số mảng.
• **Chèn/Xóa**:
  • **Cuối danh sách**: Nhanh (O(1)) nếu còn dung lượng, hoặc O(n) nếu cần mở rộng mảng.
  • **Đầu/giữa danh sách**: Chậm (O(n)) vì tất cả các phần tử sau vị trí chèn/xóa phải được dịch chuyển.
• **Tiêu thụ bộ nhớ**: Tiêu thụ ít bộ nhớ hơn LinkedList (chỉ lưu trữ dữ liệu và có thể một số dung lượng dư thừa).
• **Tận dụng CPU Cache**: Do các phần tử được lưu trữ liên tục trong bộ nhớ, ArrayList có thể tận dụng tốt bộ nhớ cache của CPU (nguyên lý cục bộ hóa dữ liệu), dẫn đến hiệu suất tốt hơn trong một số trường hợp duyệt.

1-9. Iterator

Fail-Fast và Fail-Safe

Khi làm việc với các tập hợp trong môi trường đa luồng hoặc khi thực hiện duyệt và sửa đổi đồng thời, hành vi của Iterator trở nên quan trọng. Java định nghĩa hai loại chính:

Fail-Fast Iterators

• **Đặc điểm**: Các Iterator này được thiết kế để phát hiện sớm và thất bại nhanh chóng (throw ConcurrentModificationException) nếu một tập hợp bị sửa đổi cấu trúc trong khi đang được duyệt bởi Iterator đó.
• **Mục đích**: Ngăn chặn hành vi không nhất quán hoặc khó lường khi tập hợp bị thay đổi trong quá trình duyệt.
• **Ví dụ**: Hầu hết các lớp tập hợp trong java.util như ArrayList, HashMap, Vector sử dụng Iterator fail-fast.
  • **Cơ chế**: Chúng thường sử dụng một biến đếm thay đổi (modCount) trong lớp tập hợp. Khi một Iterator được tạo, nó lưu trữ giá trị modCount hiện tại (gọi là expectedModCount). Trong mỗi thao tác của Iterator (next(), hasNext()), nó kiểm tra xem modCount có bằng expectedModCount hay không. Nếu không, một ConcurrentModificationException sẽ được ném ra.
  • **Hạn chế**: Không đảm bảo rằng lỗi sẽ luôn xảy ra trong mọi trường hợp sửa đổi đồng thời, nhưng là một nỗ lực tốt nhất.

Fail-Safe Iterators

• **Đặc điểm**: Các Iterator này không ném ra ngoại lệ nếu tập hợp bị sửa đổi cấu trúc trong khi đang được duyệt. Chúng có thể chịu đựng các sửa đổi đồng thời.
• **Mục đích**: Cho phép duyệt tập hợp một cách an toàn ngay cả khi các luồng khác đang sửa đổi nó, thường là với chi phí về tính nhất quán dữ liệu.
• **Ví dụ**: Các lớp tập hợp trong java.util.concurrent như CopyOnWriteArrayList, ConcurrentHashMap sử dụng Iterator fail-safe.
  • **Cơ chế**: Chúng thường hoạt động bằng cách tạo một bản sao (snapshot) của tập hợp tại thời điểm Iterator được tạo. Iterator duyệt trên bản sao này. Do đó, bất kỳ sửa đổi nào đối với tập hợp gốc sau khi Iterator được tạo sẽ không ảnh hưởng đến bản sao mà Iterator đang duyệt.
  • **Hạn chế**: Iterator không phản ánh các thay đổi mới nhất của tập hợp gốc, dẫn đến "tính nhất quán yếu" (weakly consistent). Nó có thể duyệt qua một bản cũ của dữ liệu.

1-10. HashMap

Cấu trúc dữ liệu cơ bản

• **Java 7**: HashMap sử dụng một mảng các Entry. Mỗi Entry chứa khóa, giá trị, giá trị băm của khóa và một con trỏ tới Entry kế tiếp (tạo thành danh sách liên kết). Khi có xung đột băm, các phần tử được lưu trữ trong danh sách liên kết tại cùng một chỉ mục mảng.
• **Java 8**: Cải tiến cấu trúc dữ liệu. HashMap vẫn sử dụng mảng và danh sách liên kết. Tuy nhiên, nếu một danh sách liên kết tại một chỉ mục (bucket) trở nên quá dài, nó sẽ được chuyển đổi thành Cây Đỏ Đen (Red-Black Tree) để cải thiện hiệu suất tìm kiếm (O(log n) thay vì O(n) trong trường hợp tệ nhất của danh sách liên kết dài).

Chuyển đổi thành Cây Đỏ Đen (Treeification)

• **Khi nào xảy ra?**: Khi độ dài của danh sách liên kết tại một bucket vượt quá ngưỡng cụ thể (TREEIFY_THRESHOLD, mặc định là 8) và dung lượng của bảng băm (số lượng bucket trong mảng) đã đạt hoặc vượt quá MIN_TREEIFY_CAPACITY (mặc định là 64).
• **Ý nghĩa**:
  • **Tránh tấn công DoS**: Ngăn chặn suy giảm hiệu suất (từ O(1) thành O(n)) nếu kẻ tấn công cố tình tạo ra nhiều khóa có cùng giá trị băm.
  • **Hiệu suất**: Cải thiện độ phức tạp thời gian tìm kiếm, thêm, xóa từ O(n) (danh sách liên kết tệ nhất) thành O(log n) (cây đỏ đen).
  • **Ưu tiên danh sách liên kết**: Mặc dù cây đỏ đen tốt hơn cho các danh sách dài, nó tốn nhiều bộ nhớ hơn (TreeNode lớn hơn Node) và có chi phí vận hành cao hơn cho các danh sách ngắn. Do đó, HashMap ưu tiên giữ danh sách liên kết trừ khi thực sự cần thiết.
  • **Xác suất thống kê**: Với hệ số tải 0.75, xác suất để một danh sách liên kết đạt đến độ dài 8 là cực kỳ thấp (khoảng 0.00000006 theo phân phối Poisson nếu hàm băm tốt). Ngưỡng 8 được chọn để đảm bảo việc chuyển đổi sang cây là một trường hợp đặc biệt, không phải là quy tắc.

Chuyển đổi lại thành danh sách liên kết (Untreeification)

• **Khi nào xảy ra?**:
  • **Trong quá trình mở rộng dung lượng**: Khi một cây đỏ đen được chia thành hai trong quá trình mở rộng (resizing) và số lượng phần tử trong một trong hai phần tử mới của cây con đó giảm xuống dưới ngưỡng (UNTREEIFY_THRESHOLD, mặc định là 6).
  • **Khi xóa nút**: Khi một nút bị xóa khỏi cây và cấu trúc cây trở nên quá nhỏ, có thể được chuyển đổi lại thành danh sách liên kết để tiết kiệm bộ nhớ.

Phương pháp tính chỉ mục

1. **Tính hashCode()**: Gọi phương thức hashCode() của đối tượng khóa.
2. **Băm thứ cấp (Secondary Hashing)**: Giá trị băm thô sau đó được xử lý bởi phương thức hash() của HashMap. Phương pháp này dịch chuyển các bit cao của giá trị băm xuống để kết hợp với các bit thấp thông qua phép XOR (h ^ (h >>> 16)).
   • **Mục đích**: Giúp phân tán các giá trị băm đều hơn, đặc biệt khi dung lượng bảng băm nhỏ (và chỉ các bit thấp của giá trị băm được sử dụng trong phép toán & (capacity - 1)).
3. **Tính chỉ mục cuối cùng**: Lấy giá trị băm đã được xử lý (từ bước 2) và thực hiện phép toán bitwise AND với (capacity - 1) (hash & (capacity - 1)). Đây là chỉ mục (bucket index) trong mảng.

Tại sao dung lượng mảng là lũy thừa của 2?

1. **Hiệu quả tính chỉ mục**: Khi dung lượng là lũy thừa của 2, phép toán modulo (%) để tính chỉ mục có thể được thay thế bằng phép toán bitwise AND (&), cụ thể là hash & (capacity - 1). Phép toán AND nhanh hơn đáng kể so với phép chia/modulo.
2. **Hiệu quả khi mở rộng dung lượng (resizing)**: Khi HashMap mở rộng dung lượng (tức là nhân đôi kích thước), việc tính toán lại chỉ mục cho các phần tử cũ trở nên rất hiệu quả. Các phần tử sẽ hoặc ở cùng chỉ mục cũ hoặc chuyển đến chỉ mục oldIndex + oldCapacity. Điều này được xác định bằng cách kiểm tra bit thứ oldCapacity của giá trị băm.

Lưu ý rằng băm thứ cấp là cần thiết để bù đắp cho việc chỉ sử dụng các bit thấp của giá trị băm khi dung lượng là lũy thừa của 2, đảm bảo phân tán đều hơn. Các lớp như Hashtable không giới hạn dung lượng là lũy thừa của 2 và do đó không cần băm thứ cấp phức tạp như HashMap.

Quy trình put()

1. **Tạo mảng lười biếng**: Nếu mảng chứa các bucket chưa được khởi tạo, nó sẽ được tạo lần đầu tiên khi phương thức put() được gọi.
2. **Tính toán chỉ mục**: Tính chỉ mục bucket cho khóa bằng cách sử dụng hashCode() của khóa, sau đó áp dụng hàm hash() của HashMap và cuối cùng là & (capacity - 1).
3. **Kiểm tra bucket trống**: Nếu bucket tại chỉ mục đã tính đang trống, một Node mới sẽ được tạo và đặt vào đó, sau đó phương thức trả về.
4. **Xử lý xung đột**: Nếu bucket đã có phần tử:
   1. **Nếu là cây Đỏ Đen**: Thực hiện logic thêm/cập nhật của cây Đỏ Đen.
   2. **Nếu là danh sách liên kết**: Duyệt qua danh sách liên kết để tìm khóa trùng lặp.
      • Nếu tìm thấy khóa trùng lặp, cập nhật giá trị.
      • Nếu không tìm thấy, thêm Node mới vào cuối danh sách liên kết.
      • Sau khi thêm, kiểm tra xem độ dài danh sách liên kết có vượt quá ngưỡng TREEIFY_THRESHOLD (8) hay không. Nếu có, cố gắng chuyển đổi danh sách thành cây Đỏ Đen (nếu dung lượng đủ lớn, ≥ 64).
5. **Kiểm tra mở rộng dung lượng**: Sau khi thêm hoặc cập nhật phần tử, HashMap kiểm tra xem số lượng phần tử hiện tại có vượt quá ngưỡng tải (size > threshold) hay không. Nếu có, nó sẽ gọi phương thức resize() để mở rộng dung lượng mảng.

Điểm khác biệt giữa Java 7 và Java 8

• **Chèn Node vào danh sách liên kết**: Java 7 sử dụng chèn đầu danh sách (prepending), trong khi Java 8 sử dụng chèn cuối danh sách (appending).
• **Điều kiện mở rộng dung lượng**: Java 7 mở rộng khi số lượng phần tử lớn hơn hoặc bằng ngưỡng và không có chỗ trống. Java 8 mở rộng ngay khi số lượng phần tử lớn hơn ngưỡng.
• **Tối ưu hóa mở rộng dung lượng**: Java 8 tối ưu hóa việc phân bố lại các Node trong quá trình mở rộng, thay vì tính lại băm cho từng Node, nó sử dụng bit bổ sung của giá trị băm để xác định vị trí mới (index hoặc index + oldCapacity).

Hệ số tải (Load Factor) mặc định là 0.75f

Giá trị 0.75f được chọn làm mặc định để cân bằng giữa việc sử dụng không gian và hiệu suất tìm kiếm/chèn/xóa:

• **Lớn hơn 0.75**: Tiết kiệm không gian bộ nhớ hơn vì HashMap ít mở rộng dung lượng hơn. Tuy nhiên, nó sẽ dẫn đến các danh sách liên kết dài hơn (hoặc cây sâu hơn), làm tăng thời gian cho các hoạt động O(n) hoặc O(log n).
• **Nhỏ hơn 0.75**: Giảm xung đột và giữ các danh sách liên kết ngắn hơn, cải thiện hiệu suất. Nhưng nó sẽ khiến HashMap mở rộng dung lượng thường xuyên hơn, tiêu tốn nhiều không gian hơn và chi phí cho các hoạt động mở rộng.

Các vấn đề phỏng vấn thường gặp về HashMap

1. **Vấn đề đa luồng**:
   • **JDK 1.7**: Có thể dẫn đến vòng lặp vô hạn (infinite loop) trong quá trình mở rộng dung lượng (resize) do lỗi trong việc xử lý danh sách liên kết.
   • **JDK 1.8**: Mặc dù vòng lặp vô hạn đã được khắc phục, nhưng vẫn có thể xảy ra mất dữ liệu hoặc dữ liệu không nhất quán khi nhiều luồng cùng sửa đổi HashMap mà không có đồng bộ hóa.
   Để xử lý đa luồng, nên sử dụng ConcurrentHashMap.
2. **Khóa null và yêu cầu đối với đối tượng khóa**:
   • **Khóa null**: HashMap cho phép một khóa là null. Nó sẽ được lưu trữ tại chỉ mục 0 của mảng. Các triển khai Map khác như Hashtable thì không cho phép.
   • **Yêu cầu đối với đối tượng khóa**:
     • Đối tượng dùng làm khóa phải ghi đè (override) các phương thức hashCode() và equals() một cách chính xác.
     • Đối tượng khóa phải là bất biến (immutable) hoặc giá trị của các trường được sử dụng trong hashCode() và equals() không được thay đổi sau khi đối tượng được dùng làm khóa. Nếu một khóa thay đổi giá trị băm của nó sau khi được đưa vào HashMap, việc tìm kiếm hoặc xóa nó có thể thất bại.
3. **Cách triển khai hashCode() của String và tại sao lại là 31?**
   • **Mục tiêu**: Đảm bảo phân tán giá trị băm đủ đều, tạo ra các mã băm tương đối độc đáo cho các chuỗi khác nhau.
   • **Công thức**: Cho một chuỗi S có độ dài n, công thức là: S[0]*31^(n-1) + S[1]*31^(n-2) + ... + S[i]*31^(n-1-i) + ... + S[n-1]*31^0
   • **Tại sao 31?**:
     • 31 là một số nguyên tố. Việc sử dụng số nguyên tố trong phép nhân băm thường tạo ra sự phân tán tốt hơn.
     • 31 là một số nguyên tố có thể được tối ưu hóa trong máy tính. Phép nhân h * 31 có thể được thay thế bằng phép dịch bit và trừ: (h << 5) - h, nhanh hơn phép nhân thông thường đối với một số kiến trúc CPU.

1-11. Mẫu thiết kế Singleton

Mô tả

Mẫu Singleton đảm bảo rằng một lớp chỉ có một thể hiện duy nhất và cung cấp một điểm truy cập toàn cục cho thể hiện đó. Nó hữu ích cho các tài nguyên duy nhất như quản lý cấu hình, kết nối cơ sở dữ liệu hoặc bộ đệm.

Năm cách triển khai phổ biến

1. Eager Initialization (Khởi tạo sớm)

Thể hiện của lớp được tạo ngay lập tức khi lớp được tải vào bộ nhớ, bất kể nó có được sử dụng hay không. Nó đơn giản và an toàn trong môi trường đa luồng.

import java.io.Serializable;

public class EagerSingleton implements Serializable {
    // Thể hiện được tạo khi lớp được tải
    private static final EagerSingleton uniqueInstance = new EagerSingleton();

    private EagerSingleton() {
        // Ngăn chặn tạo thể hiện thứ hai thông qua Reflection
        if (uniqueInstance != null) {
            throw new IllegalStateException("Không thể tạo nhiều hơn một thể hiện Singleton.");
        }
        System.out.println("EagerSingleton: Khởi tạo thể hiện.");
    }

    public static EagerSingleton getInstance() {
        return uniqueInstance;
    }

    public void showMessage() {
        System.out.println("EagerSingleton: Chào từ thể hiện duy nhất!");
    }

    // Ngăn chặn việc tạo thể hiện mới khi deserialization
    protected Object readResolve() {
        return uniqueInstance;
    }
}

• **Ưu điểm**: Đơn giản, an toàn luồng một cách tự nhiên.
• **Nhược điểm**: Tài nguyên có thể bị lãng phí nếu thể hiện không bao giờ được sử dụng.

2. Enum Singleton (Singleton bằng Enum)

Đây là cách triển khai Singleton được khuyến nghị nhất trong Java vì nó cung cấp tính an toàn luồng, chống lại deserialization và reflection một cách tự nhiên.

public enum EnumSingleton {
    UNIQUE_INSTANCE; // Thể hiện duy nhất

    private EnumSingleton() {
        System.out.println("EnumSingleton: Khởi tạo thể hiện.");
    }

    public void showMessage() {
        System.out.println("EnumSingleton: Chào từ thể hiện duy nhất!");
    }
}

• **Ưu điểm**: An toàn luồng, chống Reflection và Deserialization.
• **Nhược điểm**: Không thể lười biếng khởi tạo (eager initialization).

3. Lazy Initialization (Khởi tạo lười biếng) với đồng bộ hóa phương thức

Thể hiện chỉ được tạo khi nó được yêu cầu lần đầu tiên. Phương thức getInstance() được đồng bộ hóa để đảm bảo an toàn luồng.

import java.io.Serializable;

public class LazySynchronizedSingleton implements Serializable {
    private static LazySynchronizedSingleton uniqueInstance;

    private LazySynchronizedSingleton() {
        System.out.println("LazySynchronizedSingleton: Khởi tạo thể hiện.");
    }

    public static synchronized LazySynchronizedSingleton getInstance() {
        if (uniqueInstance == null) {
            uniqueInstance = new LazySynchronizedSingleton();
        }
        return uniqueInstance;
    }

    public void showMessage() {
        System.out.println("LazySynchronizedSingleton: Chào từ thể hiện duy nhất!");
    }
}

• **Ưu điểm**: Lười biếng khởi tạo.
• **Nhược điểm**: Hiệu suất thấp do đồng bộ hóa trên toàn bộ phương thức, ngay cả sau khi thể hiện đã được tạo.

4. Double-Checked Locking (DCL) Singleton

Một tối ưu hóa cho khởi tạo lười biếng, chỉ đồng bộ hóa phần mã quan trọng, nhưng đòi hỏi từ khóa volatile cho biến thể hiện để đảm bảo hoạt động đúng.

import java.io.Serializable;

public class DCLSingleton implements Serializable {
    // volatile đảm bảo visibility và ngăn chặn sắp xếp lại thứ tự lệnh
    private static volatile DCLSingleton uniqueInstance;

    private DCLSingleton() {
        System.out.println("DCLSingleton: Khởi tạo thể hiện.");
    }

    public static DCLSingleton getInstance() {
        if (uniqueInstance == null) { // Kiểm tra lần 1
            synchronized (DCLSingleton.class) {
                if (uniqueInstance == null) { // Kiểm tra lần 2
                    uniqueInstance = new DCLSingleton();
                }
            }
        }
        return uniqueInstance;
    }

    public void showMessage() {
        System.out.println("DCLSingleton: Chào từ thể hiện duy nhất!");
    }
}

Tại sao cần volatile?

• Lệnh uniqueInstance = new DCLSingleton(); không phải là một thao tác nguyên tử. Nó bao gồm 3 bước:
  1. Phân bổ bộ nhớ cho đối tượng DCLSingleton.
  2. Gọi constructor để khởi tạo đối tượng.
  3. Gán tham chiếu của đối tượng vừa tạo cho biến uniqueInstance.
• Các bước 2 và 3 có thể bị sắp xếp lại thứ tự lệnh (instruction reordering) bởi JVM hoặc CPU. Tức là, bước 3 (gán tham chiếu) có thể xảy ra trước bước 2 (khởi tạo đối tượng).
• Nếu điều này xảy ra, một luồng khác có thể thấy uniqueInstance không còn null (kiểm tra lần 1), nhưng thực tế đối tượng mà nó tham chiếu chưa được khởi tạo đầy đủ. Điều này dẫn đến việc luồng đó sử dụng một đối tượng chưa hoàn chỉnh, gây ra lỗi.
• Từ khóa volatile ngăn chặn việc sắp xếp lại thứ tự lệnh và đảm bảo rằng mọi ghi vào uniqueInstance (bước 3) sẽ hoàn tất trước khi bất kỳ đọc nào (kiểm tra lần 1) diễn ra. Nó cũng đảm bảo tính hiển thị (visibility) của các thay đổi giữa các luồng.

5. Static Inner Class Singleton (Lớp lồng tĩnh)

Cách này tận dụng cơ chế tải lớp của JVM để đạt được khởi tạo lười biếng và an toàn luồng mà không cần đồng bộ hóa.

import java.io.Serializable;

public class StaticInnerClassSingleton implements Serializable {

    private StaticInnerClassSingleton() {
        System.out.println("StaticInnerClassSingleton: Khởi tạo thể hiện.");
    }

    // Lớp Holder tĩnh này chỉ được tải khi phương thức getInstance() được gọi lần đầu tiên.
    private static class SingletonHolder {
        private static final StaticInnerClassSingleton uniqueInstance = new StaticInnerClassSingleton();
    }

    public static StaticInnerClassSingleton getInstance() {
        return SingletonHolder.uniqueInstance;
    }

    public void showMessage() {
        System.out.println("StaticInnerClassSingleton: Chào từ thể hiện duy nhất!");
    }
}

• **Ưu điểm**: Lười biếng khởi tạo, an toàn luồng, không cần đồng bộ hóa rõ ràng. Đây thường được coi là cách tốt nhất cho hầu hết các trường hợp.
• **Nhược điểm**: Cần một lớp lồng.

Singleton trong JDK

Mẫu Singleton được sử dụng trong nhiều lớp chuẩn của Java:

• **java.lang.Runtime**: Triển khai theo kiểu Eager Initialization (khởi tạo sớm). Bạn truy cập nó qua Runtime.getRuntime().
• **java.io.Console**: Thường được triển khai với DCL để đảm bảo chỉ có một giao diện bảng điều khiển.
• **Một số lớp tiện ích trong java.util.Collections**: Chẳng hạn như EmptyNavigableSet.INSTANCE hoặc Comparators.NaturalOrderComparator.INSTANCE, thường sử dụng Enum hoặc Static Inner Class cho các thể hiện rỗng/mặc định.