[Java] - Array

Hế lô anh em ✌️✌️✌️

Array là một trong những cấu trúc dữ liệu cơ bản và được hỗ trợ bởi hầu hết các ngôn ngữ lập trình trong đó có Java.

Bài viết hôm nay mình sẽ cùng anh em tìm hiểu về cấu trúc dữ liệu này cũng như cách sử dụng trong một số trường hợp cơ bản.

1. Array là gì?

"An array is a container object that holds a fixed number of values of a single type. The length of an array is established when the array is created. After creation, its length is fixed" 

Đây là định nghĩa về Array được mình trích từ docs của Java. Nếu dịch ra thì có thể hiểu Array là một đối tượng lưu trữ dữ liệu, dữ liệu được lưu trữ trong một Array phải cùng kiểu. Kích thước của Array là không đổi sau khi nó được khởi tạo.

Array có thể lưu trữ cả kiểu dữ liệu Primitive Types và Object Types.

Độ phức tạp thời gian của một số thao tác đối với Array:

+ Truy cập một phần tử bất kỳ (thông qua index): O(1)

+ Duyệt toàn bộ phần tử: O(n)

+ Cập nhật giá trị của một phần tử (thông qua index): O(1)

+ Thêm mới phần tử (bản chất phải tạo một Array mới): O(n)

+ Xóa một phần tử (bản chất phải tạo một Array mới): O(n) 

2. Khai báo và khởi tạo ra sao?

2.1 - Khai báo

Có hai cách để khai báo một Array trong Java:

Đầu tiên là kiểu khai báo phổ biến và được sử dụng nhiều khi làm việc với Array trong Java.

<Kiểu dữ liệu>[] <Tên của Array>;

Ví dụ: 

int[] numbers;
String[] names;

Tiếp theo, kiểu khai báo này ít được sử dụng vì thường khó để phân biệt giữa kiểu dữ liệu và tên biến.

<Kiểu dữ liệu> <Tên của Array>[];

Ví dụ:

int numbers[];
String names[];

2.2 - Khởi tạo

Giống như việc khai báo cũng có hai cách để khởi tạo một Array. 

Đầu tiên cách thông dụng nhất là khi chúng ta chưa biết cụ thể kích thước Array cần khởi tạo hoặc tập các giá trị cần khởi tạo.

int numbers[] = new int[100];        // Khởi tạo Array 100 phần tử kiểu int với giá trị mặc định là 0 
String names[] = new String[100];    // Khởi tạo Array 100 phần tử kiểu String với giá trị mặc định là null

Lưu ý, cách khởi tạo này các giá trị sẽ được khởi tạo với giá trị mặc định. Ví dụ nếu kiểu dữ liệu là kiểu Primitive Types giá trị khởi tạo mặc định sẽ là 0, còn với kiểu dữ liệu là Object thì giá trị mặc định sẽ là null.

Trường hợp chúng ta muốn khởi tạo một Array với tập các giá trị có sẵn thì có thể khởi tạo như sau:

int numbers[] = new int[] {1, 2, 3, 4, 5};                  // Khởi tạo Array với 5 phần tử kiểu int
String names[] = new String[] {"A", "B", "C", "D", "E"};    // Khởi tạo Array với 5 phần tử kiểu String

Hoặc viết gọn hơn:

int numbers[] = {1, 2, 3, 4, 5};                  // Khởi tạo Array với 5 phần tử kiểu int
String names[] = {"A", "B", "C", "D", "E"};       // Khởi tạo Array với 5 phần tử kiểu String

Với cách khởi tạo này không cần phải cố định số phần tử của Array, kích thước của Array chính là số lượng phần tử chúng ta khởi tạo.

3. Làm sao truy cập phần tử của Array?

Để truy cập một phần tử trong Array chúng ta phải sử dụng index của phần tử đó với cú pháp như sau:

<Tên Array>[<index của phần tử>]

Ví dụ:

int[] numbers = {1, 2, 3, 4, 5};
String[] names = {"A", "B", "C", "D", "E"};

