So sánh các cấu trúc dữ liệu

1. Bảng so sánh nhanh

Cấu trúc	Trùng lặp?	Thứ tự?	Kích thước	Truy cập theo	Dùng khi
Array	Có	Cố định	Cố định	Chỉ số	Biết trước số lượng phần tử, cần hiệu năng cao nhất
ArrayList	Có	Thứ tự thêm vào	Linh hoạt	Chỉ số	Danh sách có thể thay đổi kích thước, cần truy cập theo vị trí
HashMap	Key không trùng	Không đảm bảo	Linh hoạt	Khóa (key)	Cần tra cứu nhanh theo một “khóa” định danh
HashSet	Không trùng	Không đảm bảo	Linh hoạt	Giá trị	Cần tập hợp phần tử duy nhất, kiểm tra tồn tại nhanh

2. Array vs ArrayList

int[] arr = new int[5];        // kích thước CỐ ĐỊNH, chứa được kiểu nguyên thủy
List<Integer> list = new ArrayList<>(); // kích thước LINH HOẠT, chỉ chứa kiểu đối tượng

• Dùng Array khi số lượng phần tử đã biết trước và không đổi - hiệu năng tốt hơn, không cần autoboxing
• Dùng ArrayList khi cần thêm/xóa phần tử linh hoạt

3. ArrayList vs HashSet

List<String> list = new ArrayList<>(); // cho phép trùng lặp, giữ thứ tự thêm vào
Set<String> set = new HashSet<>();     // KHÔNG cho trùng lặp, không đảm bảo thứ tự

• Dùng ArrayList khi thứ tự quan trọng và có thể có phần tử trùng lặp
• Dùng HashSet khi chỉ quan tâm “có tồn tại hay không”, cần loại trùng và kiểm tra contains() nhanh

4. HashMap vs HashSet

Thực ra HashSet được cài đặt dựa trên HashMap bên trong (mỗi phần tử của Set là một khóa trong Map ẩn, giá trị chỉ là placeholder):

Map<String, Integer> studentScores = new HashMap<>(); // cần LƯU một giá trị gắn với mỗi khóa
Set<String> studentNames = new HashSet<>();            // chỉ cần biết một tên CÓ TỒN TẠI hay không

• Dùng HashMap khi cần gắn một giá trị với mỗi phần tử (tra cứu theo khóa)
• Dùng HashSet khi chỉ cần biết một phần tử có mặt trong tập hợp hay không

5. Độ phức tạp thời gian (tham khảo nhanh)

Thao tác	Array	ArrayList	HashMap/HashSet
Truy cập theo chỉ số/khóa	O(1)	O(1)	O(1) trung bình
Tìm kiếm giá trị	O(n)	O(n)	O(1) trung bình (theo khóa)
Thêm vào cuối	- (cố định)	O(1) trung bình	O(1) trung bình
Xóa	- (cố định)	O(n)	O(1) trung bình

Tổng kết

• Array: nhanh nhất, kích thước cố định, biết trước số lượng
• ArrayList: linh hoạt, giữ thứ tự, cho phép trùng lặp, truy cập theo chỉ số
• HashMap: tra cứu nhanh theo khóa, gắn giá trị với từng khóa
• HashSet: tập hợp phần tử duy nhất, kiểm tra tồn tại nhanh, không có “giá trị” đi kèm