Bài này mình viết đi sâu vào cấu trúc dữ liệu mà Java triển khai như thế nào.

Collection trong Java là gì?

Collection đại diện cho một đơn vị duy nhất của các đối tượng, tức là một nhóm.

Framework trong Java là gì?

Framework cung cấp một cấu trúc sẵn có của các lớp và giao diện để xây dựng ứng dụng phần mềm một cách hiệu quả. Nó đơn giản hóa việc thêm các tính năng mới bằng cách cung cấp các thành phần có thể tái sử dụng, thực hiện các tác vụ tương tự, loại bỏ nhu cầu phải tạo framework từ đầu cho mỗi dự án mới. Cách tiếp cận này tăng cường thiết kế hướng đối tượng, giúp phát triển nhanh hơn, nhất quán và đáng tin cậy hơn.

• Nó cung cấp các kiến trúc có sẵn
• Đại diện cho một tập hợp các lớp và giao diện.
• Mang tính tùy chọn (có thể sử dụng hoặc không).

Collection framework là gì?

Collection framework đại diện cho một kiến trúc thống nhất để lưu trữ và thao tác trên một nhóm các đối tượng. Nó cải thiện hiệu suất và tính dễ đọc của mã bằng cách cung cấp nhiều cấu trúc dữ liệu khác nhau như mảng (array), danh sách liên kết (linked list), cây (tree), và bảng băm (hash table), được thiết kế phù hợp với các nhu cầu lập trình khác nhau.

1. Interface và các Class implement của nó
2. Algorithm (thuật toán)

Tại sao lại dùng Collection Framework?

Trước khi Collection Framework được giới thiệu trong JDK 1.2, cách tiếp cận của Java đối với Collections sử dụng Arrays, Vectors, và Hash tables thiếu đi một interface chung. Nghĩa là mỗi loại Collection đều có các tập hợp method, cú pháp và hàm khởi tạo riêng, không có sự chuẩn hóa hoặc liên kết giữa chúng.

Điều này khiến người dùng gặp khó khăn trong việc ghi nhớ các chức năng đa dạng của từng loại bộ sưu tập và cản trở tính nhất quán cũng như khả năng tái sử dụng mã. Tính chất rời rạc của các bộ sưu tập này đã làm nổi bật nhu cầu về một Collection Framework thống nhất để đươn giản hóa và chuẩn hóa các thao tác bộ sưu tập trong Java.

Ưu điểm của Java Colllection Framework

Java Collections Framework mang lại những lợi ích đáng kể, cải thiện phương pháp phát triển, chất lượng mã nguồn và hiệu suất ứng dụng:

1. Reusability khả năng tái sử dụng:

Framework cung cấp một tập hợp toàn diện các lớp chung và phương thức tiện ích áp dụng cho nhiều loại bộ sưu tập khác nhau. Tính năng này thúc đẩy khả năng tái sử dụng mã, giúp các nhà phát triển không cần viết lại mã cho các thao tác chung.

2. Quality Chất lượng:

Việc sử dụng Java Collections Framework nâng cao chất lượng của các chương trình. Các thành phần trong framework đã được kiểm tra kỹ lưỡng và được sử dụng rộng rãi bởi cộng đồng lớn các nhà phát triển, đảm bảo tính đáng tin cậy và ổn định cho ứng dụng của bạn.

3. Speed Tốc độ:

Các nhà phát triển thường nhận thấy tốc độ phát triển tăng lên khi sử dụng Collections Framework. Framework này cho phép họ tập trung vào logic nghiệp vụ cốt lõi của ứng dụng thay vì phải triển khai các chức năng chung cho bộ sưu tập, từ đó đẩy nhanh quá trình phát triển.

4. Maintenance Bảo trì:

Tính chất mã nguồn mở của Java Collections Framework, kết hợp với tài liệu API sẵn có, giúp việc bảo trì mã trở nên dễ dàng hơn. Mã được viết bằng framework này có thể dễ dàng được hiểu và tiếp quản bởi các nhà phát triển khác, đảm bảo tính liên tục và thuận tiện trong việc bảo trì.

