Tổng quan về Collections trong Java

Collections là gì? Giới thiệu Java Collection Framework

Collections trong Java là các class và interface dùng để lưu trữ và quản lý nhóm các phần tử dưới dạng một cấu trúc dữ liệu duy nhất. Chúng cho phép bạn thao tác với các nhóm đối tượng một cách dễ dàng và hiệu quả, giúp quản lý dữ liệu một cách có tổ chức và linh hoạt. Mục đích chính của Collections là:

Giúp quản lý và xử lý dữ liệu một cách có cấu trúc và tổ chức.
Cung cấp các phương thức để thêm, xóa, duyệt và thao tác với các phần tử một cách dễ dàng và hiệu quả.
Tăng khả năng tái sử dụng của mã nguồn.

Java Collection Framework bao gồm: Java Collection Framework là một tập hợp các interface và classes được thiết kế để xử lý các nhóm đối tượng. Nó bao gồm:

Interfaces: Định nghĩa các loại collections khác nhau như List, Set, Queue, và Map.
Classes: Các class cụ thể triển khai các inteface như ArrayList, LinkedList, HashSet, TreeSet, HashMap, TreeMap.
Algorithms: Là thuật toán đề cập đến các phương thức được sử dụng để thực hiện các hoạt động như tìm kiếm và sắp xếp trên đối tượng triển khai của Collection Interface.

Hình mô tả sự liên kết của Interfaces, Classes và Algorithm - Nguồn: JanBask Traning

Các loại Java Collections cơ bản

Có 2 loại cơ bản của Java Collections:

Iterable Interface: Giống như tên gọi thì Interable Interface được sử dụng để quản lý các phần tử trong một danh sách và có thể lặp qua được(sử dụng for, map….). Các class được triển khai từ Collection Interface là List, Set, và Queue.
Map Interface: Map Interface tạo ra ánh xạ giữa các cặp key value. Nó hỗ trợ các tính năng như lưu trữ, truy xuất, xóa và tìm kiếm các phần tử theo key. Ví dụ như thông tin của một Object, hoặc dùng để get các config tương ưng với key mà chúng ta đã set…. TreeMap và HashMap là các class được triển khai từ Map Interface.

List trong Java

List là một danh sách có thứ tự, cho phép các phần tử trùng lặp. Vì List là một Interface nên chúng ta không thể tạo các đối tượng từ nó, chỉ có thể sử dụng được các phương thức đã được thiết kế sẵn như: map, filter, get. Để sử dụng các tính năng của List Interface, chúng ta có thể sử dụng các class sau:

ArrayList
LinkedList
Vector

ArrayList

Các phần tử trong ArrayList có thể được truy cập và thay đổi một cách dễ dàng bằng cách sử dụng index. Và có khả năng tự động mở rộng kích thước, điều này giúp cho việc thêm hoặc xóa phần tử khỏi danh sách trở nên linh hoạt hơn.

Ưu điểm: Truy cập ngẫu nhiên nhanh: Vì ArrayList sử dụng mảng bên dưới, việc truy cập phần tử theo chỉ số rất nhanh. Thêm phần tử vào cuối danh sách nhanh: Thời gian truy cập là O(1) trừ khi mảng cần được tăng kích thước. Nhược điểm: Chèn và xóa phần tử chậm: Đặc biệt là khi thêm hoặc xóa phần tử ở giữa danh sách vì cần di chuyển các phần tử khác. Tiêu tốn nhiều bộ nhớ hơn LinkedList: Vì cần dự trữ dung lượng cho việc tăng kích thước.

1
2
3


List<String> arrayList = new ArrayList<>();
arrayList.add("Apple");
arrayList.add("Banana");

LinkedList

LinkedList là một cấu trúc dữ liệu mà trong đó các phần tử được liên kết với nhau thông qua các địa chỉ bộ nhớ, do đó không cần phải cấp phát toàn bộ một khối bộ nhớ liên tục cho dữ liệu. Các phần tử có thể được chèn hoặc xóa bất kỳ lúc nào.

Ưu điểm: Chèn và xóa phần tử nhanh: Đặc biệt là khi thêm hoặc xóa phần tử ở đầu hoặc giữa danh sách. Sử dụng bộ nhớ hiệu quả hơn khi liên tục thêm hoặc xóa phần tử.

Nhược điểm: Truy cập phần tử chậm: Vì cần duyệt qua các phần tử theo thứ tự. Tiêu tốn thêm bộ nhớ cho các tham chiếu của các node.

1
2
3


