Đến nội dung chính
notes.vinhnq.com

Tìm kiếm

Java CoreJunior21 phút đọc

Java cơ bản: mảng và chuỗi

Ôn 11 thẻ
Trong bài này

Cụm bài Java cơ bản: 1. JVM và JDK · 2. Hello World và ba loại lỗi · 3. Biến và kiểu dữ liệu · 4. Toán tử và rẽ nhánh · 5. Vòng lặp và hàm · 6. Mảng và chuỗi · 7. Console và file text · 8. Byte stream và serialization

Đọc 100 điểm số rồi tính trung bình thì không thể khai báo 100 biến; cần mảng để chứa nhiều giá trị cùng kiểu. Còn chuỗi là dữ liệu backend dùng nhiều nhất (tên, email, JSON, câu SQL), và có vài bẫy so sánh, nối chuỗi phải biết. Nên đọc trước vòng lặp và hàm (nhất là phần pass-by-value); bài tiếp theo là nhập xuất console và đọc ghi file text.

1. Mảng

Ý chính: mảng là một khối ô nhớ liền nhau, cố định kích thước, mỗi ô cùng kiểu và được đánh chỉ số từ 0. Nhờ nằm liền nhau nên truy cập theo chỉ số là O(1).

Mảng một chiều

double[] scores;                 // khai báo (cách nên dùng)
double scores2[];                // cũng hợp lệ (kiểu C), nhưng không nên dùng
scores = new double[5];          // cấp phát 5 phần tử, tất cả bằng 0.0

int[] ids = new int[3];          // khai báo + cấp phát
ids[0] = 7;                      // gán theo chỉ số, 0 <= index < length
int[] primes = {2, 3, 5, 7};     // khai báo + gán giá trị luôn

for (int i = 0; i < ids.length; i++) ids[i] = i * 10;   // gán bằng vòng lặp
for (int id : ids) System.out.println(id);              // đọc
  • Giá trị mặc định khi cấp phát: 0 cho kiểu số, false cho boolean, '\u0000' cho char, null cho kiểu tham chiếu.
  • length là field, không phải method (khác String.length() và List.size()).
  • Truy cập ngoài [0, length) ném ArrayIndexOutOfBoundsException. JVM luôn kiểm tra biên, nên Java không có lỗi tràn bộ đệm kiểu C.
  • Kích thước cố định sau khi tạo. Cần co giãn thì dùng ArrayList: bên trong cũng là mảng, khi đầy thì tạo mảng mới lớn hơn khoảng 1,5 lần rồi copy sang.
  • Slide có ví dụ “gán giá trị từ 0 … 5 cho mảng 5 phần tử”. Thực ra mảng 5 phần tử chỉ có chỉ số 0 … 4.

Mảng và hàm

static int[] range(int n) {            // trả về một mảng
    int[] result = new int[n];
    for (int i = 0; i < n; i++) result[i] = i;
    return result;
}

static void print(int[] array) {       // nhận một mảng
    for (int i = 0; i < array.length; i++) {
        System.out.printf("a[%d] = %d%n", i, array[i]);
    }
}

Hàm nhận mảng và sửa phần tử thì caller sẽ thấy thay đổi (lý do ở phần pass-by-value). Hai bản slide diễn đạt khác nhau (“bị thay đổi” và “được giữ nguyên”) nhưng cùng một ý: thay đổi trong hàm vẫn còn sau khi hàm kết thúc.

Các tiện ích hay dùng của Arrays:

int[] copy = Arrays.copyOf(src, src.length);   // sao chép nông
Arrays.sort(copy);                             // primitive: dual-pivot quicksort; object: TimSort (ổn định)
int pos = Arrays.binarySearch(copy, 42);       // mảng phải đã sắp xếp
System.out.println(Arrays.toString(copy));     // in mảng; in thẳng sẽ ra dạng "[I@1b6d3586"
Arrays.equals(a, b);                           // so sánh nội dung; a == b chỉ so sánh địa chỉ

