C#.NET Căn bản: Hiểu biết về các Collection trong .NET Framework

Thư viện class .NET Base Class Library (BCL) cung cấp rất nhiều các class để thao tác với collection và giúp bạn quản lý các tập hợp đối tượng dễ dàng hơn. Với số lượng phong phú như vậy, nhiều khi bạn sẽ chưa hiểu hết nên dẫn đến khó khăn để chọn lựa đúng loại class collection mà mình mong muốn tốt nhất cho bài toán của mình. Cái khó là chọn đúng collection chính là chìa khóa để bạn đạt được sự tối ưu trong chương trình của mình và khả năng bảo trì hệ thống.

Bài viết này sẽ xóa bỏ mọi sự lờ mờ giữa các collection và các trường hợp nào nên dùng loại nào để phát huy hiệu suất tối đa. Chúng ta sẽ dành phần lớn thời gian để tìm hiểu về namespace: System.Collections.Generic, generic được đề xuất cho việc quản lý tập các đối tượng.

Các collection generic được giới thiệu trong phiên bản .NET 2.0 và chúng được đặt trong namespace System.Collections.Generic. Đây là phần chính của các collection mà bạn nên tập trung vào trước, vì nó sẽ phù hợp với 99% các trường hợp mà bạn cần để giải quyết bài toán.

Một chú ý quan trọng là các class collection generic đều không giống nhau. Từ giải thuật triển khai, cách lưu cấu trúc dữ liệu bên trong và dành cho các mục đích khác nhau. Nên việc bạn hiểu về nó sẽ giúp bạn tối ưu được hiệu năng chương trình. Hơn nữa, các chương trình multi-thread sẽ an toàn nếu  bạn lựa chọn sáng suốt trong việc sử dụng các collection đồng bộ (concurrent collection).

Vậy hãy nhìn vào mỗi collection và chỉ ra điểm mạnh điểm yếu trong bảng tổng hợp phía bên dưới giúp bạn dễ dàng so sánh sự khác biệt giữa các collection.

Các collection có kiên kết lữu trữ một giá trị trong tập hợp bởi 1 key được sử dụng để thêm/xóa/tìm kiếm các phần tử. Vì thế, các tập hợp này có sự kiên kết giữa key và value. Các collection này hầu hết được dùng khi bạn cần tìm kiếm/thao tác với một tập hợp sử dụng cặp key-value. Ví dụ nếu bạn muốn tìm kiếm một từ tiếng Việt dựa vào một từ tiếng Anh trong từ điển với key là từ tiếng Anh và value là một từ tiếng Việt tương ứng.

Dictionary<TKey,TValue> là một collection được sử dụng nhiều nhất. Dictionary<TKey,TValue> là class có tốc độ tìm kiếm, thêm, xóa phần tử nhanh nhất vì nó sử dụng một bảng băm (hash table) bên dưới. Bởi vì các key được băm ra, các key này nên được triển khai các method GetHashCode() và Equals() hoặc bạn nên cung cấp một interface IEqualityComparer khi khởi tạo từ điển. Thời gian thêm/xóa/tìm kiếm các phần tử trong từ điển được tính bằng giá trị hằng số là O (1) nghĩa là không quan trọng từ điển lớn ra sao, thờ igian để tìm kiếm phần tử vẫn không đổi. Đây là điều mong muốn nhất cho việc tìm kiếm tốc độ cao. Chỉ có một nhược điểm của dictionary là mặc định nó sử dụng 1 bảng băm, không được sắp xếp, và bạn không thể dễ dàng duyệt qua các phần tử theo một thứ tự nào đó.

SortedDictionary<TKey, TValue> tương tự như Dictionary<TKey,TValue> trong việc sử dụng nhưng khác nhau về việc triển khai. SortedDictionary<TKey, TValye> sử dụng một cây nhị phân (binary tree) để xử lý việc quản lý các phần tử theo thứ tự sắp xếp của key. Và kết quả của việc sắp xếp là kiểu TKey của key phải triển khai interface IComparable<TKey> nếu không thì các key sẽ không được sắp xếp đúng. SortedDictionary đánh đổi một chút thời gian tìm kiếm với việc thao tác như thêm/xóa/tìm kiếm. Dẫn đến thời gian thao tác của nó có giá trị O (log n). Nghĩa là với thời gian này, nếu bạn có gấp đôi kích thước của từ điển thì nó sẽ phải thêm thời gian so sánh để tìm kiếm phần tử. Sử dụng SortedDictionary<TKey,TValue> khi bạn muốn tìm kiếm nhanh hơn nhưng lại muốn có khả năng duy trì tập hợp này với thứ tự sắp xếp theo key.