List<String> linkedList = new LinkedList<>();
linkedList.add("Apple");
linkedList.add("Banana");

Set trong Java

Set lưu trữ các phần tử không trùng lặp và không có thứ tự cụ thể. Khi thêm một phần tử vào Set, nếu phần tử ấy đã tồn tại trong Set rồi thì nó sẽ không được thêm vào và không có tác động gì đến Set ban đầu.

HashSet

HashSet được sử dụng để lưu trữ các phần tử không có thứ tự, vì vậy không có cách nào để truy xuất các phần tử theo thứ tự cụ thể. HashSet kế thừa những đặc điểm của Set, điển hình là chỉ chứa các phần tử duy nhất. Nếu chúng ta thêm một phần tử đã có trong HashSet thì phần tử đó sẽ bị bỏ qua.

Ưu điểm: Thao tác thêm, xóa và kiểm tra phần tử nhanh: Do sử dụng bảng băm (hash table) bên dưới. Không cho phép các phần tử trùng lặp.

Nhược điểm: Không duy trì thứ tự của các phần tử. Hiệu suất có thể giảm khi xảy ra nhiều va chạm băm.
HashSet không được đồng bộ hóa tự động. Điều này có nghĩa rằng nếu ta muốn sử dụng HashSet trong môi trường đa luồng, chúng ta cần phải tự đồng bộ hóa bằng cách sử dụng Collections.synchronizedSet() hoặc sử dụng ConcurrentHashMap thay vì HashSet.
HashSet không cung cấp các phương thức để truy cập phần tử dựa trên index vì nó không duy trì thứ tự. Điều này làm cho việc truy cập ngẫu nhiên các phần tử không khả thi và ta cần phải sử dụng một vòng lặp hoặc phương thức contains() để kiểm tra sự tồn tại của một phần tử.

1
2
3


Set<String> hashSet = new HashSet<>();
hashSet.add("Apple");
hashSet.add("Banana");

LinkedHashSet

LinkedHashSet implement Set Interface trong Java, tương tự như HashSet, tuy nhiên có hỗ trợ duy trì thứ tự của các phần tử được thêm vào danh sách.

Ưu điểm: Duy trì thứ tự được thêm vào danh sách là một trong những ưu điểm quan trọng của LinkedHashSet. Điều này có nghĩa rằng khi ta duyệt qua LinkedHashSet, phần tử được thêm vào trước sẽ được trả ra trước và phần tử được thêm vào sau sẽ được trả ra sau, hữu ích trong các tình huống khi chúng ta quan tâm đến thứ tự dữ liệu. LinkedHashSet vẫn giữ lại tốc độ truy cập nhanh của HashSet. Chúng ta có thể thêm, xóa và kiểm tra sự tồn tại của phần tử trong thời gian gần như là hằng số.

Nhược điểm: Tốn bộ nhớ hơn HashSet: LinkedHashSet sử dụng thêm một con trỏ (hoặc một đối tượng Entry) cho mỗi phần tử để duy trì thứ tự chèn. Điều này làm tăng bộ nhớ so với HashSet, đặc biệt khi danh sách chúng ta ngày càng lớn.
Không thích hợp cho các yêu cầu đòi hỏi hiệu suất cao: Trong các tình huống đòi hỏi hiệu suất cao như khi ta cần thực hiện các thao tác thêm/xóa/sửa trên danh sách một cách nhanh chóng, ta có thể cân nhắc các cấu trúc dữ liệu khác như HashMap hoặc ArrayList được tối ưu hóa hơn.

1
2
3
4
5
6
7
8


// Create a LinkedHashSet
LinkedHashSet<String> linkedHashSet = new LinkedHashSet<>();

// Adding elements to the LinkedHashSet
linkedHashSet.add("Apple");
linkedHashSet.add("Banana");
linkedHashSet.add("Cherry");
linkedHashSet.add("Date");

Queue trong Java

Queue là một thành phần của Collections trong Java, được sử dụng để lưu trữ và quản lý các phần tử theo thứ tự First in, First out (FIFO). Các phần tử mới sẽ được thêm vào cuối hàng đợi và phần tử cũ sẽ được xóa khỏi đầu hàng đợi.

Các phương thức chính của Queue bao gồm:

add(): Thêm một phần tử vào cuối hàng đợi.
remove(): Xóa phần tử đầu tiên trong hàng đợi.
peek(): Truy cập phần tử đầu tiên trong hàng đợi mà không xóa nó ra khỏi hàng đợi.
poll(): Lấy và xóa phần tử đầu tiên ra khỏi hàng đợi.

ArrayDeque