int numberAtIndex_0 = numbers[0];
String nameAtIndex_0 = names[0];

Note: Khi truy cập một phần tử trong Array phải hết sức lưu ý về index của phần tử đó. Trong trường hợp nếu truyền một giá trị index < 0 hoặc một giá trị index lớn hơn hoặc bằng kích thước Array sẽ gặp phải ngoại lệ ArrayIndexOutOfBoundsException

int[] numbers = {1, 2, 3, 4, 5};
String[] names = {"A", "B", "C", "D", "E"};

int numberAtIndex_5 = numbers[5];
String nameAtIndex_5 = names[5];

Kết quả:

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 5 out of bounds for length 5

4. Làm sao duyệt qua các phần tử của Array?

Giống như các cấu trúc dữ liệu khác để duyệt qua các phần tử của Array có thể sử dụng các vòng lặp.

4.1 - Sử dụng vòng lặp for (cổ điển)

String[] names = {"A", "B", "C", "D", "E"};

System.out.printf("%s%10s%n", "index", "value");
for(int index=0; index < names.length; index++) {
    System.out.printf("%s%10s%n", index, names[index]);
}

Kết quả:

index     value
0         A
1         B
2         C
3         D
4         E

Note: Để lấy được kích cỡ (chiều dài) của Array chúng ta sử dụng thuộc tính length

4.2 - Sử dụng vòng lặp while

Về tư tưởng thì sử dụng vòng lặp while không khác gì vòng lặp for bên trên.

String[] names = {"A", "B", "C", "D", "E"};

System.out.printf("%s%10s%n", "index", "value");

int index = 0;
while (index < names.length) {
    System.out.printf("%s%10s%n", index, names[index]);
    index ++ ;
}

4.3 - Sử dụng vòng lặp foreach

Chúng ta có thể sử dụng vòng lặp foreach để duyệt qua các phần tử của mảng trong hai trường hợp:

+ Không cần sử dụng đến index của phần tử

+ Không cần phải thay đổi giá trị của phần tử

Cụ thể mình có ví dụ sau:

+ Nếu sử dụng vòng lặp for cổ điển:

int[] numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

for (int index = 0; index < numbers.length; index++) {
    numbers[index] += 1;
    System.out.printf("%d%s", numbers[index], " ");
}

System.out.println();

for (int index = 0; index < numbers.length; index++) {
    System.out.printf("%d%s", numbers[index], " ");
}

Kết quả:

2 3 4 5 6 7 8 9 10 11 
2 3 4 5 6 7 8 9 10 11

+ Nếu sử dụng vòng lặp foreach

int[] numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

for (int number : numbers) {
    number += 1;
    System.out.printf("%d%s", number, " ");
}

System.out.println();

for (int index = 0; index < numbers.length; index++) {
    System.out.printf("%d%s", numbers[index], " ");
}

Kết quả

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

Dễ thấy rằng nếu sử dụng vòng lặp foreach thì bản chất biến của chúng ta (trong ví dụ này là biến number) giữ bản copy giá trị của phần tử tương ứng trong Array. Nên khi thay đổi giá trị của biến này cũng không ảnh hưởng tới giá trị gốc của phần tử tương ứng trong Array. 

5. Varargs

Varargs là gì? Varargs hoạt động như thế nào?

5.1 - Varargs là gì?

Varargs là viết tắt của variable agruments. Trong Java, một phương thức có tham số và tham số đó có thể nhận vào 0 hoặc nhiều giá trị một lúc thì tham số đó được gọi là varargs.

Ví dụ mình có hàm sum() như sau:

public int sum(int... numbers) {
    int sum = 0;
    for (int number: numbers) 
        sum += number;
    return sum;
}

sum(); // 0
sum(1, 2, 3); // 6
sum(1, 2, 3, 4); // 10

Tham số của hàm sum() này có thể nhận vào bao nhiêu giá trị tùy ý giống như cách mình truyền các giá trị cho tham số bên trên.

5.2 - Varargs hoạt động như thế nào?  

