Java Collections Framework

Giới thiệu

Lựa chọn cấu trúc dữ liệu tốt nhất và các thuật toán cho một tác vụ cụ thể là một trong những chìa khóa để phát triển phần mềm chất lượng cao.

Cấu trúc dữ liệu (data structure) là một tập các dữ liệu được tổ chức sao cho có hiệu quả nhất. Cấu trúc không chỉ lưu trữ dữ liệu mà còn hỗ trợ các hoạt động để truy cập và thao tác dữ liệu.

Lưu ý: Hiệu quả tức là chính xác; dùng ít bộ nhớ; khả năng tìm kiếm và truy xuất tốt, khả năng cập nhật, thêm bớt tốt; đơn giản, dễ hiểu.

Trong tư duy hướng đối tượng, một cấu trúc dữ liệu, còn được gọi là container object hoặc container, đây là một đối tượng lưu trữ các đối tượng khác, được gọi là dữ liệu (data) hoặc các phần tử (element). Để định nghĩa cấu trúc dữ liệu về cơ bản là định nghĩa một lớp sử dụng các trường để lưu trữ dữ liệu và cung cấp các phương pháp để hỗ trợ các hoạt động như tìm kiếm, chèn và xóa. Do đó để tạo một cấu trúc dữ liệu, tức tạo ra một thể hiện từ lớp. Sau đó bạn có thể áp dụng các phương thức để thao tác với dữ liệu, chẳng hạn như chèn một phần tử vào hoặc xóa một phần tử khỏi cấu trúc dữ liệu.

Java cung cấp nhiều cấu trúc dữ liệu khác có thể được sử dụng để tổ chức và thao tác dữ liệu một cách hiệu quả. Những cấu trúc dữ liệu này được gọi là Java Collections Framework.

Collections

interface Collection định nghĩa các thao tác chung cho list, vector, stack, queue, priorit queue và set.

Java Collection Framework hỗ trợ hai loại container:

• Một để lưu trữ một tập các phần tử gọi là collection
• Lưu trữ cặp key/value gọi là map.

Map là cấu trúc dữ liệu hiệu quả để nhanh chóng tìm kiếm một phần tử bằng khoá.

• Sets lưu trữ một nhóm các phần tử không có phần tử nào trùng nhau.
• Lists lưu trữ một tập các phần tử có thứ tự.
• Stacks lưu trữ tập các đối tượng được xử lý theo dạng last-in, first-out.
• Queues lưu trữ tập các đối tượng được xử lý theo dạng first-in, first-out.
• PriorityQueues lưu trữ tập các đối tượng được xử lý theo thứ tự ưu tiên của chúng. 

Các tính năng chung của các collection được định nghĩa trong các interface, và sự thực thi được cung cấp bởi các lớp cụ thể như thể hiện trong hình 20.1

Chú ý Tất cả các interface và các lớp được định nghĩa trong Java Collections Framework được nhóm lại trong package java.util.

Design Guide Thiết kế của Java Collections Framework là một ví dụ tuyệt vời về việc sử dụng các interface, các lớp trừu tượng (abstract class) và các lớp cụ thể (concrete class). Các interface định nghĩa framework. Các lớp trừu tượng cung cấp một phần sự thự thi. Các lớp cụ thể thực thi các interface với cấu trúc dữ liệu cụ thể. Người sử dụng có thể dễ dàng tạo ra một lớp cụ thể bằng cách kế thừa lớp trừu tượng thay vì thực thi tất cả các phương thức trong interface.

interface Collection là interface gốc để thao tác với một tập các đối tượng. Các phương thức public của nó được liệt kê trong hình 20.2. Lớp AbstractCollection cung cấp một phần sự thực thi cho interface Collection. Nó thực thi tất cả các phương thức trong Collection, trừ phương thức add, size và iterator. Những phương thức này được thực hiện phù hợp trong các lớp con cụ thể.

interface Collection cung cấp các thao tác cơ bản để thêm và xóa các phần tử trong collection. Phương thức add thêm một phần tử vào collection. Phương thức addAll thêm tất cả các phần tử trong collection được chỉ định vào collection này. Phương thức remove loại bỏ một phần tử khỏi collection. Phương thức removeAll loại bỏ các phần tử từ collection có trong collection được chỉ định. Phương thức retainAll giữ lại các phần tử trong collection cũng có trong collection được chỉ định. Tất cả các phương thức này trả về boolean. Giá trị trả về là true nếu collection được thay đổi do thực hiện phương thức. Phương thức clear() đơn giản loại bỏ tất cả các phần tử khỏi collection.

Chú ý Các phương thức addAll, removeAll, và retainAll tương tự như thao tác kết hợp (union), hiệu (difference), và sự giao nhau (intersection).

interface Collection cung cấp các thao tác truy vấn khác nhau. Phương thức size trả về số phần tử trong collection. Phương thức contains kiểm tra xem liệu collection chứa phần tử được chỉ định hay không. Phương thức containsAll kiểm tra xem collection có chứa tất cả các phần tử trong collection được chỉ định hay không. Phương thức isEmpty trả về true nếu collection không chứa phần tử nào.

interface Collection cung cấp phương thức toArray() trả về một mảng tham chiếu cho collection

Design Guide