ArrayDeque là một cấu trúc dữ liệu đặc biệt cho phép chúng ta có thể thêm hoặc một phần tử từ cả hai phía. Chúng ta có thể sử dụng nó như là Stack(Last-In-First-Out) hoặc là Queue(First-In-First-Out).

Ưu điểm: Hiệu suất cao: ArrayDeque cung cấp các thao tác thêm, xóa, và truy cập phần tử ở đầu và cuối hàng đợi với thời gian trung bình O(1).
Không giới hạn kích thước: Kích thước của ArrayDeque tự động tăng lên khi cần thiết.
Không đồng bộ: Không có đồng bộ hóa nội bộ, dẫn đến hiệu suất tốt hơn khi sử dụng trong môi trường đơn luồng.
Nhược điểm: Không hỗ trợ đồng bộ: Không thích hợp cho các ứng dụng đa luồng mà cần sự đồng bộ.
Không cho phép phần tử null: ArrayDeque không chấp nhận giá trị null, điều này có thể hạn chế trong một số trường hợp.

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


import java.util.ArrayDeque;
import java.util.Deque;

public class ArrayDequeExample {
    public static void main(String[] args) {
        Deque<String> deque = new ArrayDeque<>();

        // Thêm phần tử vào đầu và cuối của deque
        deque.addFirst("A");
        deque.addLast("B");
        deque.addFirst("C");

        // Hiển thị các phần tử của deque
        System.out.println("Các phần tử trong deque: " + deque);

        // Lấy và xóa phần tử ở đầu và cuối deque
        System.out.println("Lấy phần tử đầu tiên: " + deque.removeFirst());
        System.out.println("Lấy phần tử cuối cùng: " + deque.removeLast());

        // Hiển thị các phần tử còn lại trong deque
        System.out.println("Các phần tử còn lại trong deque: " + deque);
    }
}

PriorityQueue

PriorityQueue cung cấp một hàng đợi ưu tiên. Các phần tử trong PriorityQueue được tự động sắp xếp dựa trên thứ tự tự nhiên của chúng hoặc dựa trên một Comparator được cung cấp khi tạo hàng đợi.

Ưu điểm: Sắp xếp tự động: PriorityQueue tự động sắp xếp các phần tử theo thứ tự tự nhiên hoặc theo Comparator.

Nhược điểm: Không đồng bộ: PriorityQueue không hỗ trợ đồng bộ hóa nội bộ, không an toàn trong môi trường đa luồng.
Không hỗ trợ phần tử null: PriorityQueue không chấp nhận giá trị null.
Không cho phép truy cập ngẫu nhiên: Bạn không thể truy cập trực tiếp phần tử ở vị trí cụ thể trong hàng đợ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
29
30
31
32
33
34
35
36
37
38
39


mport java.util.PriorityQueue;

class Task implements Comparable<Task> {
    private String name;
    private int priority;

    public Task(String name, int priority) {
        this.name = name;
        this.priority = priority;
    }

    public String getName() {
        return name;
    }

    @Override
    public int compareTo(Task other) {
        return Integer.compare(other.priority, this.priority); // Sắp xếp giảm dần theo độ ưu tiên
    }
}

public class PriorityQueueExample {
    public static void main(String[] args) {
        PriorityQueue<Task> taskQueue = new PriorityQueue<>();

        taskQueue.add(new Task("Task 1", 3));
        taskQueue.add(new Task("Task 2", 1));
        taskQueue.add(new Task("Task 3", 2));

        while (!taskQueue.isEmpty()) {
            System.out.println("Processing " + taskQueue.poll());
        }
    }
}

// expect result
Processing Task 1 (Priority: 3)
Processing Task 3 (Priority: 2)
Processing Task 2 (Priority: 1)

Map trong Java

Map là một trong những cấu trúc dữ liệu quan trọng trong lập trình Java. Nó được sử dụng để biểu diễn một tập hợp các phần tử theo cặp key-value, trong đó key là giá trị duy nhất và value là giá trị tương ứng với key.

Sử dụng Map có thể giúp rất nhiều trong việc lưu trữ và truy xuất dữ liệu trong ứng dụng Java.

Cách tố chức dữ liệu trong Map - Nguồn: scientecheasy

HashMap

HashMap là một class được sử dụng để lưu trữ các đối tượng theo cặp key-value. Điều này giúp cho việc truy cập và tìm kiếm các phần tử trong HashMap trở nên nhanh chóng và hiệu quả.