5. Reduces Effort to Design New APIs Giảm nỗ lực thiết kế API mới:

Một lợi ích bổ sung là giảm thiểu sự cần thiết đối với các nhà thiết kế và triển khai API phải tạo ra cơ chế bộ sưu tập mới cho mỗi API mới. Thay vào đó, họ có thể dựa vào các interface bộ sưu tập chuẩn được cung cấp bởi framework, giúp đơn giản hóa quá trình phát triển API và đảm bảo tính nhất quán giữa các ứng dụng Java.

Hierarchy of Collection Framework - Hệ thống cấp bậc

Package java.util chứ tất cả các class và interface cho Collection framework

Java Collections Framework được cấu trúc xung quanh các interface chính: Collection, List, Set, Queue, và Map

Class: là một bản thiết kế từ đó các đối tượng riêng lẻ được tạo ra. Nó đóng gói dữ liệu cho các đối tượng thông qua fields (attributes) và định nghĩa các hành vi thông qua methods. Class hỗ trợ kế thừa, cho phép 1 lớp kế thừa các thuộc tính và phương thức của lớp khác, giúp tái sử dụng mã và tính đã hình.

Interface: là một kiểu tham chiếu trong Java có thể chứa các hằng số và các phương thức trừu tượng (phương thức không có phần thân). Interface xác định những gì một lớp phải thực hiện nhưng không chỉ ra cách thực hiện, qua đó bắt buộc lớp phải triển khai các phương thức được định nghĩa. Interface được sử dụng để đạt được tính trừu tượng và hỗ trợ đa kế thừa trong Java.

Các method trong Collection interface

size, isEmpty, contains, iterator, toArray, add, remove, containsAlll, addAll, removeAll, removeIf, retainAll, clear, equals, hashCode, spliterator, stream, parallelStream

Các bạn có thể tìm hiểu thêm ý nghĩa về từng method này trong các class implement nhé.

Iterator interface

Cung cấp khả năng duyệt qua các phần tử theo một chiều duy nhất.

Methods:

• hashNext: kiểm tra xem có phần tử để duyệt tiếp hay không?
• next: trả về phần tử tiếp theo,
• remove: xóa phần tử cuối cùng mà next trả về

Một số lưu ý chung:

• Không đồng bộ: Nếu tập hợp bị sửa đổi bởi một thread khác trong khi đang duyệt qua bằng Iterator, nó sẽ gây ra ConcurrentModificationException.
• Không hỗ trợ lùi (backward traversal): Iterator chỉ hỗ trợ duyệt về phía trước. Để duyệt ngược, có thể dùng ListIterator.

Iterable Interface

Là Interface gốc cho tất cả các Collection class. Collection interface extends Iterable interface, do đó tất cả các lớp con của Collection cũng triển khai Iterable

Iterator<T> iterator()  

Trả về một iterator duyệt qua các phần tử thuộc kiểu T

Collection Interface

Collection Interface là interface mà tất cả các lớp trong Collection framework triển khai. Nó khai báo các phương thức mà mọi bộ sưu tập sẽ có. Nói cách khác, chúng ta có thể nói rằng Collection interface xây dựng nền tảng mà Collection framework phụ thuộc vào.

Một số phương thức của Collection interface bao gồm Boolean add(Object obj), Boolean addAll(Collection c), void clear(), v.v., và những phương thức này được triển khai bởi tất cả các lớp con của Collection interface.

List Interface

List interface là child interface của Collection interface. Nó biểu thị một cấu trúc dữ liệu kiểu danh sách, trong đó chúng ta có thể lưu trữ bộ sưu tập các đối tượng theo thứ tự. Nó có thể chứa các giá trị trùng lặp

List interface được triển khai bởi các lớp ArrrayList, LinkedList, Vector và Stack Để khởi tạo interface List, chúng ta phải sử dụng:

List <data-type> list1 = new ArrayList();  
List <data-type> list2 = new LinkedList();  
List <data-type> list3 = new Vector();  
List <data-type> list4 = new Stack();

Sử dụng kiểu List nhưng khai báo kiểu class implement List (Keyword: upcasting, downcasting có thể tìm hiểu thêm)