Một số phương thức trong interface Collection không thể được thực hiện trong lớp con cụ thể. Trong trường hợp này, phương thức sẽ ném lỗi .UnsupportedOperationException, đây là lớp con của lớp RuntimeException. Đây là một thiết kế tốt mà bạn có thể sử dụng trong dự án của bạn. Nếu một phương thức không có ý nghĩa trong lớp con, bạn có thể thực thi nó như sau:

public void someMethod() {
throw new UnsupportedOperationException ("Method not supported");
}

import java.util.*;

public class TestCollection {
    public static void main(String[] args){
        ArrayList collection1 = new ArrayList();
        collection1.add("New York");
        collection1.add("Atlanta");
        collection1.add("Dallas");
        collection1.add("Madison");

        System.out.println("A list of cities in collection1:");
        System.out.println(collection1);

        System.out.println("\nIs Dallas in collection1? "
                + collection1.contains("Dallas"));

        collection1.remove("Dallas");
        System.out.println("\n" + collection1.size() +
                " cities are in collection1 now");

        Collection collection2 = new ArrayList<>();
        collection2.add("Seattle");
        collection2.add("Portland");
        collection2.add("Los Angeles");
        collection2.add("Atlanta");

        System.out.println("\nA list of cities in collection2:");
        System.out.println(collection2);

        ArrayList c1 = (ArrayList) collection1.clone();
        c1.addAll(collection2);
        System.out.println("\nCities in collection1 or collection2: ");
        System.out.println(c1);

        c1 = (ArrayList)(collection1.clone());
        c1.retainAll(collection2);
        System.out.print("\nCities in collection1 and collection2: ");
        System.out.println(c1);

        c1 = (ArrayList)(collection1.clone());
        c1.removeAll(collection2);
        System.out.print("\nCities in collection1, but not in 2: ");
        System.out.println(c1);
    }
}

Chương trình tạo ra một đối tượng collection cụ thể sử dụng ArrayList (dòng 5), và gọi phương thức contains của interface Collection (dòng 15), phương thức remove (dòng 17), phương thức size (dòng 18), phương thức addAll (dòng 31), phương thức retainAll (dòng 36), và phương thức removeAll (dòng 41).

Đối với ví dụ này, chúng ta sử dụng ArrayList. Bạn có thể sử dụng bất kỳ lớp cụ thể nào của Collection như HashSet, LinkedList, Vector và Stack thay thế ArrayList để kiểm trả các phương thức này được định nghĩa trong interface Collection.

Chương trình tạo một bản sao của một danh sách các mảng (dòng 30, 35, 40). Mục đích của việc này là giữ lại danh sách mảng ban đầu và sử dụng bản sao của nó để thực hiện các thao tác addAll, retainAll, và removeAll.

Chú ý

Tất cả các lớp cụ thể trong Java Collections Framework thực thi từ interface java.lang.Cloneable và interface java.io.Serializable ngoại trừ java.util.PriorityQueue không thực thi interface Cloneable. Do đó, tất cả các thể hiện của Cloneable ngoại trừ hàng đợi ưu tiên (priority queue) có thể được nhân bản và tất cả các thể hiện của Cloneable có thể là serializable.

Iterators

Mỗi collection là một Iterable. Bạn có thể lấy đối tượng Iterable của nó để duyệt toàn bộ các phần tử trong collection.

Iterator là một mẫu thiết kế cổ điển để duyệt một cấu trúc dữ liệu mà không phải để lộ ra các chi tiết về cách dữ liệu được lưu trong cấu trúc dữ liệu.

interface Collection kế thừa từ interface Iterable. interface Iterable định nghĩa phương thức iterator, trả về một iterator. interface Iterator cung cấp một cách đồng nhất để duyệt qua các phần tử trong các kiểu collection. Phương thức iterator() trong interface Iterable trả về một thể hiện của iterator, như trong hình 20.2, cung cấp truy xuất tuần tự tới các phần tử trong collection sử dụng phương thức next(). Bạn cũng có thể sử dụng phương thức hasNext() để kiểm tra xem có nhiều hơn một phần tử trong iterator, và phương thức remove() để loại bỏ phần tử cuối cùng được trả về bởi iterator.

Listing 20.2 đưa ra một ví dụ về sử dụng iterator để duyệt toàn bộ các phần tử trong ArrayList.

import java.util.*;

public class TestIterator {

    public static void main(String[] args){
        Collection collection = new ArrayList();
        collection.add("New York");
        collection.add("Atlanta");
        collection.add("Dallas");
        collection.add("Madison");

        Iterator iterator = collection.iterator();
        while (iterator.hasNext()) {
            System.out.print(iterator.next().toUpperCase() + " ");
        }
        System.out.println();
    }
}

Chương trình tạo ra một đối tượng collection cụ thể sử dụng ArrayList (dòng 5) và thêm 4 chuỗi vào danh sách (dòng 6-9). Sau đó tạo một Iterator (dòng 11) và sử dụng iterator để duyệt toàn bộ các chuỗi trong danh sách và hiển thị các chuỗi bằng chữa hoa (dòng 12-14)

Tip

Bạn có thể viết lại mã lệnh dòng 11-14 sử dụng vòng lặp như sau:

for (String element: collection)
   System.out.print(element.toUpperCase() + " ");