Post

Array - Mảng

Posted Updated
By TungDaDev 14 min read

1. Giới thiệu

Trong khoa học máy tính, cấu trúc dữ liệu mảng là một cấu trúc dữ liệu bao gồm một nhóm các phần tử (giá trị) hoặc biến, mỗi phần tử được xác định ít nhất bằng một chỉ số (index) hoặc khóa (key).

Mảng là một trong những cấu trúc dữ liệu quan trọng nhất và hầu hết các chương trình đều dùng nó. Các cấu trúc dữ liệu khác cũng được hiện thực bằng mảng, thí dụ như danh sách hoặc chuỗi. Nó rất hiệu quả trong việc tận dụng cách đánh địa chỉ trên máy tính. Trong hầu hết các máy tính hiện đại và các thiết bị lưu trữ ngoài, bộ nhớ là chuỗi một chiều các “giá trị” và chỉ số của nó chính là địa chỉ. Bộ xử lý, đặc biệt là bộ xử lý vector, thường tối ưu hóa các tác vụ trên mảng.

Khái niệm mảng thường dùng có nghĩa là kiểu dữ liệu mảng được cung cấp bởi hầu hết các ngôn ngữ lập trình cấp cao, nó bao gồm tập hợp các giá trị hoặc biến có thể lựa chọn bằng một hoặc nhiều chỉ số được tính toán trong lúc chạy. Kiểu dữ liệu mảng thường được hiện thực bằng cấu trúc mảng; tuy nhiên một số ngôn ngữ lập trình có thể hiện thực bằng bảng băm, cây tìm kiếm hoặc các cấu trúc dữ liệu khác.

2. Khai báo mảng

Kiểu dữ liệu trong mảng có thể là kiểu nguyên thủy (primitive type) hoặc kiểu đối tượng (object). Mảng trong Java là dựa trên chỉ mục (index), phần tử đầu tiên của mảng được lưu trữ tại chỉ mục 0.

Một mảng được khai báo gồm 2 thành phần: kiểu dữ liệu và tên biến mảng.

1
2
3

type var-name[];
hoặc
type[] var-name;

Một số ví dụ khai báo mảng:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

// cả hai đều hợp lệ
int intArray[]; 
or int[] intArray; 

byte byteArray[];
short shortsArray[];
boolean booleanArray[];
long longArray[];
float floatArray[];
double doubleArray[];
char charArray[];

// một mảng tham chiếu đến các đối tượng
// lớp MyClass được khởi tạo từ người dùng
MyClass myClassArray[]; 

Object[] ao,        // mảng Object
Collection[] ca;  // mảng Collection

Mặc dù khai báo đầu tiên ở trên thiết lập thực tế rằng intArray là một biến mảng nhưng không có mảng nào thực sự tồn tại. Nó chỉ đơn giản nói với trình biên dịch rằng biến (intArray) này sẽ chứa một mảng kiểu số nguyên. Để liên kết intArray với một mảng số nguyên thực sự bạn phải cấp phát một mảng bằng cách sử dụng new và gán nó cho intArray.

Khi một mảng được khai báo, chỉ một tham chiếu của mảng được tạo. Để thực sự tạo hoặc cung cấp bộ nhớ cho mảng, bạn tạo một mảng như sau:

1

var-name = new type [size];

Ở đây, type chỉ định kiểu dữ liệu được cấp phát, size chỉ định số phần tử trong mảng và var-name là tên của biến mảng được liên kết với mảng. Nghĩa là, để sử dụng new để cấp phát một mảng, bạn phải chỉ định kiểu và số phần tử để cấp phát.

1
2
3
4
5
6

int intArray[];    //khái báo mảng
intArray = new int[20];  // cấp phát bộ nhớ cho mảng

hoặc

int[] intArray = new int[20]; // kết hợp cả 2 trong 1

