[Java Core] B6: Design Pattern Iterator. Iterable và Collection trong Java

[Java Core] B6: Design Pattern Iterator. Iterable và Collection trong Java
This entry is part 6 of 7 in the series Java Core

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.

image 60 - quochung.cyou PTIT
[Java Core] B6: Design Pattern Iterator. Iterable và Collection trong Java 31
  • 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 hay cấ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ị, …
image 62 - quochung.cyou PTIT
[Java Core] B6: Design Pattern Iterator. Iterable và Collection trong Java 32

=> 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, …
image 63 - quochung.cyou PTIT
[Java Core] B6: Design Pattern Iterator. Iterable và Collection trong Java 33

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ượng Iterator để duyệt qua các phần tử của một Collection.  
image 64 - quochung.cyou PTIT
[Java Core] B6: Design Pattern Iterator. Iterable và Collection trong Java 34
image 65 - quochung.cyou PTIT
[Java Core] B6: Design Pattern Iterator. Iterable và Collection trong Java 35

Ví dụ:

image 66 - quochung.cyou PTIT
[Java Core] B6: Design Pattern Iterator. Iterable và Collection trong Java 36


  • 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ụng Iterator.
  • 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:
image 67 - quochung.cyou PTIT
[Java Core] B6: Design Pattern Iterator. Iterable và Collection trong Java 37
  • Hoặc là có thể duyệt bằng for-each, có 2 kiểu như sau:
image 68 - quochung.cyou PTIT
[Java Core] B6: Design Pattern Iterator. Iterable và Collection trong Java 38

Đị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:

HashSetLinkedHashSetTreeSet
Cách thức làm việcHashSet 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ấtTố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ấtO(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ử NullCho 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

image 69 - quochung.cyou PTIT
[Java Core] B6: Design Pattern Iterator. Iterable và Collection trong Java 39
  • 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.
image 70 - quochung.cyou PTIT
[Java Core] B6: Design Pattern Iterator. Iterable và Collection trong Java 40

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àm compareTo() 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ụ:

image 71 - quochung.cyou PTIT
[Java Core] B6: Design Pattern Iterator. Iterable và Collection trong Java 41
  • 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 class Collections để sắp xếp các phần tử của một List:
image 72 - quochung.cyou PTIT
[Java Core] B6: Design Pattern Iterator. Iterable và Collection trong Java 42
  • Code thực tế trong Collection, có thể Ctrl+Click vào để xem
image 73 - quochung.cyou PTIT
[Java Core] B6: Design Pattern Iterator. Iterable và Collection trong Java 43
  • 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àm compare() 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ụ:

image 74 - quochung.cyou PTIT
[Java Core] B6: Design Pattern Iterator. Iterable và Collection trong Java 44
image 75 - quochung.cyou PTIT
[Java Core] B6: Design Pattern Iterator. Iterable và Collection trong Java 45
  • 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 class Collections để sắp xếp các phần tử của một List:
image 76 - quochung.cyou PTIT
[Java Core] B6: Design Pattern Iterator. Iterable và Collection trong Java 46
  • Code thực tế trong Collection, có thể Ctrl+Click vào để xem
image 77 - quochung.cyou PTIT
[Java Core] B6: Design Pattern Iterator. Iterable và Collection trong Java 47
  • 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
ComparableComparator
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:
image 78 - quochung.cyou PTIT
[Java Core] B6: Design Pattern Iterator. Iterable và Collection trong Java 48
image 79 - quochung.cyou PTIT
[Java Core] B6: Design Pattern Iterator. Iterable và Collection trong Java 49
  • 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.
Series Navigation<< [Java Core] B5: Tính chất trừu tượng, Interface và Abstract Class trong Java[Java Core] B7: Exception trong Java >>

Comments

No comments yet. Why don’t you start the discussion?

Leave a Reply