Có nhiều phương thức trong interface List có thể được sử dụng để chèn, xóa và truy cập các phần tử trong danh sách.

Các lớp triển khai interface List bao gồm:

ArrayList

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable  

Lớp ArrayList implements giao diện List. Nó sử dụng mảng động để lưu trữ các phần tử. ArrayList cho phép lưu trữ các phần tử trùng lặp và hỗ trợ các kiểu dữ liệu khác nhau thông qua tính năng generics (1 khi xác định kiểu thì tất cả các element phải tuân theo). Lớp này duy trì thứ tự chèn các phần tử và không đồng bộ. Tuy nhiên, các phần tử trong ArrayList có thể được truy cập ngẫu nhiên (random access) nhờ vào chỉ số (index).

truy cập ngẫu nhiên: ám chỉ việc truy cập trực tiếp vào phần tử thông qua chỉ số (index) mà không cần duyệt qua các phần tử khác.

Thời gian hằng số O(1) khi dùng lệnh arrayList.get(i)

Các điểm quan trọng:

• Duy trì thứ tự chèn
• Không đồng bộ
• Hỗ trợ truy cập ngẫu nhiên
• Chậm hơn so với LinkedList trong các thao tác chỉnh sửa (chèn, xóa)

Vì khi thêm hoặc xóa phần tử không phải ở cuối danh sách, ArrayList cần dịch chuyển các phần tử còn lại đểm đảm bảo thứ tự danh sách.

• Yêu cầu lớp bao bọc cho các kiểu nguyên thủy

ArrayList không hỗ trợ trực tiếp các kiểu dữ liệu nguyên thủy như int, float, và char. Thay vào đó, nó yêu cầu các lớp bao bọc như Integer, Float, Character, v.v... để lưu trữ các kiểu nguyên thủy này.

Hiện tại thường các dự án sử dụng Java 11 trở lên nên việc sử dụng Java Collection Framework trở nên an toàn và thuận tiện hơn khi có Generics (có từ Java 5) - có thể tìm hiểu thêm.

ArrayList<String> list = new ArrayList<String>(); //creating new generic arraylist  

Serialization

Quá trình chuyển đổi một đối tượng Java thành một chuỗi byte để lưu trữ hoặc truyền qua mạng Deserialization là quá trình ngược lại, chuyển đổi byte thành đối tượng Java.

Khi làm việc với ArrayList, bạn có thể tuần tự hóa nó (serialize) nếu lớp ArrayList và các đối tượng bên trong nó đều thực thi giao diện Serializable

import java.io.*;
import java.util.ArrayList;

public class ArrayListSerializationExample {
    public static void main(String[] args) {
        // Tạo một ArrayList và thêm các phần tử
        // Nếu một trong các đối tượng bên trong ArrayList không thực thi Serializable, bạn sẽ gặp lỗi NotSerializableException.
        ArrayList<String> list = new ArrayList<>();
        list.add("Java");
        list.add("Python");
        list.add("C++");

        // Đường dẫn file để lưu dữ liệu
        String filename = "arraylist.ser"; // File .ser là file nhị phân, không đọc được trực tiếp. Để xem nội dung, bạn phải deserialization.

        // Serialization (Ghi ArrayList ra file)
        try (FileOutputStream fileOut = new FileOutputStream(filename);
             ObjectOutputStream out = new ObjectOutputStream(fileOut)) {
            out.writeObject(list);
            System.out.println("Serialization thành công. Dữ liệu đã được lưu vào file: " + filename);
        } catch (IOException e) {
            e.printStackTrace();
        }

        // Deserialization (Đọc ArrayList từ file)
        ArrayList<String> deserializedList = null;
        try (FileInputStream fileIn = new FileInputStream(filename);
             ObjectInputStream in = new ObjectInputStream(fileIn)) {
            deserializedList = (ArrayList<String>) in.readObject();
            System.out.println("Deserialization thành công. Dữ liệu đã được đọc từ file.");
        } catch (IOException | ClassNotFoundException e) {
            e.printStackTrace();
        }

        // Hiển thị dữ liệu sau khi deserialization
        if (deserializedList != null) {
            System.out.println("Dữ liệu trong ArrayList sau deserialization: " + deserializedList);
        }
    }
}