Lưu ý:

  • Các phần tử trong mảng được phân bổ bởi new sẽ tự động được khởi tạo bằng 0 (đối với kiểu số), false (đối với boolean) hoặc null (đối với kiểu tham chiếu) - Tham khảo giá trị mảng mặc định trong Java.
  • Khởi tạo một mảng là một quá trình gồm hai bước. Đầu tiên, bạn phải khai báo một biến kiểu mảng mong muốn. Thứ hai, bạn phải cấp phát bộ nhớ sẽ chứa mảng, sử dụng new và gán nó cho biến mảng. Do đó, trong Java tất cả các mảng đều được cấp phát động.

3. Thao tác với mảng

Truy cập các phần tử của mảng

Mỗi phần tử trong mảng được truy cập thông qua chỉ mục của nó. Chỉ số bắt đầu bằng 0 và kết thúc bằng (tổng kích thước mảng) -1. Tất cả các phần tử của mảng có thể được truy cập bằng cách sử dụng vòng lặp FOR. (ngoài ra bạn có thể tìm hiểu sử dụng với các vòng lặp còn lại)

1
2

for (int i = 0; i < arr.length; i++)
  System.out.println("Phần tử thứ " + i +  " : " + arr[i]);

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

public class Array {

    public static void main(String[] args) {
        // TODO Auto-generated method stub

        // khai báo mảng số nguyên.
        int[] arr;

        // cấp phát bộ nhớ cho 5 phần tử số nguyên
        arr = new int[5];

        // khởi tạo phần tử đầu tiên với giá trị bằng 10
        arr[0] = 10;

        // khởi tạo phần tử đầu tiên với giá trị bằng 20
        arr[1] = 20;

        // và các phần tử kế tiếp
        arr[2] = 30;
        arr[3] = 40;
        arr[4] = 50;

        // truy cập các phần tử theo chỉ mục
        for (int i = 0; i < arr.length; i++)
            System.out.println("Element at index " + i + " : " + arr[i]);
    }

}

Mảng đối tượng

Một mảng các đối tượng được tạo giống như một mảng các mục dữ liệu kiểu nguyên thủy theo cách sau:

1

Student[] arrStudents = new Student[9]; // Student là một lớp do người dùng định nghĩa

Mảng arrStudents có 9 vùng nhớ, mỗi vùng là địa chỉ của một đối tượng Student được lưu trữ. Các đối tượng Student phải được khởi tạo bằng sử dụng Contructor và các tham chiếu của chúng phải được gán cho các phần tử mảng như ví dụ sau:

Student.java:

1
2
3
4
5
6
7
8
9

public class Student {
    public int roll_no;
    public String name;

    Student(int roll_no, String name) {
        this.roll_no = roll_no;
        this.name = name;
    }
}

Array.java:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

public class Array {

    public static void main(String[] args) {
        // khai báo một mảng số nguyên.
        Student[] arr;

        // cấp phát bộ nhớ cho 5 đối tượng kiểu Student.
        arr = new Student[5];

        // khởi tạo phần tử đầu tiên của mảng
        arr[0] = new Student(1, "Michael");

        // khởi tạo các phần tử thứ 2 của mảng
        arr[1] = new Student(2, "Sonny");

        // và các phần tử còn lại
        arr[2] = new Student(3, "Tom Hagne");
        arr[3] = new Student(4, "Vito");
        arr[4] = new Student(5, "Vicent");

        // truy cập các phần tử theo chỉ mục
        for (int i = 0; i < arr.length; i++)
            System.out.println("Phần tử thứ " + i + " : " + arr[i].roll_no + " " + arr[i].name);
    }
}

Điều gì xảy ra nếu chúng ta cố gắng truy cập phần tử bên ngoài kích thước mảng? JVM ném ArrayIndexOutOfBoundsException để chỉ ra rằng mảng đã được truy cập với một chỉ mục bất hợp pháp. Chỉ số âm hoặc lớn hơn hoặc bằng kích thước của mảng.

1
2
3
4
5
6
7
8
9
10

class Exam {
	public static void main(String[] args) {
		int[] arr = new int[2];
		arr[0] = 10;
		arr[1] = 20;

		for (int i = 0; i <= arr.length; i++)
			System.out.println(arr[i]);
	}
}

Mảng đa chiều

