[Java] Java Collection Framework – Phần 3: Set và Set Interface

Để tiếp tục cho series bài viết về Java Collection Framework, trong bài viết này mình sẽ giới thiệu tới các bạn về Set (tập hợp), Set Interface và class quan trọng về tập hợp cũng như các ví dụ để làm rõ hơn các vấn đề. Trước khi bắt đầu, mình có 1 yêu cầu đó là các bạn hãy xem lại 2 bài viết trước trong series bài viết về Java Collection Framework của mình, đặc biệt là phần 2 về Collection Interface:

• [Java] Java Collection Framework – Phần 1: Giới thiệu chung
• [Java] Java Collection Framework – Phần 2: Collection Interface

1. Set (tập hợp) và đặc điểm của Set

Set hay còn gọi là bộ hoặc tập hợp, mặc dù cùng mang nghĩa là tập hợp nhưng khác với Collection thì trong Set các phần tử là duy nhất cũng có nghĩa là Set không chứa các phần tử trùng lặp. Chính vì vậy Set có một số đặc điểm sau:

• Các phần tử trong set là không trùng lặp
• Cho phép chứa phần tử null, nhưng chỉ có tối đa một phần tử null trong Set
• Nếu thêm 1 phần tử đã tồn tại trong Set vào Set thì trong Set vẫn chỉ chứa 1 phần tử mà thôi.

2. Set Interface và các phương thức bên trong

Set Inteface là một interface con được kế thừa từ Collection Interface vì vậy nó có đầy đủ các phương thức của Collection Interface, hơn nữa Set Interface cũng không có thêm 1 phương thức nào vì vậy các bạn có thể xem lại phần 2: Collection Interface để hiểu rõ hơn về các phương thức của Set Interface.

Chú ý: cách làm việc của 2 phương thức add() và addAll() trong Set Interface sẽ hơi khác với trong Collection Interface. Đó là với Set Interface, 2 phương thức này sẽ chỉ thêm phần tử vào trong Set nếu như phần tử đó chưa có trong Set.

Sau đây là một số class phổ biến implement Set Interface và đặc điểm của chúng

2.1. HashSet

HashSet là class thực thi giao diện Set Interface dựa trên cấu trúc dữ liệu bảng băm (Hash Table) cho phép việc truy câp tìm kiếm (contains), thêm (add), xóa (remove) các phần tử trong Set được thực thi với tốc độ O(1). Đây cũng là loại Set có tốc độ cao nhất.

– Một điểm đáng chú ý là trong khi sử, Iterator của HashSet có thể sẽ throw ConcurrentModificationException nếu bạn thay đổi nội dung HashSet (thêm hoặc xóa bớt phần tử) sau khi Iterator đã được tạo ra.

2.2. LinkedHashSet

LinkedHashSet là sự kết hợp giữ bảng băm (Hash table) và danh sách liên kết (linked list) để thực thi giao diện Set Interface. Tuy được kế thừa từ HashSet nhưng khác so với HashSet đó là các phần tử trong LinkedHashSet được lưu giữ dưới dạng danh sách liên kết 2 chiều.

– Một điều cần chú ý là Iterator của LinkedHashSet cho chúng ta các phần tử theo thứ tự thời gian chèn vào Set (insertion-order), phần tử nào được thêm vào trước sẽ nằm trước, và trường hợp thêm lại một phần tử đã có trong Set sẽ không ảnh hưởng tới thứ tự trong Iterator.

2.3. EnumSet

EnumSet cũng là 1 class thực thi giao diện Set Interface, tuy nhiên thay vì việc các phần tử trong Set là các đối tượng của một lớp nào đó thì các phần tử trong EnumSet lại các giá trị Enum.

3. Một số Class và Interface quan trọng về Set

3.1. AbstractSet Class

AbstractSet là một abstract class được kế thừa từ AbstractCollection đồng thời thực thi (implements) Set Interface nhằm cung cấp bộ khung (thực thi các phương thức cơ bản) để các class khác về Set trong bộ Collection Framework, hoặc các class mà chính bạn định nghĩa có thể hoạt động theo đúng tính chất và đặc điểm của Set.

Để hiểu rõ các bạn có thể truy cập vào tài liệu javadoc từ Oracle tại địa chỉ sau: https://docs.oracle.com/javase/7/docs/api/java/util/AbstractSet.html

3.2. SortedSet Interface

SortedSet là một interface được kế thừa từ Set interface. Nó hoạt động tương tự như Set nhưng có một điểm khác biệt đó là các thành phần (phần tử) bên trong sẽ được sắp xếp theo một thứ tự nhất định. Điều này cũng đồng nghĩa với việc khi sử dụng iterator để duyệt các phần tử bên trong Set, thì các phần tử này sẽ được gọi ra theo thứ tự xác định.

– Một điểm cần lưu ý là để sử dụng được SortedSet và các class thực thi SortedSet, thì bạn cần sử dụng Comparator hoặc class của các phần tử của Set phải là kiểu dữ liệu nguyên thủy hoặc implement giao diện Comparable.

– Thêm một điều cần lưu ý nữa là theo mặc định thì các phần tử trong set sẽ được sắp theo chiều tăng dần (hoặc chiều mà bạn muốn thông qua giao diện comparable) tuy nhiên bạn cũng có thể duyệt các phần tử theo thứ tự ngược lại bằng cách sử dụng phương thứ descendingIterator().

