Java| HashSet | TreeSet | |
|---|---|---|
| Cấu trúc | Hash table | Red-black tree |
add/contains | O(1) trung bình | O(log n) |
| Thứ tự duyệt | Không xác định | Sắp xếp |
| Null | 1 element null | ❌ (NPE) |
| Yêu cầu | hashCode() + equals() đúng | Comparable hoặc Comparator |
| API extra | — | first, last, subSet, floor, ceiling |
java
new HashSet<>(List.of("banana", "apple")); // output thứ tự không xác định
new TreeSet<>(List.of("banana", "apple")); // apple, banana — sorted
NavigableSet<Integer> nts = new TreeSet<>(List.of(1, 3, 5, 7, 9));
nts.subSet(3, 8); // [3, 5, 7] — range query O(log n)
nts.ceiling(4); // 5Khi dùng:
- HashSet: default, 99% case chỉ cần "không trùng".
- TreeSet: khi cần duyệt theo thứ tự, range query, hoặc floor/ceiling (leaderboard nhỏ).
- LinkedHashSet: option thứ 3 — O(1) như HashSet nhưng duyệt theo insertion order. Dùng để dedup list giữ order gốc.
Chọn HashSet trừ khi cần sorted hoặc range query rõ ràng.
| HashSet | TreeSet | |
|---|---|---|
| Structure | Hash table | Red-black tree |
add/contains | O(1) average | O(log n) |
| Iteration order | Unspecified | Sorted |
| Null | 1 null element | ❌ (NPE) |
| Requirements | Correct hashCode() + equals() | Comparable or Comparator |
| Extra API | — | first, last, subSet, floor, ceiling |
java
new HashSet<>(List.of("banana", "apple")); // unspecified order
new TreeSet<>(List.of("banana", "apple")); // apple, banana — sorted
NavigableSet<Integer> nts = new TreeSet<>(List.of(1, 3, 5, 7, 9));
nts.subSet(3, 8); // [3, 5, 7] — range query in O(log n)
nts.ceiling(4); // 5When to use:
- HashSet: default, 99% of cases you only need "no duplicates".
- TreeSet: for sorted iteration, range queries, floor/ceiling (small leaderboards).
- LinkedHashSet: third option — O(1) like HashSet but iterates in insertion order. Useful to dedup a list while preserving order.
Pick HashSet unless you have a clear need for sorted access or range queries.