Mảng hai chiều và mảng răng cưa

Mảng 2D dùng cho dữ liệu dạng bảng: ma trận, bàn cờ, bảng khoảng cách giữa các thành phố. Trong Java nó là mảng của các mảng: mỗi hàng là một object mảng riêng.

int[][] matrix = new int[2][3];          // 2 hàng, 3 cột
matrix[1][2] = 9;
int[][] grid = {{1, 2}, {3, 4}, {5, 6}};

for (int r = 0; r < grid.length; r++) {
    for (int c = 0; c < grid[r].length; c++) {   // dùng grid[r].length, đừng giả định mọi hàng dài bằng nhau
        System.out.print(grid[r][c] + " ");
    }
    System.out.println();
}

Vì mỗi hàng là một mảng riêng nên các hàng có thể dài khác nhau. Đó là mảng răng cưa (jagged array):

int[][] triangle = new int[4][];        // mới có 4 hàng, chưa có cột
for (int r = 0; r < triangle.length; r++) {
    triangle[r] = new int[r + 1];       // hàng r có r+1 phần tử
}
flowchart LR
  T[triangle] --> R0[hàng 0: 1 ô]
  T --> R1[hàng 1: 2 ô]
  T --> R2[hàng 2: 3 ô]
  T --> R3[hàng 3: 4 ô]
  • Duyệt theo hàng ([r][c], c chạy ở vòng trong) nhanh hơn duyệt theo cột, vì phần tử trong một hàng nằm liền nhau.
  • In nhanh mảng 2D: Arrays.deepToString(grid).

Mảng nhiều chiều

Mảng n chiều có n cặp [], ví dụ int[][][] cube = new int[2][3][4];. Slide viết new [size1]...[sizeN] là thiếu tên kiểu; đúng ra là new int[size1]...[sizeN].

2. Chuỗi (String)

Ý chính: String là class bất biến: mọi method “sửa” chuỗi đều trả về chuỗi mới. Từ đó suy ra hai quy tắc: so sánh bằng equals, nối nhiều lần bằng StringBuilder.

String không phải kiểu nguyên thuỷ. Bên trong là một mảng byte cộng một cờ bảng mã (Latin-1 hoặc UTF-16, tối ưu “compact strings” từ Java 9). Vì vậy nhiều thao tác giống mảng: có độ dài, chỉ số từ 0, truy cập ngoài khoảng ném StringIndexOutOfBoundsException.

Các method hay dùng

String s = " Java Basic ";
s.length();                 // 12: tính cả hai dấu cách ở hai đầu
s.trim();                   // "Java Basic": bỏ khoảng trắng đầu và cuối
s.strip();                  // "Java Basic" (Java 11): hiểu cả khoảng trắng Unicode, nên dùng thay trim
s.isBlank();                // false (Java 11): true nếu rỗng hoặc chỉ có khoảng trắng
s.charAt(1);                // 'J'
s.indexOf("a");             // 2; không tìm thấy thì -1
s.lastIndexOf('a');         // 7
s.trim().substring(5);      // "Basic"
s.trim().substring(0, 4);   // "Java": chỉ số cuối không được lấy
s.toUpperCase();            // " JAVA BASIC "
s.contains("Bas");          // true; còn có startsWith, endsWith
s.replace("Basic", "Core"); // " Java Core "
"a,b,,c,,".split(",");      // [a, b, , c]: chuỗi rỗng ở cuối bị bỏ
String.join("-", "a", "b"); // "a-b"
"ab".repeat(3);             // "ababab" (Java 11)
"Java".equalsIgnoreCase("JAVA"); // true
char[] chars = s.toCharArray();  // chuỗi -> mảng char; new String(chars) để đổi ngược lại

split, replaceAll, matches nhận regex (biểu thức mẫu), không phải chuỗi thường:

  • "a.b".split(".") trả về mảng rỗng vì . khớp mọi ký tự; phải viết split("\\.").
  • replaceAll/matches biên dịch lại pattern ở mỗi lần gọi. split có đường tắt cho separator một ký tự như "," hay "\\.".
  • Chi tiết ở Regex: cú pháp, Java API và bài tập.