Link javadoc từ Oracle: https://docs.oracle.com/javase/7/docs/api/java/util/SortedSet.html

3.2.1. TreeSet – Class đặc trưng cho SortedSet

Mỗi khi nhắc đến SortedSet bạn sẽ phải nghĩ ngay đến TreeSet, một dạng Set được xây dựng dựa trên cấu trúc dữ liệu cây (tree), cho phép các hành động (phương thức) cơ bản như add(), remove(), contains() đều được thực hiện trong thời gian là O(log(n)).

– Một điều cần lưu ý là TreeSet không synchronized (không đồng bộ) vì vậy khi có nhiều hơn một luồng (thread) cùng tương tác với đối tượng TreeSet thì bạn cần phải sử dụng câu lệnh trong khối lệnh synchronized. Còn nếu bạn muốn tạo một SortedSet dạng synchronized thì bạn có thể sử dụng phương thức synchronizedSortedSet() của lớp công cụ Collections mà mình sẽ nhắc tới trong bài viết sau trong cùng series bài viết này. Cách sử dụng cụ thể như sau:

– Ngoài ra trong bộ Java Collection Framework còn có class ConcurrentSkipListSet cũng thực thi giao diện SortedSet, tuy nhiên class ít được sử dụng hơn nên mình sẽ không nhắc tới ở đây (có thể mình sẽ đề cập đến trong một bài viết khác).

3.2.2 Một số phương thức đặc trưng của SortedSet

Ngoài các phương thức được kế thừa từ Set, SortedSet còn có thêm các phương thức sau:

1 – comparator()

Return:

• Comparator được sử dụng để sắp xếp các phần tử trong Set
• Hoặc null nếu sử dụng comparator mặc định

2 – first()

Return: Phần tử đầu tiên (nhỏ nhất theo thứ tự sắp xếp) của Set hiện tại

3 – last()

Return: Phần tử cuối cùng (lớn nhất theo thứ tự sắp xếp) của Set hiện tại

4 – headSet(E toElement)

Return: SortedSet<E> bao gồm các phần tử nằm trước (nhỏ hơn) toElement trong Set hiện tại theo thứ tự sắp xếp

5 – tailSet(E fromElement)

Return: SortedSet<E> bao gồm các phần tử nằm sau (lớn hơn) toElement trong Set hiện tại  theo thứ tự sắp xếp

6 – subSet(E fromElement, E toElement)

Return: SortedSet<E> bao gồm các phần tử bắt đầu từ (lớn hơn hoặc bằng) fromElement và đứng trước (nhỏ hơn) toElement trong SortedSet hiện tại

3.3. NavigableSet Interface

NavigableSet là một interface được kế thừa từ SortedSet. Vì vậy nó mang đầy đủ đặc điểm của SortedSet, điểm khác biệt là NavigableSet có thêm các phương thức bổ sung cho việc sắp xếp các phần tử trong Set.

– Một điều đáng ngạc nhiên là cả 2 class TreeSet và ConcurrentSkipListSet thực thi giao diện SortedSet ở trên cũng đều thực thi giao diện NavigableSet.

3.3.1. Các phương thức đặc trưng của NavigableSet

Như đã đề cập ở trên là so với SortedSet thì NavigableSet có thêm các phương thức bổ sung cho việc sắp xếp, vậy liệu các bạn có tò mò rằng các phương thức đó là những phương thức nào không? Nếu có thì hãy đọc phần dưới đây để biết câu trả lời nhé 😀

1 – descendingSet()

Return: Một NavigableSet là đảo của Set hiện tại hay chính là 1 NavigableSet có đầy đủ các phần tử của NavigableSet hiện tại nhưng được sắp xếp theo thứ tự ngược lại.

2 – descendingIterator()

Return: tương tự như descendingSet(), descendingIterator() trả lại 1 Iterator với thứ tự các phần tử được đảo ngược lại so với NavigableSet hiện tại

3 – ceiling(E e)

Return: phần tử nhỏ nhất mà lớn hơn hoặc bằng so với phần tử e (chính nó hoặc phần tử ngay sau e trong Set)

4 – floor(E e)

Return: phần tử lớn nhất mà nhỏ hơn hoặc bằng so với phần tử e (chính nó hoặc phần tử ngay trước e trong Set)

5 – higher(E e)

Return: phần tử nhỏ nhất mà lớn hơn so với phần tử e (phần tử đứng ngay sau e)

6 – lower(E e)

Return: phần tử lớn nhất mà nhỏ hơn so với phần tử e (phần tử đứng ngay trước e)

7 – pollFirst()

Chức năng: Lấy ra và xóa phần tử đầu tiên (nhỏ nhất) bên trong NavigableSet

Return:

• phần tử nhỏ nhất
• Hoặc null nếu Set rỗng (không có phần tử nào)

8 – pollLast()

Chức năng: Lấy ra phần tử cuối cùng (lớn nhất) bên trong NavigableSet

Return:

• Phần tử lớn nhất
• Hoặc null nếu Set rỗng

Như vậy là mình đã giới thiệu xong tới các bạn về Set – một thành phần quan trọng bên trong Java Collection Framework. Mong các bạn hãy tiếp tục ủng hộ mình trong các bài viết tiếp theo của series bài viết về Java Collection Framework và trong cả blog của mình nhé.