Set, Queue

Kiểu dữ liệu và Exceptions trong Java

Jim White

Java Developer

Giao diện Set

Set cũng là một loại Collection
- Không cho phép phần tử trùng lặp
  - Đảm bảo mỗi phần tử là duy nhất
- Các Set thường không có thứ tự (nên không có chỉ mục)
List giống hộp thuốc chia ngăn; mỗi phần tử ở một vị trí xác định
Set giống bao tải; phần tử nằm ngẫu nhiên trong bao

List như hộp chia thuốc, phần tử lưu theo chỉ mục ở vị trí cố định

Set như bao tải chứa phần tử ngẫu nhiên, không có thứ tự

¹ Hình ảnh do Wikimedia Commons cung cấp

List vs Set

Khi nào dùng Set
- Đảm bảo phần tử duy nhất
- Tra cứu nhanh hơn
  - Kiểm tra một phần tử có trong Set
- Tiết kiệm bộ nhớ hơn khi tập lớn dần
- Tốt cho kiểm tra tư cách thành viên trong cache
  - Ví dụ: tìm từ duy nhất trong tài liệu

List vs Set

Khi nào dùng List
- Giữ nguyên thứ tự và cho phép trùng lặp
- Truy cập theo vị trí nhanh hơn
- Thêm/xóa theo chỉ mục nhanh hơn
- Phù hợp khi thứ tự quan trọng
  - Ví dụ: quản lý bước của quy trình hoặc bài hát trong playlist

Hiện thực Set

Nhiều hiện thực của Set
- HashSet là hiện thực phổ biến
HashSet
- Túi phần tử không có thứ tự
- Nhanh hơn các Set khác khi chèn, xóa, tra cứu
- Thường dùng nhiều bộ nhớ hơn các Set khác
- Cho phép một null

HashSet là túi không có thứ tự, cho phép một null

Tạo HashSet

Dùng constructor tổng quát (generic) để tạo HashSet
```
HashSet<String> set = new HashSet<String>();
```
HashSet nằm trong gói java.util
- Cần import
- import java.util.HashSet

Phương thức HashSet

Dùng .add() và .remove() để thêm, xóa phần tử
Dùng .remove() rồi .add() để thay thế một phần tử
Dùng .contains() để kiểm tra phần tử đã tồn tại
Bỏ qua phần tử trùng lặp
Cho phép null
Không đảm bảo thứ tự

set.add("France");
set.add("Japan");
set.add("Brazil");
set.add("Egypt");
set.add(null); // null được phép
set.remove("Brazil");

boolean z =
  set.contains("France"); // z là true
set.add("Japan"); // Bị bỏ qua
System.out.println(set);

[null, Japan, Egypt, France]

Giao diện Queue

Cấu trúc dữ liệu Queue xử lý theo nguyên tắc vào trước ra trước (FIFO)
- Phần tử thêm đầu tiên sẽ được lấy ra đầu tiên
- Như xếp hàng mua vé
- Có phần đầu (head) và đuôi (tail)

Hình hàng đợi với head (đầu) và tail (đuôi) được đánh dấu

Có nhiều hiện thực của Queue
- Tương tự về hành vi và thao tác

ArrayBlockingQueue

Hiện thực Queue phổ biến
- Dùng mảng bên dưới
Lưu ý: ArrayBlockingQueue nằm trong gói java.util.concurrent
- Không thuộc java.util

Tạo ArrayBlockingQueue

Dùng constructor tổng quát để tạo ArrayBlockingQueue
- Có sức chứa (giới hạn số phần tử) xác định qua constructor

import java.util.concurrent;  // Ở đầu lớp

// Tạo queue mới chứa tối đa 4 String
ArrayBlockingQueue<String> queue = new ArrayBlockingQueue<String>(4);

Phương thức ArrayBlockingQueue

Dùng .add(object) hoặc .offer(object) để thêm vào đuôi
- .add(object) ném ngoại lệ khi Queue đầy
- .offer(object) bỏ qua phần tử mới khi đã đầy

ArrayBlockingQueue<String> queue 
    = new ArrayBlockingQueue<String>(4);
queue.offer("France");
queue.offer("Japan");
queue.offer("Brazil");
queue.offer("Egypt");
queue.offer("China"); // Bỏ qua China

// Gây IllegalStateException
// queue.add("China");

System.out.println(queue);

[France, Japan, Brazil, Egypt]

Phương thức ArrayBlockingQueue

Dùng .remove() hoặc .poll() để lấy từ đầu hàng
- .remove() ném ngoại lệ khi Queue rỗng
- .poll() trả về null khi Queue rỗng
Không cho phép null

ArrayBlockingQueue<String> queue 
    = new ArrayBlockingQueue<String>(4);
String x = queue.poll(); // x là null
// Gây NoSuchElementException
// String y = queue.remove();

queue.offer("France");
String next = queue.poll();
System.out.println(next);

France

Ayo berlatih!

Kiểu dữ liệu và Exceptions trong Java