Mảng đa chiều (nhiều chiều) là mảng của mảng với mỗi phần tử của mảng giữ tham chiếu của mảng khác. Mảng nhiều chiều được tạo bằng cách thêm một tập hợp các dấu ngoặc vuông ([]) cho mỗi chiều.

1
2

int[][] intArray = new int[10][20]; // mảng hoặc ma trận 2 chiều
 int[][][] intArray = new int[10][20][10]; // mảng 3 chiều

Chúng ta lần lượt đi qua thêm các ví dụ sau:

ArrayMultiDimensional:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

public class ArrayMultiDimensional {
    public static void main(String args[]) {
        // khai báo và khởi tạo mảng 2 chiều
        int[][] arr = {
                        {2, 7, 9},
                        {3, 6, 1},
                        {7, 4, 2}
                     };

        // in mảng 2 chiều
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++)
                System.out.print(arr[i][j] + " ");

            System.out.println();
        }
    }
}

Truyền mảng vào các phương thức

Giống như các biến, mảng cũng có thể truyền được cho các phương thức. Ví dụ bên dưới sẽ chuyển mảng thành phương thức sum() để tính tổng các giá trị của mảng.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

public class ArraySum {

    public static void main(String args[]) {
        int arr[] = {3, 1, 2, 5, 4};

        // truyền mảng cho phương thức sum()
        sum(arr);

    }

    public static void sum(int[] arr) {
        // tính tổng giá trị mảng
        int sum = 0;

        for (int i = 0; i < arr.length; i++)
            sum += arr[i];

        System.out.println("Tổng các giá trị của mảng : " + sum);
    }
}

Trả về mảng từ các phương thức

Như thường lệ, một phương thức cũng có thể trả về một mảng. Ví dụ, chương trình dưới đây trả về một mảng từ phương thức x1

1
2
3
4
5
6
7
8
9
10
11
12
13

public class ReturnArray {
    public static void main(String args[]) {
        int arr[] = x1();

        for (int i = 0; i < arr.length; i++)
            System.out.print(arr[i] + " ");
    }

    public static int[] x1() {
        // trả về mảng
        return new int[]{1, 2, 3};
    }
}

Mảng (lớp) đối tượng

Mọi mảng đều có một lớp đối tượng được liên kết, được chia sẻ với tất cả các mảng khác có cùng kiểu.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

public class ArrayClassObject {
    public static void main(String args[]) {
        int intArray[] = new int[3];
        byte byteArray[] = new byte[3];
        short shortsArray[] = new short[3];

        // mảng chuỗi
        String[] strArray = new String[3];

        System.out.println(intArray.getClass()); // class [I
        System.out.println(intArray.getClass().getSuperclass()); // class java.lang.Object
        System.out.println(byteArray.getClass()); // class [B
        System.out.println(shortsArray.getClass()); // class [S
        System.out.println(strArray.getClass()); // class [Ljava.lang.String;
    }
}

Trong đó:

  • Chuỗi “[I” là chữ ký kiểu thời gian chạy cho đối tượng lớp “mảng có kiểu thành phần int“.
  • Lớp cha trực tiếp duy nhất của bất kỳ kiểu mảng nào là java.lang.Object.
  • Chuỗi “[B” là chữ ký kiểu thời gian chạy cho đối tượng lớp “mảng có kiểu thành phần byte”.
  • Chuỗi “[S” là chữ ký kiểu thời gian chạy cho đối tượng lớp “mảng có kiểu thành phần short”.
  • Chuỗi “[L” là chữ ký kiểu thời gian chạy cho đối tượng lớp “mảng có kiểu thành phần Class”.

Thành viên mảng

Bây giờ, như bạn đã biết rằng mảng là đối tượng của một lớp và lớp cha trực tiếp của mảng là lớp Đối tượng. Các thành viên của một kiểu mảng đều có các điểm chung sau đây:

  • Độ dài mảng là số lượng thành phần của mảng. độ dài có thể là số dương hoặc số không.
  • Tất cả các thành viên đều kế thừa từ lớp Object; phương thức duy nhất của Object không được kế thừa là phương thức clone của nó.
  • Phương thức public clone(), ghi đè phương thức clone trong lớp Object và không có ngoại lệ nào được kiểm tra.

Sao chép mảng

Khi bạn sao chép mảng một chiều, chẳng hạn như Object [], “bản sao chép sâu” được thực hiện với mảng mới chứa bản sao của các phần tử của mảng ban đầu thay vì tham chiếu.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

public class CloneArray {
    public static void main(String args[]) {
        /*
         * Giả sử ta có mảng intArray = {1,2,3}
         */
        int intArray[] = {1, 2, 3};

        int cloneArray[] = intArray.clone();

        // sẽ in false khi bản sao chép sâu được tạo cho mảng một chiều
        System.out.println(intArray == cloneArray);

        for (int i = 0; i < cloneArray.length; i++) {
            System.out.print(cloneArray[i] + " ");
        }
    }
}

Tuy nhiên, một bản sao của mảng đa chiều (như Object [] []) là một “bản sao chép cạn”, có nghĩa là nó chỉ tạo một mảng mới duy nhất với mỗi mảng phần tử là một tham chiếu đến một mảng phần tử gốc nhưng các mảng con được chia sẻ.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

public class CloneArray2 {
    public static void main(String args[]) {
        int intArray[][] = {
                            {1, 2, 3},
                            {4, 5}
                        };

        int cloneArray[][] = intArray.clone();

        // in ra false
        System.out.println(intArray == cloneArray); // false

        // sẽ in true khi bản sao chép cạn được tạo
        // tức là các mảng con được chia sẻ
        System.out.println(intArray[0] == cloneArray[0]); // true
        System.out.println(intArray[1] == cloneArray[1]); // true

    }
}

4. Ưu – nhược điểm của Array

Ưu điểm:

  • Cho phép xử lí nhiều thành phần dữ liệu trong cùng 1 thời điểm.
  • Bộ nhớ chỉ được cấp cho mảng khi mảng thực sự được sử dụng.
  • Truy cập ngẫu nhiên: chúng ta có thể lấy bất cứ dữ liệu nào ở tại bất cứ vị trí chỉ mục nào.

Nhược điểm:

  • Giới hạn kích cỡ: Kích thước mảng cố định không thay đổi. Nó không tăng kích thước của nó tại runtime. Để xử lý vấn đề này, Collection Framework được sử dụng trong Java.
  • Các phần tử của một mảng là được đặt và tham chiếu liên tiếp nhau trong bộ nhớ, điều đó là khó khăn khi ta cố tình bỏ đi một phần tử nào đó trong mảng, nó mất tính liên tiếp. Thông thường một kỹ thuật mà thường sử dụng là tạo một mảng mới lưu trữ các đối tượng của mảng ban đầu và bỏ đi các phần tử không cần thiết, tuy nhiên điều này làm giảm hiệu năng của chương trình.
  • Với trường hợp mở rộng mảng cũng với kỹ thuật tương tự là khởi tạo một mảng mới với kích cỡ lớn hơn sau đó thì copy các phần tử mảng cũ cho mảng mới .
  • Chỉ lưu trữ được duy nhất cùng một kiểu dữ liệu trong mảng

Nhìn chung, mảng là cấu trúc dữ liệu thuộc dạng cơ bản và dễ nhất mà mình muốn chia sẻ với các bạn trong Series này. Nhưng hãy nhìn vào phần ưu – nhược điểm mà xem, không một cấu trúc dữ liệu nào là hoàn hảo hết cả - chỉ có cái nào là phù hợp hơn thôi. Trong các bài viết sau, bạn sẽ thấy thêm nhiều cái mới mẽ có thể khắc phục được các nhược điểm mà Array gặp phải. Cùng đón xem nhé – Chúc bạn học tốt.

Bài viết mang tính chất “ghi chú, lưu trữ, chia sẻ và phi lợi nhuận”.
Nếu bạn thấy hữu ích, đừng quên chia sẻ với bạn bè và đồng nghiệp của mình nhé!

Happy coding! 😎 👍🏻 🚀 🔥

Information Technology, Software Development
Java Data-Structures & Algorithms
This post is licensed under CC BY 4.0 by the author.