Về bản chất varargs giống như một Array. Khi một phương thức có tham số kiểu varargs, chúng ta truyền giá trị cho tham số đó thì một Array sẽ được khởi tạo với kích thước bằng với số lượng các giá trị truyền vào cho tham số.

Sau khi khởi tạo các giá trị truyền vào sẽ được gán lại vào Array và khi đó chúng ta có một tham số dạng Array gồm các giá trị chúng ta truyền vào.

Với cách thức hoạt động như vậy varargs giúp chúng ta giải quyết bài toán khi không biết trước số lượng các giá trị mà tham số có thể nhận.

Việc khởi tạo chỉ được thực hiện khi có giá trị truyền vào tham số sẽ giúp tối ưu hóa bộ nhớ cho quá trình khởi tạo đó.

Note: Mình cũng có một bài viết riêng về varargs đề cập đến việc làm sao sử dụng varargs cho đúng. Anh em có thể tham khảo tại đây.

6. Chuyển đổi từ Array sang List

Mỗi cấu trúc dữ liệu có ưu nhược điểm riêng và Array cũng vậy. Do đó đôi khi chúng ta muốn chuyển đổi các phần tử từ Array sang dạng List để làm việc thuận tiện hơn. 

Cách đơn giản nhất là sử dụng vòng lặp:

int[] numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

List<Integer> listOfNumbers = new ArrayList<>();
for (Integer number : numbers) {
    listOfNumbers.add(number);
}

Ngoài ra để ngắn gọn có thể sử dụng phương thức asList(T... a) của class Arrays. Phương thức này nhận vào một varargs như đã đề cập trong phần 5. Sau khi nhận vào tham số nó sẽ khởi tạo một list với những giá trị được truyền vào.

Integer[] numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
List<Integer> listOfNumbers = Arrays.asList(numbers);

Tuy nhiên cách này lại có hai nhược điểm:

+ Tham số không thể là một Array có các phần tử với kiểu dữ liệu nguyên thủy (primitive types)

int[] numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
List<Integer> listOfNumbers = Arrays.asList(numbers);  // error

+ Việc thêm hoặc xóa phần tử sẽ gặp ngoại lệ UnsupportedOperationException

Integer[] numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
List<Integer> listOfNumbers = Arrays.asList(numbers);
listOfNumbers.add(100);          // Exception: UnsupportedOperationException
listOfNumbers.remove(0);         // Exception: UnsupportedOperationException

7. Chuyển đổi từ Array sang Stream

Từ Java 8, việc giới thiệu Streams API đem đến nhiều điều mới mẻ và thuận tiện khi lập trình Java. Phần 6 mình đã cùng anh em tìm hiểu cách chuyển đổi các phần từ Array sang dạng List. Trong phần tiếp theo này mình sẽ cùng anh em tìm hiểu cách chuyển đổi từ Array sang Stream.

Chúng ta sử dụng phương thức stream(T[] arrray) của class Arrays

Integer[] numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
Stream<Integer> listOfNumbers = Arrays.stream(numbers);

Ngoài ra cũng có thể sử dụng phương thức stream(T[] array, int startInclusive, int endInclusive) để tạo một Stream với một tập các phần tử của Array ban đầu.

Integer[] numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
Stream<Integer> listOfNumbers = Arrays.stream(numbers, 0, 4);

8. Sắp xếp các phần tử trong Array

Sắp xếp là một trong những thao tác cơ bản khi chúng ta làm việc với các cấu trúc dữ liệu. Thực tế có rất nhiều thuật toán sắp xếp nhưng mình sẽ không đề cập đến chúng trong bài viết này.

Bài viết hôm nay mình sẽ chỉ giới thiệu phương thức sort() của class Arrays và cách chúng ta sử dụng nó để sắp xếp các phần tử của Array.

8.1 - Sắp xếp các phần tử kiểu dữ liệu primitive types