Một số tài liệu ghi " Java Basic ".length() là 13. Đếm lại: 1 dấu cách + 4 chữ + 1 dấu cách + 5 chữ + 1 dấu cách = 12.

So sánh chuỗi: == và equals

String a = "hello";
String b = new String("hello");
String c = "hel" + "lo";      // hằng số lúc biên dịch, được gộp thành "hello"
a == b;                       // false: hai object khác nhau
a.equals(b);                  // true: cùng nội dung
a == c;                       // true: cả hai là cùng một literal trong string pool

JVM dùng chung một object cho các literal giống nhau (string pool), nên == đôi khi “tình cờ” đúng. Đừng dựa vào đó: so sánh nội dung luôn dùng equals. Viết hằng số bên trái ("ACTIVE".equals(status)) để không bị NullPointerException khi status là null.

Nối chuỗi trong vòng lặp và StringBuilder

result = result + i trong vòng lặp tạo chuỗi mới mỗi lượt và copy lại toàn bộ nội dung cũ, tổng chi phí O(n²). StringBuilder giữ một mảng nới rộng được, nên append tốn O(1) khấu hao (thỉnh thoảng phải nới mảng, nhưng chia đều ra mỗi lần vẫn là hằng số):

StringBuilder sb = new StringBuilder();
for (int i = 0; i < 10_000; i++) sb.append(i).append(',');
sb.setLength(sb.length() - 1);   // bỏ dấu phẩy cuối
sb.insert(0, ">> ");             // chèn ở đầu
sb.reverse();                    // đảo ngược; còn có delete(start, end), replace(start, end, str)
String result = sb.toString();
  • Nối vài chuỗi trên một dòng ("Xin chào " + name + "!") thì cứ dùng +, compiler tự tối ưu.
  • StringBuffer giống StringBuilder nhưng mọi method đều synchronized. Tài liệu cũ khuyên dùng khi “lập trình đa luồng”, nhưng hiếm khi đúng: mỗi thread nên tự build chuỗi của mình.
  • String pool, intern() và so sánh chi tiết các lựa chọn nằm trong bài wrapper, BigDecimal và String.

Bài tập

Đề đã được viết lại ngắn gọn theo cách của mình. Code đã chạy thử trên JDK 21.

  1. Tính tổng các phần tử của mảng.
  2. Tìm vị trí của n trong mảng, không có thì trả về -1.
  3. Phần tử lớn nhất của mảng 2D.
  4. Mảng đối xứng (đọc xuôi và ngược như nhau, ví dụ [1, 2, 3, 2, 1]), in YES/NO.
  5. Tìm số xuất hiện nhiều hơn một lần và có vị trí (lần xuất hiện đầu tiên) nhỏ nhất; không có thì in NO. N tối đa 100 000. Input: dòng đầu là số bộ test T, mỗi bộ gồm một dòng N và một dòng N số. Mẫu: 10 5 3 4 3 5 6 cho 5, 1 2 3 4 cho NO.
  6. Tính tích của ma trận A (cỡ N×M) với ma trận chuyển vị của nó. Đọc nhiều bộ test (dòng đầu là số bộ test, mỗi bộ gồm n m rồi n dòng của ma trận), in Test k: trước mỗi ma trận kết quả, các số cách nhau đúng một dấu cách.
  7. Nhập 5 số nguyên vào mảng, in tổng và số lớn nhất.
  8. Tính tổng và điểm trung bình của mảng {8.5, 7.0, 9.0, 6.5, 8.0} bằng for-each.
  9. Kiểm tra người thắng trên bàn cờ caro 3×3 (mảng char[3][3], ô trống là ' '): thắng khi có 3 ký tự giống nhau trên một hàng, một cột hoặc một đường chéo.