SortedList<TKey,TValue> là một collection khác được sắp xếp và có liên kết trong danh sách các collection generic. Một lần nữa SortedList<TKey,TValue>  lại giống với SortedDictionary<TKey,TValue> trong việc sử dụng key để sắp xếp. Không giống SortedDictionary tuy nhiên các phần tử trong SortedList lại được lưu trữ dưới dạng mảng được sắp xếp. Nghĩa là việc thêm và xóa sẽ có thời gian là O(n) bởi vì xóa hay thêm mới phần tử vào sẽ phải chuyển tất cả các phần tử khác dịch lên hoặc dịch xuống trong danh sách. Thời gian tìm kiếm sẽ là O (log n) bởi vì SortedList có thể sử dụng cây nhị phân để tìm kiếm bất cứ phần tử nào trong danh sách bằng chính key của nó. Tại sao bạn muốn làm điều này? Câu trả lời là nếu bạn load SortedList lên trước, việc thêm sẽ chậm hơn nhưng các chỉ số của mảng sẽ nhanh hơn việc liên kết các đối tượng, tìm kiếm sẽ nhanh hơn một chút hơn là SortedDictionary. Tôi sẽ dùng SortedList khi muốn tìm kiếm nhanh, và muốn duy trì tập hợp theo thứ tự sắp xếp của key, và ít khi thêm hay xóa phần tử.

Các collection class khác không liên kết. Chúng không sử dụng key để thao tác với tâp hợp nhưng dựa trên chính đối tượng được lưu trữ hoặc một số thì thao tác thông qua chỉ số (index)

List<T> là một collection lưu trữ liên tiếp. Vài người có lẽ gọi đây là vector hoặc mảng động. Cơ bản nó là một mảng các phần tử được có thể mở rộng kích thước (capacity) khi số lượng phần tử đạt tới tới hạn của kích cỡ của nó. Bởi vì các phần tử được lưu trữ liên tiếp như một mảng, bạn có thể truy cập đến các phần tử trong List<T> bằng chỉ số (index) rất nhanh. Tuy nhiên việc thêm, và xóa phần tử ở đầu, hoặc giữa của List<T> sẽ nhiều chi phí bởi vì bạn phải chuyển tất cả các phần tử khác lên hoặc xuống trong danh sách khi bạn xóa hoặc chèn. Tuy nhiên thêm mới và xóa ở vị trí cuối cùng của List<T> thì chi phí của nó sẽ là hằng số - O (1). Thông thường List<T> được dùng khi bạn không có bất cứ ràng buộc nào khác, và thường chúng ta hay dùng List<T> ngay cả với mảng trừ khi chúng ta chắc chắn kích thước của nó luôn được cố định.

LinkedList<T> là một triển khai cơ bản của danh sách liên kết kép (doubly-linked list). Nghĩa là bạn có thể thêm hoặc xóa phần tử ở giữa của tập hợp rất nhanh (vì nó không có phần tử nào bị di chuyển lên xuống trong bộ nhớ), nhưng bạn cũng không thể truy cập đến vị trí của phần tử thông qua chỉ số nhanh được. Hầu hết chúng ta hay dùng List<T> hơn là LinkedList<T> trừ khi bạn làm rất nhiều thao tác thêm hay xóa phần tử, trong các trường hợp đó thì LinkedList<T> sẽ tốt hơn.

HashSet<T> là một tập hợp không được sắp xếp của một danh sách các phần tử duy nhất. Nghĩa là các tập hợp này không có các phần tử trùng nhau và không được sắp xếp. The logic, tập hợp này tương tự như a Dictionary<TKey,TValue> với cả TKey  và TValue được coi như cùng một đối tượng. Collection này rất hữu ích cho việc duy trì một tập hợp các phần tử mà bạn muốn kiểm tra các phần tử trùng nhau. Ví dụ, nếu bạn nhận một hóa đơn với một mã nhà cung cấp, bạn có thể muốn kiểm tra xem mã nhà cung cấp này có thuộc về một tập hợp mã có sẵn mà bạn đang quản lý không. Trong trường hợp này thì HashSet<T> hữu ích và rất nhanh khi bạn coi việc tìm kiếm hóa đơn là thứ yếu. Một lần nữa, giống Dictionary, kiểu T nên có một triển khai của GetHashCode() và Equals() hoặc bạn nên triển khai interface IEqualityComparer<T> cho HashSet<T> khi xây dựng.

SortedSet<T> với HashSet<T> giống như SortedDictionary<TKey,TValue> với Dictionary<TKey,TValue>. SortedSet<T> là một cây nhị phân với key và value được nằm trên cùng đối tượng. Một lần nữa khi bạn thêm/xóa hay tìm kiếm với SortedSet<T> thì thời gian sẽ là O (log n) – nhưng bạn có thể lặp qua các phần tử theo thứ tự. Để collection này có hiệu quả, kiểu T phải được implement IComparable<T> hoặc bạn cần một IComparer<T> từ bên ngoài.