Integer[] numbers = {1, 6, 2, 0, 15, 9, 8, 7, 21, 10};
Arrays.sort(numbers); // after sorted: {0, 1, 2, 6, 7, 8, 9, 10, 15, 21}

8.2 - Sắp xếp các phần tử kiểu dữ liệu Object

Student[] students = {new Student(22, "Long"), new Student(23, "An"), new Student(19, "Cường")};
Arrays.sort(students, Comparator.comparing(Student::getAge));

Đối với dữ liệu kiểu Object chúng ta phải truyền thêm tham số thứ 2 là một đối tượng Comparator để hàm sort() biết được các đối tượng đó sẽ được sắp xếp theo thuộc tính nào.

Note: Thuật toán sử dụng bao gồm thuật toán merge sort đối với kiểu dữ liệu Object và quick sort đối với kiểu dữ liệu primitive types 

9. Tìm kiếm phần tử trong Array

Cùng với sắp xếp thì tìm kiếm cũng là một thao tác được sử dụng khá nhiều khi làm việc với các cấu trúc dữ liệu. 

Tìm kiếm có nhiều thuật toán khác nhau nhưng trong bài viết này mình tập trung vào những ý tưởng đơn giản để làm sao chúng ta triển khai việc tìm kiếm trong Array nhanh nhất.

9.1 - Sử dụng vòng lặp

Ý tưởng đơn giản nhất có lẽ vẫn là sử dụng vòng lặp để duyệt qua các phần tử của Array và kiểm tra xem đâu là phần tử chúng ta muốn tìm kiếm.

Integer[] numbers = {1, 6, 2, 0, 15, 9, 8, 7, 21, 10};

for(int index=0; index<numbers.length; index++) {
    if(numbers[index] == 21) {
        System.out.println("Phần tử " + numbers[index] + " được tìm thấy tại index " + index);
        break;
    }
}

int index = 0;
for (Integer number: numbers) {
    if(number == 21) {
        System.out.println("Phần tử " + numbers[index] + " được tìm thấy tại index " + index);
        break;
    }
    index++;
}

Ở đây mình muốn tìm kiếm phần tử có giá trị 21 và mình thực hiện lặp qua toàn bộ giá trị của Array, khi gặp phần tử có giá trị 21 mình thực hiện in ra và kết thúc bằng lệnh break.

Với phương pháp này rõ ràng nếu kích thước Array lớn và phần tử muốn tìm ở cuối Array thì chi phí tìm kiếm sẽ rất tốn kém.

9.2 - Sử dụng phương thức binarySearch()

Như mình đã phân tích bên trên, sử dụng vòng lặp là cách tư duy "nguyên thủy" nhất chúng ta có thể áp dụng nhưng nó lại không phải là phương pháp tối ưu.

Cũng chính vì điều đó các thuật toán tìm kiếm ra đời với mong muốn cải thiện hiệu năng. Tuy nhiên để triển khai một thuật toán tìm kiếm lại không hề đơn giản vì chúng ta phải hiểu nó và đôi khi chúng ta cũng không biết phải dùng thuật toán nào cho phù hợp.

Vậy giải pháp là sử dụng các hàm dựng sẵn được triển khai theo một thuật toán nào đó (trong bài viết này là thuật toán tìm kiếm nhị phân - binary search).

Arrays.binarySearch();

Integer[] numbers = {1, 6, 2, 0, 15, 9, 8, 7, 21, 10};

Arrays.sort(numbers);

int index1 = Arrays.binarySearch(numbers, 21);            // tìm kiếm trong toàn bộ Array
System.out.println("Phần tử " + numbers[index1] + " được tìm thấy tại index " + index1);

int index2 = Arrays.binarySearch(numbers, 0, 6, 15);      // tìm kiếm một phần của Array
System.out.println("Phần tử " + numbers[index2] + " được tìm thấy tại index " + index2);

Collections.binarySearch()

Integer[] numbers = {1, 6, 2, 0, 15, 9, 8, 7, 21, 10};

List<Integer> listOfNumbers = Arrays.asList(numbers);

Collections.sort(listOfNumbers);