Lời giải bài 1–5: tổng, tìm kiếm, max 2D, đối xứng, số lặp đầu tiên

1. Dùng long cho biến tổng để tránh tràn:

static long sum(int[] a) {
    long s = 0;
    for (int x : a) s += x;
    return s;               // hoặc Arrays.stream(a).asLongStream().sum()
}

2. Tìm kiếm tuyến tính, O(n):

static int indexOf(int[] a, int target) {
    for (int i = 0; i < a.length; i++) if (a[i] == target) return i;
    return -1;
}

3. Khởi tạo bằng Integer.MIN_VALUE chứ không phải 0, vì mảng có thể toàn số âm. Đồng thời xử lý trường hợp có hàng rỗng:

static int max2D(int[][] m) {
    int max = Integer.MIN_VALUE;
    boolean any = false;
    for (int[] row : m) for (int x : row) { max = Math.max(max, x); any = true; }
    if (!any) throw new IllegalArgumentException("Ma trận rỗng");
    return max;
}

4. Kỹ thuật hai con trỏ như bài palindrome ở bài vòng lặp và hàm:

static boolean isSymmetric(int[] a) {
    for (int i = 0, j = a.length - 1; i < j; i++, j--) if (a[i] != a[j]) return false;
    return true;
}

5. N tới 100 000 nên không dùng O(n²). Đếm tần suất bằng HashMap rồi duyệt lại mảng từ đầu; O(n) thời gian, O(n) bộ nhớ:

static String firstRepeated(int[] a) {
    Map<Integer, Integer> count = new HashMap<>();
    for (int x : a) count.merge(x, 1, Integer::sum);
    for (int x : a) if (count.get(x) > 1) return String.valueOf(x);
    return "NO";
}
// [1, 5, 3, 4, 5, 3] -> 5 (cả 5 và 3 đều lặp, nhưng 5 xuất hiện trước)

Với mẫu 10 5 3 4 3 5 6 cũng vậy: cả 5 và 3 đều lặp, nhưng 5 xuất hiện trước.

Lời giải bài 6: nhân ma trận với chuyển vị và đọc nhiều bộ test

Kết quả là ma trận N×N, với C[i][j] = Σₖ A[i][k] · A[j][k]. Không cần tạo ma trận chuyển vị, vì Aᵀ[k][j] = A[j][k]:

static long[][] timesTranspose(int[][] a) {
    int n = a.length, m = a[0].length;
    long[][] c = new long[n][n];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            long s = 0;
            for (int k = 0; k < m; k++) s += (long) a[i][k] * a[j][k];
            c[i][j] = s;
        }
    return c;   // [[1,2],[3,4]] -> [[5,11],[11,25]]
}

Kết quả luôn đối xứng (C[i][j] == C[j][i]), nên có thể chỉ tính nửa trên rồi chép sang nửa dưới, giảm một nửa số phép tính.

Phần đọc nhiều bộ test và in kết quả:

// import java.io.*; import java.util.StringJoiner;
public static void main(String[] args) throws IOException {
    StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    in.nextToken(); int t = (int) in.nval;
    StringBuilder out = new StringBuilder();
    for (int test = 1; test <= t; test++) {
        in.nextToken(); int n = (int) in.nval;
        in.nextToken(); int m = (int) in.nval;
        int[][] a = new int[n][m];
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) { in.nextToken(); a[i][j] = (int) in.nval; }
        out.append("Test ").append(test).append(":\n");
        for (long[] row : timesTranspose(a)) {
            StringJoiner line = new StringJoiner(" ");
            for (long v : row) line.add(Long.toString(v));
            out.append(line).append('\n');
        }
    }
    System.out.print(out);
}

Mẫu 1 / 2 2 / 1 2 / 3 4 cho ra Test 1: / 5 11 / 11 25. StringJoiner lo phần “đúng một dấu cách, không thừa ở cuối dòng”, lỗi hay khiến bài bị chấm sai trên các trang luyện thuật toán.

