Mở đầu
Lâu nay khi lập trình chúng ta chủ yếu sử dụng kiểu dữ liệu List để thao tác với các collection, mặc dù đây không phải là kiểu collection duy nhất trong .NET nhưng các lập trình viên đã quá quen thuộc với việc sử dụng kiểu List nên thói quen này không phải dễ thay đổi.
Trong bài viết này chúng ta sẽ cùng so sánh tốc độ của kiểu List và HashSet (một kiểu collection xuất hiện bắt đầu từ .NET 3.5) để biết được khi nào thì nên sử dụng List và khi nào thì nên dùng kiểu HashSet.
Kiểu List<T>
Kiểu List<T> chứa một danh sách item, truy cập qua chỉ số. Không giống như kiểu mảng là một kiểu cố định kích thước, list tự động tăng kích thước khi cần. Đây chính là lý do tại sao List đôi khi còn được gọi là kiểu mảng động.
Cấu trúc bên trong của List thực chất là một mảng, nếu mảng này hết chỗ nó sẽ tạo ra một mảng mới lớn hơn và copy toàn bộ item từ mảng cũ sang mảng mới. Ngày nay thì chúng ta thấy hầu hết lập trình viên đều dùng kiểu List thay vì kiểu mảng. Tuy nhiên trong một số trường hợp nếu item là cố định thì bạn nên dùng kiểu mảng để có performance tốt hơn.
Một số phép toán trên kiểu List
private static void ListOperation()
{
var intList = new List<int>(100);
intList.Add(5);
intList.RemoveAt(0);
//Add item at index
intList.Insert(0, 10);
intList.Insert(1, 7);
var first = intList[0];
// Index of an item
var index = intList.IndexOf(4);
// Check List contains item
bool contain = intList.Contains(4);
// Iterate over all objects
foreach (var item in intList)
Console.WriteLine(item);
}
Thêm/Xóa phần tử ở đầu hoặc giữa List
Nếu bạn cần thêm/xóa một phần tử ở đầu hoặc giữa List thì nó sẽ cần dịch chuyển một hoặc nhiều item. Trường hợp xấu nhất, nếu bạn thêm/xóa một phần tử ở đầu List nó sẽ phải dịch tất cả item còn lại trong List. Nếu List càng lớn thì sẽ càng mất thời gian và resource để thực hiện.
Thêm/Xóa phần tử ở cuối List
Thêm/Xóa một phần tử ở cuối List ngược lại rất nhanh và không phụ thuộc vào kích thước của List vì không item nào cần phải dịch chuyển.
Tìm kiếm một phần tử
Khi tìm kiếm một phần tử bằng một số hàm như IndexOf, Contains, Find thì kiểu List sẽ thực hiện duyệt qua tất cả các item để tìm ra phần tử đó. Trong trường hợp xấu nhất, nếu phần tử nằm ở cuối List thì tất cả các item cần được duyệt qua.
Truy cập một phần tử bởi chỉ số
Là phép toán thực hiện rất nhanh vì bản chất bên trong List là một mảng. Tốc độ truy cập không bị ảnh hưởng bởi độ lớn của List.
Kiểu HashSet<T>
HashSet là kiểu xuất hiện từ .NET 3.5, nó chứa các item duy nhất, nghĩa là nó không thể chứa các item trùng lặp và thứ tự của item cũng không quan trọng. VD: {a,b,c} tương đương {c,b,a}
Sử dụng HashSet khi bạn cần tìm kiếm nhanh trên một tập các item không lặp. VD trong bài toán thực tế mình đang phải làm là kiểm tra một danh sách Order có nằm trong một danh sách Order khác không?
Kiểu HashSet dựa trên hàm hash để tính toán ra chỉ số của item vì vậy phép tìm kiếm có tốc độ rất nhanh.
Dưới đây là một số phép toán trên kiểu HashSet
private static void HashSetOperation()
{
var intHashSet = new HashSet<int>() { 1, 2, 3, 4, 5 };
intHashSet.Add(10);
intHashSet.Remove(5);
//Check Set contains item
bool contain = intHashSet.Contains(1);
// Iterate over all objects
foreach (var item in intHashSet)
Console.WriteLine(item);
//Delete all items
intHashSet.Clear();
}So sánh tốc độ List<T> và HashSet<T>
Mặc dù trong các tài liệu đều chỉ ra kiểu HashSet nhanh hơn List nhưng thực tế có phải luôn luôn như vậy? Chúng ta sẽ cùng kiểm nghiệm qua một ví dụ benchmark đơn giản: Kiểm tra một danh sách có nằm trong một danh sách khác hay không:
private static void ListHashSetPerformanceBenchmark()
{
//const int COUNT = 50;
const int COUNT = 50000;
HashSet<int> intHashSet = new HashSet<int>();
Stopwatch stopWatch = new Stopwatch();
for (int i = 0; i < COUNT; i++)
{
intHashSet.Add(i);
}
stopWatch.Start();
for (int i = 0; i < COUNT; i++)
{
intHashSet.Contains(i);
}
stopWatch.Stop();
Console.WriteLine(stopWatch.Elapsed);
stopWatch.Reset();
List<int> intList = new List<int>();
for (int i = 0; i < COUNT; i++)
{
intList.Add(i);
}
stopWatch.Start();
for (int i = 0; i < COUNT; i++)
{
intList.Contains(i);
}
stopWatch.Stop();
Console.WriteLine(stopWatch.Elapsed);
}Kết quả thực hiện cho thấy sự khác nhau rõ rệt về performance:
50 item List.Contains mất 0.000018s, HashSet.Contains mất 0.000023s
50000 item List.Contains mất 9.38s, HashSet.Contains mất 0.002s
Từ kết quả trên có thể thấy rằng không phải lúc nào performance của HashSet cũng nhanh hơn List. Với số lượng item nhỏ (<50 item) thì tốc độ của List còn nhanh hơn so với HashSet nhưng khi số lượng item lớn thì lúc đó HashSet mới phát huy tác dụng, tốc độ của HashSet rất nhanh và không phụ thuộc vào số lượng item.
Kết luận
Kiểu List tương đối nhanh khi bạn truy cập item bằng index nhưng khi tìm kiếm một item trong List lớn (50 item trở lên) thì nó sẽ chậm dần. Ngược lại kiểu HashSet lại rất nhanh khi tìm kiếm trên một tập item lớn. Vì vậy mà tùy từng trường hợp cụ thể bạn cần lựa chọn kiểu collection cho phù hợp với bài toán của mình.