Cuối cùng, Stack<T> và Queue<T> là hai collection đặc biệt cho phép bạn quản lý các đối tượng tuần tự trong một cách rất cụ thể. Stack<T> là một ngăn chứa vào sau lấy ra trước (LIFO) khi các phần tử được thêm và xóa từ trên cùng của stack. Thông thường điều này hữu ích trong các trường hợp mà bạn muốn các thao tác với ngăn xếp và có thể quay lại undo các hành động theo thứ tự khi cần. Queue<T> là một trường hợp khác nó xử lý theo vào trước ra trước tức là thêm mới phần tử vào cuối cùng của queue và remove ở vị trí đầu tiên. Nó hữu ích khi bạn cnaf xử lý các phần tử theo thứ tự mà chúng được thêm vào như máy in giấy hoặc xếp hàng mua đồ.

Trên đây là các collection cơ bản, các bạn có thể xem bảng tổng hợp.

Các collection nguyên bản được xem xét thôi không hỗ trợ bởi các nhà phát triển và chính Microsoft. Thật vậy, họ chỉ ra rằng hầu hết chúng ta dùng các collection generic và concurrent collection chứ ít khi dùng các collection nguyên bản trừ khi bạn phải làm việc với code .NET trên phiên bản cũ.

Bởi vì các collection này đã lỗi thời, hãy làm bảng tóm tắt về các collection nguyên bản và đi kèm với nó là các collection generic tương ứng:

• ArrayList
  • Động, lưu trữ liên tiếp tập đối tượng.
  • Nên dùng generic collection List<T>
• Hashtable
  • Có liên kết, tập hợp không được sắp xếp theo cặp Key-value
  • Nên dùng Dictionary<TKey,TValue>
• Queue
  • Tập đối tượng sử dụng cơ chế FIFO
  • Nên dùng Queue<T>
• SortedList
  • Có liên kết, tập hợp được sắp xếp theo cặt key-value
  • Nên dùng SortedList<T>
• Stack
  • Tập đối tượng cơ chế LIFO
  • Nên dùng Stack<T> hơn

Nhìn chung, các collection cũ hơn không hỗ trợ kiểu strong type và trong nhiều trường hợp performance của nó không được tốt như anh em generic của nó. Một lý do duy nhất để bạn phải quay về dùng chúng ta chúng ta phải code để tương thích với các dự án sử dụng phiên bản .NET cũ.

Các collection concurrent được bổ sung trong .NET 4.0 và được đặt trong namespace System.Collections.Concurrent. Các collection này được tối ưu cho việc sử dụng trong trường hợp chạy đa luồng.

Concurrent queue, stack và dictionary làm việc nhiều hơn bạn nghĩ. Bag và blocking collection thì ít dùng hơn. Dưới đây là bản tóm tắt:

• ConcurrentQueue
  • Phiên bản thread-safe phiên bản của Queue (FIFO).
• ConcurrentStack
  • Phiên bản thread-safe của stack (LIFO).
• ConcurrentBag
  • Collection không được sắp xếp của các đối tượng phiên bản Thread-safe.
  • Tối ưu cho các trường hợp một thread có thể cả đọc và ghi.
• ConcurrentDictionary
  • Phiên bản thread-safe của dictionary.
  • Tối ưu cho nhiều thao tác đọc (cho phép nhiều luồng đọc)
• BlockingCollection
  • Collection bao bọc triển khai mô hình nhà cung cấp và thuê bao.
  • Luồn đọc có thể khóa cho đến khi các phần tử có sẵn để đọc.
  • Luồng ghi có thể bị khóa cho đến khi không gian có sẵn đến ghi.

.NET Base Class Library có nhiều các collection được xây dựng sẵn giúp bạn lưu trưc và thao tác với dữ liệu. Hiểu cơ chế của các collection nyaf làm việc ra sao và biết khi nào cần sử dụng collection nào là một trong những kỹ năng cần thiết để viết code tối ưu hơn. Chọn sai collection cho chương trình có thể làm code của bạn chậm hơn rất nhiều hoặc ngay cả khó hơn cho việc bảo t rì nếu bạn chọn một cái không thực thi tốt hoặc không phù hợp với bài toán.

Nhớ là tránh dùng các collection nguyên bản và nên chọn các collection generic. Nếu bạn cần xử lý song song đa luồng, bạn có thể dùng các collection generic nếu data chỉ đọc hoặc xem xét dùng các concurrent collection cho việc thao tác nếu bạn đang chạy .NET 4.0 hoặc cao hơn.

Trích nguồn từ: (geekswithblogs.net)