Lời giải bài 7–9: nhập mảng, for-each, bàn cờ caro

7. Lấy phần tử đầu làm mốc cho max, không dùng 0:

Scanner in = new Scanner(System.in);
int[] a = new int[5];
for (int i = 0; i < a.length; i++) {
    System.out.print("Số thứ " + (i + 1) + ": ");
    a[i] = Integer.parseInt(in.nextLine().trim());
}
long sum = 0;
int max = a[0];                       // lấy phần tử đầu làm mốc, không dùng 0 (mảng có thể toàn số âm)
for (int x : a) {
    sum += x;
    if (x > max) max = x;
}
System.out.println("Tổng các số là: " + sum + ", số lớn nhất là: " + max);   // {3, 15, 7, 12, 15} -> 52 và 15

8.

double[] scores = {8.5, 7.0, 9.0, 6.5, 8.0};
double total = 0;
for (double s : scores) total += s;
System.out.printf("Tổng: %.1f, trung bình: %.2f%n", total, total / scores.length);   // 39.0 và 7.80

For-each không cho biết chỉ số. Cần in “môn thứ i” thì quay về for có chỉ số.

9.

static char winner(char[][] b) {
    for (int i = 0; i < 3; i++) {
        if (b[i][0] != ' ' && b[i][0] == b[i][1] && b[i][1] == b[i][2]) return b[i][0];   // hàng i
        if (b[0][i] != ' ' && b[0][i] == b[1][i] && b[1][i] == b[2][i]) return b[0][i];   // cột i
    }
    char c = b[1][1];                                                                    // hai đường chéo đều đi qua tâm
    if (c != ' ' && ((b[0][0] == c && b[2][2] == c) || (b[0][2] == c && b[2][0] == c))) return c;
    return ' ';                                                                          // chưa ai thắng
}
// {{'X','O','X'}, {' ','X','O'}, {'O',' ','X'}} -> 'X' (đường chéo chính)

Cùng cách nghĩ dùng cho ảnh số: ảnh xám là int[height][width], ảnh màu là int[height][width][3] (R, G, B). Tài liệu gốc ghi Int[][] (chữ I hoa, không biên dịch được) và nói arr[0][1] của một mảng vừa tạo in ra 20; thực ra mảng mới tạo toàn số 0.

Lab 03: danh sách điểm bằng hai mảng song song

Đề (viết lại): nhập tên và điểm của 3 học sinh, lưu tên vào String[] và điểm vào double[]; in danh sách, in điểm trung bình của lớp, rồi in những học sinh có điểm từ 8 trở lên.

Hai mảng song song hợp với chương này (chưa học class), nhưng dễ vỡ: sắp xếp một mảng mà quên mảng kia là tên và điểm lệch nhau. Một senior sẽ gom mỗi học sinh thành một record và dùng List.

Lời giải Lab 03 và cách viết lại bằng record
import java.util.Scanner;

public class Lab03 {
    public static void main(String[] args) {
        final int n = 3;
        String[] names = new String[n];
        double[] scores = new double[n];          // names[i] và scores[i] là của cùng một học sinh
        Scanner in = new Scanner(System.in);

        for (int i = 0; i < n; i++) {
            System.out.printf("Nhập tên học sinh %d: ", i + 1);
            names[i] = in.nextLine().strip();
            System.out.print("Nhập điểm: ");
            scores[i] = Double.parseDouble(in.nextLine().trim());
        }

        System.out.println("Danh sách học sinh:");
        double sum = 0;
        for (int i = 0; i < n; i++) {
            System.out.printf("%s - %.1f%n", names[i], scores[i]);
            sum += scores[i];
        }
        System.out.printf("Điểm trung bình: %.2f%n", sum / n);

        System.out.println("Học sinh có điểm >= 8:");
        boolean found = false;
        for (int i = 0; i < n; i++) {
            if (scores[i] >= 8) {
                System.out.printf("%s - %.1f%n", names[i], scores[i]);
                found = true;
            }
        }
        if (!found) System.out.println("(không có)");
    }
}