Size and Capacity of an ArrayList

Kích thước (size) và dung lượng (capacity) của một ArrayList là hai thuật ngữ thường gây nhầm lẫn cho người mới bắt đầu. ArrayList xử lý kích thước biến đổi của các phần tử bằng cách thêm hoặc xóa phần tử, làm cho nó linh hoạt khi làm việc với các tập hợp. Độ dài (length) của một ArrayList đề cập đến số lượng phần tử được lưu trữ trong đó, có thể lấy được bằng cách gọi phương thức size(). Kích thước này được điều chỉnh tự động khi các phần tử được thêm hoặc xóa.

Nếu kích thước vượt quá cap được cấp sẽ tạo newCap 
int newCapacity = oldCapacity + (oldCapacity >> 1);

Tùy phiên bản JDK mà triển khai nhưng hầu như là 1.5

Dung lượng (capacity) của một ArrayList là số lượng tối đa các phần tử mà nó có thể chứa trước khi cần thay đổi kích thước. Ban đầu, dung lượng của một ArrayList được xác định bởi hàm tạo (constructor) được sử dụng để tạo nó hoặc bởi dung lượng mặc định nếu không có hàm tạo nào được định nghĩa. Khi tổng số phần tử trong ArrayList vượt quá dung lượng hiện tại, ArrayList sẽ tự động cấp phát lại và tăng dung lượng để chứa thêm phần tử, giúp lưu trữ hiệu quả và giảm thiểu sự lãng phí. Dung lượng của ArrayList có thể được lấy bằng cách sử dụng phương thức capacity().

private static final int DEFAULT_CAPACITY = 10;

ArrayList<Integer> al = new ArrayList<Integer>(10);

Nói dễ hiểu thì nếu bạn khởi tạo giá trị ban đầu cho ArrayList thì nó như cái hộp với kích thước khởi tạo. Size chính là các phần tử ở trong cái hộp đó. Nếu k có phần tử nào thì size = 0, còn cap sẽ là dung tích cái hộp có thể chứa.

LinkedList

LinkedList triển khai giao diện Collection (LinkedList implements the Collection interface). Nó sử dụng danh sách liên kết đôi (doubly linked list) bên trong để lưu trữ các phần tử. LinkedList có thể lưu trữ các phần tử trùng lặp. Nó duy trì thứ tự chèn và không được đồng bộ hóa (not synchronized). Trong LinkedList thao tác (thêm, xóa, sửa) nhanh hơn vì không cần thực hiện việc dịch chuyển các phần tử.

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

private static class Node<E> {
    E item;
    Node<E> next;
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

Vector

Vector sử dụng một mảng động để lưu trữ các phần tử dữ liệu. Nó tương tự như ArrayList. Tuy nhiên, Vector được đồng bộ hóa (synchronized) và chứ nhiều phương thức không thuộc về framework Collection.

public class Vector<E>
    extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable

Synchronized trong Java là một cơ chế để đảm bảo rằng chỉ một luồng (thread) được phép truy cập vào một tài nguyên nhất định tại một thời điểm. Nó giúp tránh race condition và đảm bảo tính nhất quán dữ liệu khi có nhiều luồng truy cập đồng thời.

Có những cách sau để đặt từ khóa synchronized:

1. Synchronized Method

Đồng bộ hóa toàn bộ một phương thức. Cách hoạt động:

• Nếu phương thức không static, khóa (lock) sẽ được đặt trên đối tượng instance
• Nếu là phương thức static, khóa sẽ được đặt trên class-level object (ClassName.class)

class Counter {
    private int count = 0;

    public synchronized void increment() { // Instance lock
        count++;
        System.out.println(Thread.currentThread().getName() + " tăng count: " + count);
    }