Ưu điểm:
Thao tác thêm, xóa và truy cập nhanh: Vì sử dụng bảng băm (hash table) bên dưới.
Cho phép một khóa null và nhiều giá trị null.
Phù hợp cho các bài toán có nhiều truy vấn và thao tác trên dữ liệu.

Nhược điểm: Không giữ thứ tự của các phần tử, vì vậy nó không phù hợp cho các tác vụ yêu cầu giữ thứ tự.
HashMap không cho phép chúng ta thêm các key trùng lặp. Nếu bạn thêm một cặp key-value với key đã tồn tại trong HashMap, nó sẽ ghi đè giá trị cũ.

1
2
3


Map<String, String> hashMap = new HashMap<>();
hashMap.put("Apple", "Red");
hashMap.put("Banana", "Yellow");

LinkedHashMap

LinkedHashMap là một class con của HashMap trong Java. Nó kế thừa tất cả tính năng của HashMap và bổ sung thêm các đặc điểm mới. Mở rộng từ HashMap và giữ nguyên thứ tự chèn của các phần tử.

Ưu Điểm:
Duy Trì Thứ Tự Chèn: LinkedHashMap lưu trữ các phần tử theo thứ tự chèn, giúp dễ dàng duyệt qua các phần tử theo thứ tự chèn vào.
Dễ Dàng Duyệt Qua: Có thể duyệt qua các phần tử theo thứ tự chèn hoặc theo thứ tự truy cập gần nhất khi bật chế độ truy cập.

Nhược Điểm: Không thích hợp cho việc sắp xếp theo key: Nếu yêu cầu cần sắp xếp LinkedHashMap dựa trên key hoặc value, chúng ta sẽ cần phải thực hiện thêm công việc để tự sắp xếp dữ liệu. LinkedHashMap không cung cấp sắp xếp tự động theo các tiêu chí này. Chậm Hơn HashMap: Do duy trì thứ tự chèn, LinkedHashMap có thể chậm hơn HashMap một chút trong một số thao tác.

LinkedHashMap là một cấu trúc dữ liệu phù hợp cho các tác vụ cần giữ nguyên thứ tự chèn và thao tác tra cứu nhanh nhưng cần xem xét các ưu điểm và nhược điểm trước khi sử dụng nó trong dự án.

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


import java.util.LinkedHashMap;
import java.util.Map;

// Tạo một LinkedHashMap
LinkedHashMap<Integer, String> linkedHashMap = new LinkedHashMap<>();

// Thêm các phần tử vào LinkedHashMap
linkedHashMap.put(1, "One");
linkedHashMap.put(2, "Two");
linkedHashMap.put(3, "Three");

// Duyệt qua các phần tử theo thứ tự chèn
for (Map.Entry<Integer, String> entry : linkedHashMap.entrySet()) {
    System.out.println(entry.getKey() + " => " + entry.getValue());
}

Các thuật toán cơ bản của Collections Java

Java Collections Framework cung cấp một số thuật toán cơ bản để thực hiện các thao tác trên các cấu trúc dữ liệu. Các thuật toán này nằm trong lớp Collections và có thể áp dụng cho các loại collection như List, Set, Map. Dưới đây là một số thuật toán phổ biến và ví dụ minh họa cách sử dụng chúng.

Sắp Xếp (Sorting)

Thuật toán sắp xếp giúp sắp xếp các phần tử trong danh sách theo thứ tự tự nhiên hoặc theo một Comparator tùy chỉnh.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


import java.util.*;

List<String> list = new ArrayList<>(Arrays.asList("Banana", "Apple", "Mango", "Cherry"));

// Sắp xếp theo thứ tự tự nhiên
Collections.sort(list);
System.out.println("Sorted list: " + list);

// Sắp xếp theo thứ tự tùy chỉnh
Collections.sort(list, Comparator.reverseOrder());
System.out.println("Reverse sorted list: " + list);

Trộn (Shuffling)

Thuật toán trộn thay đổi vị trí các phần tử trong danh sách một cách ngẫu nhiên.

1
2
3
4
5
6


import java.util.*;

List<Integer> list = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5));

Collections.shuffle(list);
System.out.println("Shuffled list: " + list);

Tìm Kiếm (Searching)

Tìm kiếm là một trong những chức năng quan trọng của Java Collections Framework. Được thực hiện thông qua các phương thức tìm kiếm được cung cấp bởi các class collection như List và Map. Có những phương thức khác giúp hỗ trợ trong việc tìm kiếm theo những tiêu chí khác nhau:

contains(Object o)
find(Object o)
findIndexOf(List<? extends Comparable<? super T» list, T key)
getOrDefault(Object key, V defaultValue)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