Với input Nam 8.5, An 6, Huy 9: trung bình 7.83, học sinh từ 8 điểm là Nam - 8.5 và Huy - 9.0. Output mẫu trong tài liệu gốc ghi “Linh - 8.5”, nhưng input không có ai tên Linh; đúng ra là Nam.

Viết lại bằng record và List:

record Student(String name, double score) {}

List<Student> students = List.of(new Student("Nam", 8.5), new Student("An", 6), new Student("Huy", 9));
double average = students.stream().mapToDouble(Student::score).average().orElse(Double.NaN);   // 7.83...
List<String> good = students.stream().filter(s -> s.score() >= 8).map(Student::name).toList(); // [Nam, Huy]

average() trả về OptionalDouble, nên danh sách rỗng phải được xử lý rõ ràng thay vì âm thầm chia cho 0.

Ghi nhớ

  • Giải thích được vì sao truy cập mảng là O(1) và vì sao duyệt theo hàng nhanh hơn theo cột.
  • Phân biệt được length, length(), size(), và biết so sánh, in, copy sâu một mảng 2D.
  • Giải thích được vì sao == với chuỗi đôi khi đúng, và vì sao vẫn phải dùng equals.
  • Biết khi nào dùng +, khi nào dùng StringBuilder, và vì sao StringBuffer hầu như không cần.
  • Nhớ ba bẫy của String: split nhận regex, toUpperCase() phụ thuộc locale, length() đếm đơn vị UTF-16.

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

Junior

Giá trị mặc định của các phần tử trong new int[3], new boolean[2], new String[2] là gì?

0, false, null.

Biến cục bộ thì không có giá trị mặc định: dùng khi chưa gán sẽ bị lỗi biên dịch.

length, length() và size() khác nhau thế nào?

array.length là field của mảng, string.length() là method của String, list.size() là method của collection.

string.length() trả về số đơn vị UTF-16 (emoji có thể tính là 2). Ba cách viết khác nhau vì mảng là kiểu đặc biệt của JVM, còn String và List là class bình thường.

So sánh hai chuỗi và hai mảng thế nào cho đúng?

Chuỗi dùng equals; mảng dùng Arrays.equals (hoặc Arrays.deepEquals cho nhiều chiều).

  • Chuỗi: a == b chỉ so sánh địa chỉ (đôi khi đúng do string pool, đừng dựa vào). Viết "CONST".equals(x) hoặc Objects.equals(a, b) để an toàn với null.
  • Mảng: a.equals(b) của mảng cũng chỉ so sánh địa chỉ.

Mid

Mảng 2D trong Java được lưu thế nào? Vì sao duyệt theo hàng nhanh hơn duyệt theo cột?

Mảng 2D là mảng của các tham chiếu, mỗi hàng là một mảng 1D riêng; duyệt theo hàng đọc các ô liền nhau nên tận dụng được cache.

Các hàng có thể dài khác nhau. Phần tử trong cùng một hàng nằm liền nhau, nên duyệt theo hàng tận dụng được cache line của CPU (khối dữ liệu CPU nạp một lần). Duyệt theo cột thì nhảy qua lại giữa các object khác nhau, dễ bị cache miss.

Vì sao nối chuỗi bằng + trong vòng lặp chậm? StringBuilder và StringBuffer khác nhau thế nào?

Mỗi lần s = s + x tạo chuỗi mới và copy toàn bộ nội dung cũ, n lần nối tốn O(n²); StringBuilder nối với O(1) khấu hao, StringBuffer giống vậy nhưng synchronized.

  • StringBuilder giữ một mảng nới rộng được.
  • StringBuffer cùng API, mọi method synchronized, chậm hơn một chút và hầu như không cần, vì chuỗi đang build thường chỉ thuộc về một thread.
  • Nối vài giá trị trên một dòng thì cứ dùng +; từ Java 9 compiler sinh lời gọi invokedynamic tối ưu cho việc đó.
