Cấu trúc dữ liệu
Array, List và HashSet
Cả 3 đều là cấu trúc dữ liệu được sử dụng để lưu trữ một tập hợp các phần tử có cùng kiểu dữ liệu
Tiêu chí | Array | List<T> | HashSet<T> |
|---|---|---|---|
Cấu trúc | Mảng cố định kích thước | Mảng động (có Capacity, tự tăng) | Bảng băm (bucket + hash) |
Kích thước | Cố định (khởi tạo xong không đổi) | Linh hoạt (tự tăng Capacity) | Linh hoạt |
Truy cập theo index | O(1) | O(1) | Không hỗ trợ |
Duyệt tuần tự | O(n) | O(n) | O(n) |
Thêm phần tử | Không (phải cấp phát lại) | Cuối danh sách: trung bình O(1); chèn giữa: O(n) | Trung bình O(1) |
Tìm | O(n) | O(n) | Trung bình O(1) |
Cho phép trùng lặp | Có | Có | Không (tập hợp duy nhất) |
Duy trì thứ tự | Thứ tự chỉ số | Giữ thứ tự chèn | Không đảm bảo thứ tự |
Khi nên dùng | Kích thước biết trước, tối đa hiệu năng/nhớ | Danh sách tổng quát, thêm/xóa không quá nhiều ở giữa | Kiểm tra tồn tại, phép toán tập hợp (union/intersect/diff) |
Hạn chế | Cứng nhắc về kích thước | Thêm/xóa giữa tốn kém O(n) | Không truy cập theo index; overhead bộ nhớ lớn hơn |
Hashtable và Dictionary
Đều là cấu trúc dữ liệu để lưu trữ dữ liệu dưới dạng cặp key/value.
Tiêu chí | Hashtable | Dictionary<TKey,TValue> |
|---|---|---|
IsGeneric | Không (non-generic) → boxing với value types | Có (generic) → tránh boxing |
Kiểu key/value |
|
|
Null Key | Không cho phép | Không cho phép |
Null Value | Cho phép (kiểu tham chiếu) | Cho phép (kiểu tham chiếu) |
Hiệu năng trung bình | Thấp hơn do boxing + cast | Tốt hơn, đặc biệt với value types |
An toàn kiểu (type-safety) | Thấp (dễ lỗi cast runtime) | Cao (kiểm tra compile-time) Trả về exception |
Thứ tự | Không đảm bảo | Không đảm bảo (thường là theo thứ tự chèn trên .NET hiện đại, đừng phụ thuộc) |
Thread-safety | Không an toàn luồng. | Không an toàn luồng. Dùng |
API | Cũ, chủ yếu vì tương thích legacy | Khuyến nghị mặc định trong hầu hết trường hợp |
Khi nên dùng | Chỉ khi phải tương thích code cũ | Lựa chọn mặc định cho map/tra cứu key/value. |