    public static synchronized void staticIncrement() { // Class lock
        System.out.println(Thread.currentThread().getName() + " gọi static method");
    }
}

public class Main {
    public static void main(String[] args) {
        Counter counter = new Counter();

        Thread t1 = new Thread(counter::increment, "Thread-1");
        Thread t2 = new Thread(counter::increment, "Thread-2");

        t1.start();
        t2.start();
    }
}

// Output:
Thread-1 tăng count: 1
Thread-2 tăng count: 2

2. Synchronized Block

Chỉ đồng bộ hóa một khối mã trong phương thức, thay vì toàn bộ phương thức. Cách hoạt động:

• Khóa có thể đặt trên this, một đối tượng cụ thể, hoặc class-level object (ClassName.class).

class Counter {
    private int count = 0;

    public void increment() {
        synchronized (this) { // Instance lock
            count++;
            System.out.println(Thread.currentThread().getName() + " tăng count: " + count);
        }
    }

    public void printCount() {
        System.out.println("Giá trị hiện tại: " + count);
    }
}

3. Static Synchronized Block

Đồng bộ hóa một khối mã tĩnh bằng cách đặt khóa trên ClassName.class.

class Counter {
    public static void staticMethod() {
        synchronized (Counter.class) { // Class lock
            System.out.println(Thread.currentThread().getName() + " đang thực thi staticMethod");
            try {
                Thread.sleep(1000);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }
}

4. Sử dụng Object Lock (Custom Lock Object)

Thay vì đồng bộ hóa trên this hoặc ClassName.class, bạn có thể sử dụng một đối tượng khóa tùy chỉnh.

class Counter {
    private int count = 0;
    private final Object lock = new Object();

    public void increment() {
        synchronized (lock) { // Custom lock object
            count++;
            System.out.println(Thread.currentThread().getName() + " tăng count: " + count);
        }
    }
}

Stack

Stack là một lớp con của Vector. Nó triển khai cấu trúc dữ liệu vào sau-ra trước (last-in-first-out), tức là Stack. Stack chứa tất cả các phương thức của lớp Vector và cũng cung cấp các phương thức riêng như boolean push(), boolean peek(), boolean push(object o), giúp xác định các đặc điểm của nó.

public class Stack<E> extends Vector<E>

.push(E item)
.pop // Lấy và loại bỏ phần tử ở đỉnh của stack. Nếu stack rỗng, phương thức này ném ra EmptyStackException.
.peek() // Lấy phần tử ở đỉnh mà không loại bỏ nó. Nếu stack rỗng, phương thức này ném ra EmptyStackException
.empty()
.search(Object o) // Tìm kiếm phần tử trong stack và trả về vị trí của nó tính từ đỉnh stack (vị trí bắt đầu từ 1). Nếu không tìm thấy, trả về -1.

Queue Interface

Giao diện Queue duy trì thứ tự vào trước-ra trước (first-in-first-out). Nó có thể được định nghĩa là một danh sách có thứ tự được sử dụng để lưu trữ các phần tử chuẩn bị được xử lý. Có nhiều lớp như PriorityQueue, Deque và ArrayDeque triển khai giao diện Queue.

public interface Queue<E> extends Collection<E>

Queue<String> q1 = new PriorityQueue();  
Queue<String> q2 = new ArrayDeque();

.offer(E e)
.poll()
.peek()
.remove()
.isEmpty()
.size()
.contains(Object o)

PriorityQueue

Lớp PriorityQueue triển khai giao diện Queue. Nó lưu trữ các phần tử hoặc đối tượng được xử lý dựa trên độ ưu tiên của chúng. PriorityQueue không cho phép lưu trữ các giá trị null trong hàng đợi.

public class PriorityQueue<E> extends AbstractQueue<E>
    implements java.io.Serializable

Deque Interface

Deque (Double Ended Queue) là một giao diện mở rộng từ giao diện Queue. Trong Deque, chúng ta có thể thêm và xóa các phần tử từ cả hai đầu. Deque là viết tắt của hàng đợi hai đầu, cho phép thực hiện các thao tác ở cả hai đầu của hàng đợi.

public interface Deque<E> extends Queue<E>

Deque d = new ArrayDeque();  

ArrayDeque

Lớp ArrayDeque triển khai giao diện Deque, giúp chúng ta sử dụng Deque một cách hiệu quả. Khác với Queue, chúng ta có thể thêm hoặc xóa các phần tử từ cả hai đầu.

ArrayDeque nhanh hơn ArrayList và Stack, đồng thời không bị giới hạn về dung lượng.

public class ArrayDeque<E> extends AbstractCollection<E>
                           implements Deque<E>, Cloneable, Serializable

Set Interface

Giao diện Set trong Java nằm trong gói java.util. Nó mở rộng giao diện Collection. Set đại diện cho một tập hợp các phần tử không có thứ tự và không cho phép lưu trữ các phần tử trùng lặp. Trong Set, chúng ta có thể lưu trữ tối đa một giá trị null. Set được triển khai bởi các lớp như HashSet, LinkedHashSet và TreeSet.

public interface Set<E> extends Collection<E>

Set<data-type> s1 = new HashSet<data-type>();  
Set<data-type> s2 = new LinkedHashSet<data-type>();  
Set<data-type> s3 = new TreeSet<data-type>();  

HashSet

Lớp HashSet triển khai giao diện Set. Nó đại diện cho một tập hợp sử dụng bảng băm (hash table) để lưu trữ. Hashing được sử dụng để lưu các phần tử trong HashSet, đảm bảo rằng các phần tử trong đó là duy nhất.

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable

LinkedHashSet

Lớp LinkedHashSet đại diện cho việc triển khai LinkedList của giao diện Set. Nó kế thừa từ lớp HashSet và triển khai giao diện Set. Giống như HashSet, LinkedHashSet cũng chỉ chứa các phần tử duy nhất. Ngoài ra, nó duy trì thứ tự chèn và cho phép chứa các phần tử null.

public class LinkedHashSet<E>
    extends HashSet<E>
    implements Set<E>, Cloneable, java.io.Serializable

SortedSet Interface

SortedSet là một giao diện thay thế cho Set, cung cấp thứ tự tổng thể cho các phần tử của nó. Các phần tử trong SortedSet được sắp xếp theo thứ tự tăng dần (ascending order). SortedSet cung cấp các phương thức bổ sung để duy trì thứ tự tự nhiên của các phần tử.

public interface SortedSet<E> extends Set<E>

SortedSet<data-type> set = new TreeSet();  

TreeSet

Lớp TreeSet trong Java triển khai giao diện Set và sử dụng cây để lưu trữ. Giống như HashSet, TreeSet cũng chỉ chứa các phần tử duy nhất. Tuy nhiên, thời gian truy cập và lấy dữ liệu của TreeSet khá nhanh. Các phần tử trong TreeSet được lưu trữ theo thứ tự tăng dần.

public class TreeSet<E> extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable

Map Interface

Giao diện Map trong Java là một phần của Java Collections Framework. Nó đại diện cho một ánh xạ giữa một tập hợp các khóa và các giá trị tương ứng của chúng. Một Map không thể chứa các khóa trùng lặp; mỗi khóa chỉ có thể ánh xạ đến tối đa một giá trị. Giao diện Map được sử dụng để lưu trữ các cặp khóa-giá trị, trong đó mỗi khóa là duy nhất, và cung cấp một cách hiệu quả để truy xuất, cập nhật và thao tác dữ liệu dựa trên các khóa.

public interface Map<K, V>

If the map contains more than Integer.MAX_VALUE elements, returns Integer.MAX_VALUE.

Map<T, T> hm = new HashMap<>();   
Map<T, T> tm = new TreeMap<>();  

HashMap

HashMap trong Java là một cấu trúc dữ liệu khóa-giá trị, cung cấp khả năng truy xuất dữ liệu hiệu quả thông qua khóa bằng cách sử dụng hashing. Hashing chuyển đổi các chuỗi lớn hoặc các đối tượng khác thành các giá trị nhỏ hơn và đồng nhất để truy xuất và tìm kiếm nhanh chóng. HashMap triển khai giao diện Map và được sử dụng để quản lý các tập dữ liệu lớn một cách hiệu quả. Ngoài ra, HashSet sử dụng HashMap bên trong để lưu trữ các phần tử một cách duy nhất, chứng minh tính hữu ích của hashing trong Java Collections Framework cho việc truy xuất và quản lý dữ liệu nhanh chóng.

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable