- [Java Core] B1: Tại sao nên học Java, syntax cơ bản
- [Java Core] B2: Class và Object (Lớp và đối tượng)
- [Java Core] B3: Cách Java quản lý dữ liệu
- [Java Core] B4: Tính chất đóng gói, kế thừa và đa hình trong Java
- [Java Core] B5: Tính chất trừu tượng, Interface và Abstract Class trong Java
- [Java Core] B6: Design Pattern Iterator. Iterable và Collection trong Java
- [Java Core] B7: Exception trong Java
Buổi 6: Một số trúc dữ liệu thường thấy trong Java
- Cấu trúc dữ liệu là gì, sử dụng khi nào
- Interface Iterable, Collection -> List, Set, Queue
- Interface Map, SortedMap -> HashMap, TreeMap
- Sử dụng một số hàm của cấu trúc dữ liệu như sort
Cấu trúc dữ liệu là gì, sử dụng khi nào
Cấu trúc dữ liệu là một cách tổ chức dữ liệu trong máy tính để có thể lưu trữ và xử lý dữ liệu một cách hiệu quả. Cấu trúc dữ liệu là một phần quan trọng trong việc thiết kế các chương trình và các thuật toán.
![[Java Core] B6: Design Pattern Iterator. Iterable và Collection trong Java 12 image 60 - quochung.cyou PTIT](http://213.35.113.17:9002/wp-content/uploads/2024/01/image-60.png)
- Thông thường, sẽ có 2 kiểu cấu trúc dữ liệu chính là
Linear Data Structure
vàNon-Linear Data Structure
haycấu trúc dữ liệu tuyến tính
vàcấu trúc dữ liệu phi tuyến tính
. - Cấu trúc dữ liệu tuyến tính là các cấu trúc dữ liệu mà các phần tử dữ liệu được sắp xếp theo một thứ tự nhất định. Các cấu trúc dữ liệu tuyến tính thường được sử dụng để lưu trữ dữ liệu đơn giản như danh sách, mảng, hàng đợi, stack, …
- Cấu trúc dữ liệu phi tuyến tính là các cấu trúc dữ liệu mà các phần tử dữ liệu được sắp xếp theo một thứ tự không nhất định. Các cấu trúc dữ liệu phi tuyến tính thường được sử dụng để lưu trữ dữ liệu phức tạp như cây, đồ thị, …
![[Java Core] B6: Design Pattern Iterator. Iterable và Collection trong Java 13 image 62 - quochung.cyou PTIT](http://213.35.113.17:9002/wp-content/uploads/2024/01/image-62.png)
=> Câu hỏi: Với các cấu trúc dữ liệu phức tạp như vậy, làm sao để ta có thể lưu trữ, và duyệt qua các phần tử của chúng?
- Nghe như một công việc đơn giản với các cấu trúc dữ liệu tuyến tính như list. Ta chỉ cần duyệt qua toàn bộ phần tử khi duyệt. Nhưng làm sao để ta duyệt thứ tự một cấu trúc dữ liệu phức tạp, ví dụ như
cây
? Có thể, ta cần nó duyệt theo DFS, hoặc BFS, hoặc duyệt theo thứ tự trước, sau, hoặc duyệt ngẫu nhiên, …
![[Java Core] B6: Design Pattern Iterator. Iterable và Collection trong Java 14 image 63 - quochung.cyou PTIT](http://213.35.113.17:9002/wp-content/uploads/2024/01/image-63.png)
Interface Iterable, Collection -> List, Set, Queue
- Interface
Iterable
là một interface trong Java, nó có một phương thức làiterator()
trả về một đối tượngIterator
để duyệt qua các phần tử của mộtCollection
.
![[Java Core] B6: Design Pattern Iterator. Iterable và Collection trong Java 15 image 64 - quochung.cyou PTIT](http://213.35.113.17:9002/wp-content/uploads/2024/01/image-64-719x1024.png)
![[Java Core] B6: Design Pattern Iterator. Iterable và Collection trong Java 16 image 65 - quochung.cyou PTIT](http://213.35.113.17:9002/wp-content/uploads/2024/01/image-65.png)
Ví dụ:
![[Java Core] B6: Design Pattern Iterator. Iterable và Collection trong Java 17 image 66 - quochung.cyou PTIT](http://213.35.113.17:9002/wp-content/uploads/2024/01/image-66-1024x869.png)
- Như trong ví dụ trên, ta có thể thấy, ta có thể duyệt qua các phần tử của một
Collection
bằng cách sử dụngIterator
. - Ta lấy ra iterator của object list, thuộc class ArrayList. Do interface List đã define hàm iterator, nên class ArrayList phải implement hàm iterator này, và tự triển khai logic cách để duyệt qua bản thân như thế nào.
- Các class khác như LinkedList, Vector, … cũng phải implement hàm iterator này, và tự triển khai logic cách để duyệt qua bản thân như thế nào.
- Điều này cho phép khi duyệt qua các Map, Set, … ta không cần phải quan tâm đến cách duyệt của chúng, mà chỉ cần gọi hàm iterator() của chúng, và duyệt qua các phần tử của chúng.
- Ví dụ về việc duyệt qua các phần tử của một
Set
:
![[Java Core] B6: Design Pattern Iterator. Iterable và Collection trong Java 18 image 67 - quochung.cyou PTIT](http://213.35.113.17:9002/wp-content/uploads/2024/01/image-67-1024x883.png)
- Hoặc là có thể duyệt bằng for-each, có 2 kiểu như sau:
![[Java Core] B6: Design Pattern Iterator. Iterable và Collection trong Java 19 image 68 - quochung.cyou PTIT](http://213.35.113.17:9002/wp-content/uploads/2024/01/image-68-1024x757.png)
Định nghĩa một số cấu trúc dữ liệu trong Java
Set
- Set: là một cấu trúc dữ liệu mà nó không chứa các phần tử trùng lặp. Các phần tử trong Set được sắp xếp theo thứ tự tùy vào cách implement của từng class. Các class implement Set có thể là HashSet, LinkedHashSet, TreeSet, …
- HashSet: là một class implement Set, nó sử dụng một HashMap để lưu trữ các phần tử. Do đó, các phần tử trong HashSet sẽ không được sắp xếp theo thứ tự
- LinkedHashSet: là một class implement Set, nó sử dụng một LinkedHashMap để lưu trữ các phần tử. Do đó, các phần tử trong LinkedHashSet sẽ được sắp xếp theo thứ tự.
- TreeSet: là một class implement Set, nó sử dụng một TreeMap để lưu trữ các phần tử. Do đó, các phần tử trong TreeSet sẽ được sắp xếp theo thứ tự.
Độ phức tạp:
HashSet | LinkedHashSet | TreeSet | |
---|---|---|---|
Cách thức làm việc | HashSet sử dụng HashMap nội bộ để lưu trữ phần tử. | LinkedHashSet sử dụng LinkedHashMap nội bộ để lưu trữ phần tử. | TreeSet sử dụng TreeMap nội bộ để lưu trữ phần tử. |
Thứ tự của các phần tử | Không duy trì thứ tự của các phần tử. | Duy trì thứ tự chèn của các phần tử. | Duy trì thứ tự theo bộ so sánh (hoặc tăng dần tự nhiên). |
Hiệu suất | Tốt hơn so với LinkedHashSet và TreeSet. | Nằm giữa HashSet và TreeSet, hiệu suất gần như tương tự HashSet. | Thấp hơn HashSet và LinkedHashSet do phải sắp xếp. |
Thao tác thêm, xóa, truy xuất | O(1) cho chèn, loại bỏ, và truy xuất. | O(1) cho chèn, loại bỏ, và truy xuất. | O(log(n)) cho chèn, loại bỏ, và truy xuất. |
So sánh các phần tử | Sử dụng equals() và hashCode() để so sánh và loại bỏ phần tử trùng lặp. | Sử dụng equals() và hashCode() để so sánh và loại bỏ phần tử trùng lặp. | Sử dụng compare() hoặc compareTo() để so sánh và loại bỏ phần tử trùng lặp. Không sử dụng equals() và hashCode(). |
Phần tử Null | Cho phép tối đa một phần tử null. | Cho phép tối đa một phần tử null. | Không cho phép phần tử null, nếu thử chèn sẽ ném NullPointerException. |
Sử dụng bộ nhớ | Đòi hỏi ít bộ nhớ hơn so với LinkedHashSet và TreeSet. | Yêu cầu bộ nhớ nhiều hơn HashSet do duy trì LinkedList cùng với HashMap. | Yêu cầu bộ nhớ nhiều hơn HashSet do duy trì bộ so sánh và TreeMap. |
Khi nào sử dụng? | Muốn danh sách không chứa phần tử trùng và không cần duy trì thứ tự. | Muốn danh sách không chứa phần tử trùng và muốn duy trì thứ tự chèn. | Muốn danh sách không chứa phần tử trùng và muốn sắp xếp các phần tử. |
Tóm gọn:
- HashSet: không duy trì thứ tự, tốc độ nhanh
- LinkedHashSet: duy trì thứ tự theo thứ tự chèn, tốc độ giữa
- TreeSet: duy trì thứ tự theo bộ so sánh, tốc độ chậm hơn
Map
- Là cấu trúc dữ liệu theo kiểu key-value, trong đó key là duy nhất, và value có thể trùng nhau. Các class implement Map có thể là HashMap, LinkedHashMap, TreeMap, …
Sơ đồ kế thừa của các cấu trúc dữ liệu trong Java
![[Java Core] B6: Design Pattern Iterator. Iterable và Collection trong Java 20 image 69 - quochung.cyou PTIT](http://213.35.113.17:9002/wp-content/uploads/2024/01/image-69-1024x594.png)
- Theo hình trên, ta có 3 interface chủ đạo gồm List, Queue, Set sẽ kế thừa từ interface Collection. Từ interface Collection, chúng sẽ có các hàm chung như add, remove, contains, … và các hàm khác.
- Lúc này, ở các class implement List, Queue, Set, chúng sẽ phải implement các hàm này, và tự triển khai logic cách để add, remove, contains, … như thế nào. Ngoài ra là triển khai các hàm từ interface Iterable, để có thể duyệt qua các phần tử của chúng, và các hàm từ riêng các interface List, Queue, Set, để có thể thực hiện các thao tác riêng của chúng.
- Map thì là một trường phái khác, do chúng không kế thừa từ interface Collection, vì Map nhận vào 2 value. Do đó, để sử dụng được các hàm Collection trong Map, ta có thể lấy ra keySet, valueSet, entrySet của Map, và sử dụng các hàm Collection trên chúng.
![[Java Core] B6: Design Pattern Iterator. Iterable và Collection trong Java 21 image 70 - quochung.cyou PTIT](http://213.35.113.17:9002/wp-content/uploads/2024/01/image-70-1024x1006.png)
Về Comparable và Comparator, cách sử dụng trong các cấu trúc dữ liệu để sắp xếp
- Trong Java, có 2 cách để sắp xếp các phần tử của một cấu trúc dữ liệu, đó là sử dụng Comparable và Comparator.
- Comparable là một interface, nó có một hàm là
compareTo()
, và nó được implement bởi các class muốn sắp xếp các phần tử của chúng. HàmcompareTo()
sẽ trả về một số nguyên, và nó sẽ được sử dụng để so sánh 2 phần tử của cấu trúc dữ liệu đó. Nếu trả về số âm, thì phần tử đầu tiên sẽ được đặt trước phần tử thứ hai, nếu trả về số dương, thì phần tử thứ hai sẽ được đặt trước phần tử đầu tiên, nếu trả về 0, thì 2 phần tử sẽ được đặt ngang hàng với nhau.
Code ví dụ:
![[Java Core] B6: Design Pattern Iterator. Iterable và Collection trong Java 22 image 71 - quochung.cyou PTIT](http://213.35.113.17:9002/wp-content/uploads/2024/01/image-71-964x1024.png)
- Như code trên, class Student implement interface Comparable, và phải triển khai cách để so sánh giữa 2 Student với nhau
- Để sử dụng so sánh, ta có thể sử dụng hàm
sort()
của classCollections
để sắp xếp các phần tử của mộtList
:
![[Java Core] B6: Design Pattern Iterator. Iterable và Collection trong Java 23 image 72 - quochung.cyou PTIT](http://213.35.113.17:9002/wp-content/uploads/2024/01/image-72-1024x976.png)
- Code thực tế trong Collection, có thể Ctrl+Click vào để xem
![[Java Core] B6: Design Pattern Iterator. Iterable và Collection trong Java 24 image 73 - quochung.cyou PTIT](http://213.35.113.17:9002/wp-content/uploads/2024/01/image-73-1024x320.png)
- Như code trên, ta có thể thấy, hàm sort của Collections sẽ nhận vào một List, và List này phải chứa T là một class implement Comparable, và hàm sort sẽ sử dụng hàm compareTo của T để so sánh các phần tử của List với nhau.
- Comparator là một interface, nó có một hàm là
compare()
, và nó được implement bởi các class muốn sắp xếp các phần tử của chúng. Hàmcompare()
sẽ trả về một số nguyên, và nó sẽ được sử dụng để so sánh 2 phần tử của cấu trúc dữ liệu đó. Nếu trả về số âm, thì phần tử đầu tiên sẽ được đặt trước phần tử thứ hai, nếu trả về số dương, thì phần tử thứ hai sẽ được đặt trước phần tử đầu tiên, nếu trả về 0, thì 2 phần tử sẽ được đặt ngang hàng với nhau.
Code ví dụ:
![[Java Core] B6: Design Pattern Iterator. Iterable và Collection trong Java 25 image 74 - quochung.cyou PTIT](http://213.35.113.17:9002/wp-content/uploads/2024/01/image-74-954x1024.png)
![[Java Core] B6: Design Pattern Iterator. Iterable và Collection trong Java 26 image 75 - quochung.cyou PTIT](http://213.35.113.17:9002/wp-content/uploads/2024/01/image-75-1024x474.png)
- Như code trên, class StudentAgeComparator implement interface Comparator, và phải triển khai cách để so sánh giữa 2 Student với nhau
- Để sử dụng so sánh, ta có thể sử dụng hàm
sort()
của classCollections
để sắp xếp các phần tử của mộtList
:
![[Java Core] B6: Design Pattern Iterator. Iterable và Collection trong Java 27 image 76 - quochung.cyou PTIT](http://213.35.113.17:9002/wp-content/uploads/2024/01/image-76-1024x941.png)
- Code thực tế trong Collection, có thể Ctrl+Click vào để xem
![[Java Core] B6: Design Pattern Iterator. Iterable và Collection trong Java 28 image 77 - quochung.cyou PTIT](http://213.35.113.17:9002/wp-content/uploads/2024/01/image-77-1024x338.png)
- Như code trên, ta có thể thấy, hàm sort của Collections sẽ nhận vào một List, và 1 Comparator, và hàm sort sẽ sử dụng hàm compare của Comparator để so sánh các phần tử của List với nhau.
- So sánh Comparable và Comparator
Comparable | Comparator |
---|---|
Comparable là một interface, nó có một hàm là compareTo(), và nó được implement bởi các class muốn sắp xếp các phần tử của chúng. | Comparator là một interface, nó có một hàm là compare(), và nó được implement bởi các class muốn sắp xếp các phần tử của chúng. |
Comparable bắt buộc triển khai trong class mà ta muốn sort class đó, và chỉ chỉ khai được một cách duy nhất. | Comparator không bắt buộc triển khai trong class mà ta muốn sort class đó, và có thể khai báo nhiều Comparator khác nhau, tuỳ vào mục đích sử dụng. |
- Ví dụ về việc sử dụng nhiều loại Comparator khác nhau:
![[Java Core] B6: Design Pattern Iterator. Iterable và Collection trong Java 29 image 78 - quochung.cyou PTIT](http://213.35.113.17:9002/wp-content/uploads/2024/01/image-78-1024x958.png)
![[Java Core] B6: Design Pattern Iterator. Iterable và Collection trong Java 30 image 79 - quochung.cyou PTIT](http://213.35.113.17:9002/wp-content/uploads/2024/01/image-79-1024x658.png)
- Như code trên, ta có thể thấy, ta có thể sử dụng nhiều Comparator khác nhau, để sắp xếp các phần tử của List theo nhiều cách khác nhau.