Một bộ chỉ đơn giản là một tập hợp các đối tượng duy nhất. Duy nhất có nghĩa là không có hai đối tượng nào có thể có (các) giá trị giống nhau. Tùy thuộc vào việc thực hiện bộ, nó có thể được đặt hàng hoặc không. Bộ Java, dưới dạng Kiểu dữ liệu trừu tượng (ADT), có một số thao tác chính (trong đó T đại diện cho bất kỳ kiểu dữ liệu nào, ví dụ: int, String hoặc bất kỳ đối tượng lớp nào): ![Java Đặt làm Giao diện - 1]()
boolean add(T item): trả về true nếu mục được thêm thành công vào tập hợp và trả về false nếu mục đã có trong tập hợp.boolean remove(T item): trả về true nếu mục đã được xóa thành công khỏi tập hợp và sai nếu ngược lại (nếu mục không có trong tập hợp).boolean contains(T item): trả về true nếu mục nằm trong tập hợp và false nếu không.boolean isEmpty(): trả về true nếu set trống và false nếu ngược lại.
contains()cung cấp thời gian chạy tuyệt vời cho việc này: Độ phức tạp thời gian O(1) hoặc O(log n) tùy thuộc vào việc triển khai được sử dụng là a HashSethay aTreeSet, tương ứng. Vì vậy, một bộ có thể được sử dụng để làm gì? Chà, nếu bạn cần theo dõi nhiều đối tượng riêng biệt--chẳng hạn như ID, tên hoặc số nhận dạng duy nhất khác--và thường xuyên kiểm tra xem một mục có tồn tại trong bộ sưu tập đó hay không, thì một bộ có thể là một lựa chọn tốt. Đây là một trường hợp sử dụng ví dụ của một tập hợp: Hãy tưởng tượng rằng bạn có một danh sách Studentcác đối tượng đại diện cho tất cả học sinh trong một lớp nhất định. Mỗi người Studentcó thể có một tên duy nhất (chuỗi) và lớp (int) cho lớp này. Nếu bạn muốn thường xuyên tham khảo danh sách tất cả học sinh A (điểm >=90), thì sẽ rất tẻ nhạt khi lặp qua danh sách này và kiểm tra điểm của từng học sinh mỗi lần. Thay vào đó, bạn có thể sử dụng một HashSetchuỗi để theo dõi tất cả học sinh A trong lớp, chẳng hạn như:
- Mỗi khi điểm của học sinh được cập nhật, bạn chỉ cần kiểm tra xem điểm mới của Học sinh có lớn hơn hoặc bằng 90 hay không.
- Nếu vậy, hãy thêm chúng vào tập hợp các sinh viên A bằng cách sử dụng
add()- Nếu họ đã là học sinh hạng A, thì thao tác này đơn giản là bị bỏ qua.
- Nếu không, sau đó loại bỏ chúng khỏi tập hợp các sinh viên A bằng cách sử dụng
remove()- Nếu họ không phải là học sinh A vào thời điểm này, thì thao tác này sẽ bị bỏ qua.
- Nếu vậy, hãy thêm chúng vào tập hợp các sinh viên A bằng cách sử dụng
contains(“Johnny Appleseed”)đến trường quay. Tất nhiên, đây chỉ là một ví dụ về trường hợp sử dụng cho một tập hợp và vấn đề cụ thể về theo dõi học sinh A này có thể được giải quyết theo những cách khác.
Triển khai: Ví dụ về HashSet trong Java và Java TreeSet
CảHashSettrong Java và TreeSettrong Java đều có định dạng java.utils package. Bạn có thể nhập chúng như vậy:
// imports everything from Java's util package, including HashSet and TreeSet
import java.util.*;
import java.util.HashSet; // imports only the Java HashSet
import java.util.TreeSet; // imports only the Java TreeSet
HashSetvà Java TreeSetlà cái TreeSetđược sắp xếp, còn cái HashSetthì không. Đây là lý do tại sao TreeSetđộ phức tạp thời gian có O(log n) cho các hoạt động chính, trong khi HashSetcó độ phức tạp thời gian O(1) hoặc không đổi; phải TreeSetduy trì trật tự mọi lúc. Ngoài các hoạt động tập hợp khóa đã đề cập trước đó, cả HashSetvà TreeSettrong Java đều có một số chức năng hữu ích khác:
void clear(): xóa tập hợp tất cả các đối tượng.int size(): trả về số đối tượng trong tập hợp.Object clone(): trả về một bản sao nông của tập hợp.Iterator iterator(): trả về một trình vòng lặp cho tập hợp, bắt đầu từ đối tượng đầu tiên.
size()nếu muốn xem mình có bao nhiêu sinh viên hạng 'A' hoặc clear()nếu bạn muốn xóa danh sách vào cuối học kỳ. Bạn có thể sử dụng clone()để tạo và giữ một bản sao của danh sách học sinh A tại một thời điểm cụ thể, chẳng hạn như trong các báo cáo giữa kỳ (theo cách này, bản sao không được cập nhật cùng với bản gốc).
Ví dụ về Hashset Java
Đây là một ví dụ ngắn về aHashSetof Strings đang được sử dụng trong Java:
import java.util.HashSet;
class HashSetDemo {
public static void main(String[] args)
{
// create a HashSet of Strings
HashSet<String> hs = new HashSet<String>();
// Add elements using the add() method
hs.add("Collin");
hs.add("Bob");
hs.add("Abigail");
// Duplicates will ignored; this statement is useless
hs.add("Collin");
System.out.println(hs);
System.out.println("Bob is in the set (T/F): " + hs.contains("Bob"));
System.out.println("Max is in the set (T/F): " + hs.contains("Max"));
}
}
[Collin, Bob, Abigail]
Bob is in the set (T/F): true
Max is in the set (T/F): false
Ví dụ Java TreeSet
Ví dụ về bộ Java có thể giúp bạn hiểu lý thuyết. Đây là một ví dụ ngắn về aTreeSetof Strings đang được sử dụng trong Java:
import java.util.TreeSet;
class TreeSetDemo {
public static void main(String[] args)
{
// create a TreeSet of Strings
TreeSet<String> ts = new TreeSet<String>();
// Add elements using the add() method.
ts.add("Collin");
ts.add("Bob");
ts.add("Abigail");
// Duplicates will ignored; this statement is useless
ts.add("Collin");
// printing the set prints the names in alphabetical order!
System.out.println(ts);
System.out.println("Bob is in the set (T/F): " + ts.contains("Bob"));
System.out.println("Max is in the set (T/F): " + ts.contains("Max"));
System.out.println("Size of the set: " + ts.size());
ts.clear();
System.out.println("Size of the set after clear(): " + ts.size());
}
}
[Abigail, Bob, Collin]
Bob is in the set (T/F): true
Max is in the set (T/F): false
Size of the set: 3
Size of the set after clear(): 0
GO TO FULL VERSION