# 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

<table id="bkmrk-ti%C3%AAu-ch%C3%ADarraylist%3Ct%3E"><colgroup><col></col><col></col><col></col><col></col></colgroup><tbody><tr><th>****Tiêu chí****

</th><th>****Array****</th><th>****List&lt;T&gt;****</th><th>****HashSet&lt;T&gt;****</th></tr><tr><td>****Cấu trúc****

</td><td>Mảng cố định kích thước

</td><td>Mảng động (có Capacity, tự tăng)

</td><td>Bảng băm (bucket + hash)

</td></tr><tr><td>****Kích thước****

</td><td>Cố định (khởi tạo xong không đổi)

</td><td>Linh hoạt (tự tăng Capacity)

</td><td>Linh hoạt

</td></tr><tr><td>****Truy cập theo index****

</td><td>O(1)

</td><td>O(1)

</td><td>****Không hỗ trợ****

</td></tr><tr><td>****Duyệt tuần tự****

</td><td>O(n)

</td><td>O(n)

</td><td>O(n)

</td></tr><tr><td>****Thêm phần tử****

</td><td>Không (phải cấp phát lại)

</td><td>Cuối danh sách: trung bình O(1); chèn giữa: O(n)

</td><td>Trung bình O(1)

</td></tr><tr><td>****Tìm****

</td><td>O(n)

</td><td>O(n)

</td><td>****Trung bình O(1)****

</td></tr><tr><td>****Cho phép trùng lặp****

</td><td>Có

</td><td>Có

</td><td>****Không****<span style="white-space: pre-wrap;"> (tập hợp duy nhất)</span>

</td></tr><tr><td>****Duy trì thứ tự****

</td><td>****Thứ tự chỉ số****

</td><td>****Giữ thứ tự chèn****

</td><td>****Không đảm bảo thứ tự****

</td></tr><tr><td>****Khi nên dùng****

</td><td>Kích thước biết trước, tối đa hiệu năng/nhớ

</td><td>Danh sách tổng quát, thêm/xóa không quá nhiều ở giữa

</td><td>Kiểm tra tồn tại, phép toán tập hợp (union/intersect/diff)

</td></tr><tr><td>****Hạn chế****

</td><td>Cứng nhắc về kích thước

</td><td>Thêm/xóa giữa tốn kém O(n)

</td><td>Không truy cập theo index; overhead bộ nhớ lớn hơn

</td></tr></tbody></table>

### 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.

<table id="bkmrk-ti%C3%AAu-ch%C3%ADhashtabledic"><colgroup><col style="width: 169px;"></col><col style="width: 278px;"></col><col></col></colgroup><tbody><tr><th>****Tiêu chí****

</th><th>****Hashtable****</th><th>****Dictionary&lt;TKey,TValue&gt;****</th></tr><tr><td>****IsGeneric****

</td><td>****Không****<span style="white-space: pre-wrap;"> (non-generic) → boxing với value types</span>

</td><td>****Có****<span style="white-space: pre-wrap;"> (generic) → tránh boxing</span>

</td></tr><tr><td>****Kiểu key/value****

</td><td>`<span class="editor-theme-code">object</span>`/`<span class="editor-theme-code">object</span>`

</td><td>`<span class="editor-theme-code">TKey</span>`/`<span class="editor-theme-code">TValue</span>`

</td></tr><tr><td>****Null Key****

</td><td>****Không cho phép****

</td><td>****Không cho phép****

</td></tr><tr style="height: 10px;"><td>****Null Value****

</td><td>Cho phép (kiểu tham chiếu)

</td><td>Cho phép (kiểu tham chiếu)

</td></tr><tr><td>****Hiệu năng trung bình****

</td><td>Thấp hơn do boxing + cast

</td><td>****Tốt hơn****, đặc biệt với value types

</td></tr><tr><td>****An toàn kiểu (type-safety)****

</td><td>Thấp (dễ lỗi cast runtime)  
Trả về null

</td><td>****Cao****<span style="white-space: pre-wrap;"> (kiểm tra compile-time)</span>

Trả về exception

</td></tr><tr><td>****Thứ tự****

</td><td>Không đảm bảo

</td><td><span style="white-space: pre-wrap;">Không đảm bảo (thường là theo thứ tự chèn trên .NET hiện đại, </span>****đừng phụ thuộc****)

</td></tr><tr><td>****Thread-safety****

</td><td>Không an toàn luồng.  
<span style="white-space: pre-wrap;">Có thể bọc </span>`<span class="editor-theme-code">Hashtable.Synchronized</span>`<span style="white-space: pre-wrap;"> (overhead cao)</span>

</td><td>Không an toàn luồng.

<span style="white-space: pre-wrap;">Dùng </span>`<span class="editor-theme-code">ConcurrentDictionary<,></span>`<span style="white-space: pre-wrap;"> cho đa luồng.</span>

</td></tr><tr><td>****API****

</td><td>Cũ, chủ yếu vì tương thích legacy

</td><td>****Khuyến nghị mặc định****<span style="white-space: pre-wrap;"> trong hầu hết trường hợp</span>

</td></tr><tr><td>****Khi nên dùng****

</td><td>Chỉ khi phải tương thích code cũ

</td><td>****Lựa chọn mặc định****<span style="white-space: pre-wrap;"> cho map/tra cứu key/value.</span>

</td></tr></tbody></table>