Arrays.copyOf là copy nông nghĩa là sao? Copy mảng 2D thế nào?

Copy nông là chỉ copy giá trị từng ô; với mảng object hay mảng 2D, ô là tham chiếu nên bản sao vẫn dùng chung object bên dưới. Copy sâu mảng 2D thì copy từng hàng.

Arrays.copyOf, clone() và System.arraycopy đều copy nông. Với mảng primitive, đó là bản sao thật. Với mảng 2D, sửa copy[0][0] thì original[0][0] cũng đổi. Copy sâu: int[][] copy = new int[m.length][]; for (int i = 0; i < m.length; i++) copy[i] = m[i].clone();.

Senior

Vì sao ArrayList thêm phần tử với chi phí O(1) khấu hao, trong khi bên dưới là mảng cố định?

Vì mỗi lần đầy, dung lượng được nhân lên khoảng 1,5 lần, nên tổng chi phí copy qua n lần thêm chỉ là O(n), tức O(1) mỗi lần.

Một lần nới mảng tốn O(n), nhưng rất hiếm khi xảy ra. Nếu biết trước kích thước thì khởi tạo new ArrayList<>(expectedSize) để tránh copy nhiều lần và đỡ tạo rác cho GC.

Arrays.sort dùng thuật toán gì cho mảng primitive và mảng object? Vì sao khác nhau?

Primitive dùng dual-pivot quicksort (nhanh, ít bộ nhớ, không ổn định); object dùng TimSort (ổn định). Khác nhau vì chỉ object mới cần giữ thứ tự của các phần tử bằng nhau.

  • Hai số 5 giống hệt nhau không phân biệt được, nên với primitive, không ổn định cũng không sao.
  • TimSort ổn định (phần tử bằng nhau giữ nguyên thứ tự ban đầu, quan trọng khi sắp xếp nhiều lần theo các tiêu chí khác nhau), rất nhanh với dữ liệu gần có thứ tự, đổi lại tốn thêm tối đa n/2 bộ nhớ.
  • Mảng rất lớn thì có Arrays.parallelSort, chạy song song trên ForkJoinPool.

Từ vựng tiếng Anh

Term Phát âm Nghĩa Ví dụ câu dùng khi phỏng vấn
contiguous memory /kənˈtɪɡjuəs/ bộ nhớ liền kề “Arrays use contiguous memory, which makes them cache-friendly.”
jagged array /ˈdʒæɡɪd/ mảng răng cưa “A 2D array in Java can be jagged because each row is a separate array.”
amortized /ˈæmərtaɪzd/ khấu hao (chi phí trung bình) “ArrayList add is amortized O(1).”
index /ˈɪndeks/ chỉ số “Array indexes start at zero and go up to length minus one.”
out of bounds /aʊt əv baʊndz/ vượt ngoài phạm vi “Reading index 5 of a five-element array throws an out-of-bounds exception.”
shallow copy /ˈʃæloʊ ˈkɑːpi/ bản sao nông “Arrays.copyOf makes a shallow copy, so nested arrays are still shared.”
immutable /ɪˈmjuːtəbl/ bất biến “Strings are immutable, so every concatenation creates a new object.”
row-major order /roʊ ˈmeɪdʒər/ duyệt theo hàng trước “Iterating in row-major order is faster because each row is contiguous.”
two-pointer technique kỹ thuật hai con trỏ “I check symmetry with the two-pointer technique in O(1) extra space.”

Phần lớn hình minh hoạ trong slide lấy từ sách Introduction to Java Programming and Data Structures (Y. Daniel Liang, bản 11), một tài liệu tốt nếu muốn đọc thêm.


Ghi chép dựa trên khoá Fundamentals of Backend (Ronin Engineer) và tài liệu Java Core của Hỏi Dân IT, cộng thêm kiến thức tự tìm hiểu, viết lại theo cách hiểu của mình.