ArrayList<String> list = new ArrayList<>();
  list.add("Apple");
  list.add("Banana");
  list.add("Cherry");

  if (list.contains("Banana")) {
      System.out.println("List contains Banana");
  } else {
      System.out.println("List does not contain Banana");
  }

Việc sử dụng các phương thức này sẽ giúp tối ưu hóa việc truy cập và tìm kiếm phần tử trong các tập hợp và danh sách.

Xóa trong Java Collections

Bạn có thể xóa phần tử từ các collection như ArrayList, HashSet, và HashMap bằng cách sử dụng các phương thức khác nhau như remove(), removeIf(), và clear().

1
2
3
4
5


// Nếu chúng ta muốn xóa một phần tử 'x' từ ArrayList
list.remove(x);

// Nếu chúng ta muốn xóa tất cả các phần tử 
list.clear();

Tương tự, các phương thức remove() và clear() cũng có sẵn cho các bộ sưu tập khác trong Java như Set và Map.

Thêm Java Collections

Bạn có thể thêm phần tử vào các collection như ArrayList, HashSet, và HashMap bằng cách sử dụng các phương thức như add(), addAll(), và put().

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


ArrayList<String> list = new ArrayList<>();

// Thêm phần tử vào ArrayList
list.add("Apple");
list.add("Banana");

HashMap<String, Integer> map = new HashMap<>();
  
  // Thêm phần tử vào HashMap
  map.put("Apple", 1);
  map.put("Banana", 2);
  map.put("Cherry", 3);

Khi sử dụng các phương thức này, kết quả sẽ trả về true nếu phần tử đã được thêm vào thành công và false nếu phần tử không thể được thêm vào danh sách.

Thread Safety trong Java Collections

Thread Safety trong Java Collections là khả năng các collection có thể được truy cập đồng thời bởi nhiều luồng (threads) mà không gây ra các vấn đề về tính consistency của dữ liệu hoặc gây ra excepction.

Tuy nhiên, cần cân nhắc kỹ khi sử dụng bởi vì các method này sẽ gây ra Hiệu năng thấp do việc đồng bộ hóa từng thao tác và Phức tạp hơn trong việc sử dụng và quản lý.

Java cung cấp một số cách để đảm bảo thread safety trong Collections:

Sử dụng các class Collections đồng bộ (synchronized): Vector, Stack, Hashtable, v.v.,Tuy nhiên, chúng không còn được khuyến khích sử dụng do hiệu năng không cao.
Sử dụng các method đã được define của Collections: Collections cung cấp các method để tạo ra các collection đồng bộ như synchronizedList, synchronizedSet, và synchronizedMap.
Sử dụng các class của Concurrent: Các class trong package java.util.concurrent như ConcurrentHashMap, CopyOnWriteArrayList, CopyOnWriteArraySet được thiết kế để hỗ trợ việc truy cập đồng thời một cách hiệu quả và an toàn.

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


import java.util.*;

List<String> syncList = Collections.synchronizedList(new ArrayList<>());

syncList.add("Apple");
syncList.add("Banana");

synchronized(syncList) {
    for (String s : syncList) {
        System.out.println(s);
    }
}

ConcurrentMap<String, Integer> concurrentMap = new ConcurrentHashMap<>();

concurrentMap.put("Apple", 1);
concurrentMap.put("Banana", 2);

concurrentMap.forEach((key, value) -> System.out.println(key + " = " + value));

Tổng kết về Java Collections

Tóm lại, Java Collections là một framework được sử dụng để lưu trữ và xử lý các đối tượng trong Java. Nó cung cấp các interface, abstract classes và implementation classes cho phép chúng ta thực hiện các thao tác phức tạp trên các collection như add, remove, search, sort.

Các loại Collections được hỗ trợ trong Java Collections bao gồm List, Set, Queue, Map. Mỗi loại đều có các đặc điểm riêng và phù hợp cho các mục đích sử dụng khác nhau.

Hiểu rõ các loại collections, ưu nhược điểm của từng loại, và khi nào nên sử dụng chúng sẽ giúp bạn viết mã hiệu quả và dễ bảo trì hơn. Hãy luôn chú ý đến tính an toàn với luồng khi làm việc với collections trong các ứng dụng đa luồng.

HAPPY CODING!

Nguồn các trích dẫn mình dùng trong blog:
https://www.geeksforgeeks.org/collections-in-java-2/
https://viblo.asia/p/tong-quan-ve-collections-trong-java-maGK7E0Dlj2
https://200lab.io/blog/tong-quan-ve-collections-trong-java/