int index = Collections.binarySearch(listOfNumbers, 21);
System.out.println("Phần tử " + listOfNumbers.get(index) + " được tìm thấy tại index " + index);

Note: Thuật toán tìm kiếm nhị phân hoạt động hiệu quả nhất trong trường hợp danh sách đã được sắp xếp. Chính vì vậy anh em có thể thấy mình đã chạy hàm sort() để sắp xếp danh sách trước khi thực hiện tìm kiếm. 

10. Kết hợp các Array

Đặc điểm của Array là không thể thêm hay xóa phần tử trên chính Array đó. Nhưng trong thực tế chúng ta gặp nhiều bài toán buộc phải kết hợp hai hay nhiều Array lại với nhau. Vậy phải làm sao?

Ý tưởng là tạo một Array mới với kích thước bằng tổng kích thước của các Array cần kết hợp. Nhưng kết hợp như thế nào?

10.1 - Sử dụng vòng lặp

int[] evenNumbers = {0, 2, 4, 6, 8, 10};
int[] oddNumbers = {1, 3, 5, 7, 9};

int[] numbers = new int[evenNumbers.length + oddNumbers.length];

for(int index=0; index<numbers.length; index++) {
    numbers[index] = (index < evenNumbers.length ? evenNumbers[index] : oddNumbers[index - evenNumbers.length]);
}

Ở đây mình thực hiện lặp qua Array mới được khởi tạo sau đó kiểm tra nếu index nhỏ hơn kích thước Array đầu tiên mình sẽ gán các giá trị của Array đầu tiên cho các vị trí tương ứng của Array mới. Nếu index lơn hơn kích thước Array đầu tiên mình sẽ bắt đầu gán các giá trị của Array thứ 2 cho các vị trí tương ứng tiếp theo của Array mới.

10.2 - Sử dụng phương thức Arrays.setAll()

Arrays.setAll(int[] array, IntUnaryOperator generator)

Thực ra đây chỉ là một cách viết ngắn hơn so với việc sử dụng vòng lặp như mình sử dụng bên trên.

int[] evenNumbers = {0, 2, 4, 6, 8, 10};
int[] oddNumbers = {1, 3, 5, 7, 9};

int[] numbers = new int[evenNumbers.length + oddNumbers.length];

Arrays.setAll(numbers, (index -> index < evenNumbers.length ? evenNumbers[index] : oddNumbers[index - evenNumbers.length]));

11. Multidimensional Arrays

Multidimensional Arrays được hiểu là Array của các Arrays. Về lý thuyết một Array có thể có rất nhiều chiều nhưng thông thường chúng ta chỉ làm việc với Array hai chiều hoặc ba chiều.

Để đơn giản bài viết này mình chỉ giới thiệu Array hai chiều (2-Dimensional Array)

11.1 - Khai báo

int[][] matrix;

11.2 - Khởi tạo

int[][] matrix = new int[5][5];

11.3 - Duyệt qua các phần tử

int wid = 5;
int hei = 5;
int[][] matrix = new int[wid][hei];

for(int i=0; i<wid; i++) {
    for(int j=0; j<hei; j++)
        matrix[i][j] = i*j;
}

for(int i=0; i<wid; i++) {
    for(int j=0; j<hei; j++)
        System.out.printf("%d ", matrix[i][j]);
    System.out.println();
}

12. Lời kết

Vậy là trong bài viết này mình đã cùng anh em điểm qua hầu hết các khái niệm cũng như thao tác cơ bản khi làm việc với Array trong Java.

Array tuy không phải là một cấu trúc dữ liệu phức tạp nhưng để sử dụng thành thạo và biết cách tối ưu thì không hề dễ dàng.

Hi vọng bài viết sẽ giúp anh em có cái nhìn tổng quan hơn về Array nói riêng và các thao tác đối với các loại cấu trúc dữ liệu nói chung.

Hẹn gặp lại anh em trong các bài viết tiếp theo.

Tham khảo:

https://www.baeldung.com/java-arrays-guide