Sự khác nhau giữa HashSet <T> và Danh sách <T> là gì?

Question

Bạn có thể giải thích sự khác biệt giữa HashSet<T> và List<T> trong .NET không?

Có thể bạn có thể giải thích bằng ví dụ trong trường hợp nào HashSet<T> nên được ưu tiên hơn List<T>?

Cảm ơn.

Answer 1

Không giống như một danh sách <> ...

1. Một HashSet là một danh sách không có thành viên trùng lặp.

2. Bởi vì một HashSet bị hạn chế để chứa các mục chỉ duy nhất, cấu trúc bên trong được tối ưu hóa cho tìm kiếm (so với một danh sách) - đó là nhanh hơn đáng kể

3. Thêm vào một HashSet trả về một boolean - false nếu Ngoài thất bại do đã tồn tại trong Set ) có thể thực hiện các hoạt động bộ toán học chống lại một Set:. Union/Intersection/IsSubsetOf, vv

4. HashSet không thực hiện IList chỉ ICollection

5. Bạn không thể sử dụng các chỉ mục với một HashSet, chỉ các điều tra viên.

Lý do chính để sử dụng HashSet sẽ là nếu bạn quan tâm đến việc thực hiện các hoạt động Thiết lập.

Với 2 bộ: hashSet1 và hashSet2

//returns a list of distinct items in both sets 
HashSet set3 = set1.Union(set2); 

ruồi so với một hoạt động tương đương sử dụng LINQ. Nó cũng là neater để viết!

Answer 2

Danh sách không nhất thiết phải là duy nhất, trong khi hàm băm là, cho một.

Answer 3

A HashSet<T> là lớp được thiết kế để cung cấp cho bạn O(1) tra cứu để ngăn chặn (tức là, bộ sưu tập này có chứa một đối tượng cụ thể không và cho tôi biết câu trả lời nhanh).

A List<T> là một lớp học được thiết kế để cung cấp cho bạn bộ sưu tập có quyền truy cập ngẫu nhiên O(1) hơn có thể phát triển động (nghĩ mảng động). Bạn có thể kiểm tra ngăn chặn trong thời gian O(n) (trừ khi danh sách được sắp xếp, sau đó bạn có thể thực hiện tìm kiếm nhị phân trong thời gian O(log n)).

Maybe you can explain with an example in what cases HashSet<T> should be prefered against List<T>

Khi bạn muốn kiểm tra ngăn trong O(1).

Answer 4

Danh sách là bộ sưu tập theo thứ tự các đối tượng thuộc loại T không giống như mảng mà bạn có thể thêm và xóa các mục nhập.

Bạn sẽ sử dụng danh sách nơi bạn muốn tham chiếu các thành viên theo thứ tự bạn đã lưu trữ chúng và bạn đang truy cập chúng theo vị trí chứ không phải chính mục đó.

Một HashSet giống như một từ điển mà bản thân mục đó là khóa cũng như giá trị, thứ tự không được đảm bảo.

Bạn sẽ sử dụng một HashSet nơi bạn muốn kiểm tra xem một đối tượng là trong bộ sưu tập

Answer 5

Sử dụng một List<T> khi bạn muốn:

• Lưu trữ một bộ sưu tập của các mục trong một trật tự nhất định.

Nếu bạn biết chỉ mục của mục bạn muốn (thay vì giá trị của bản thân mục đó), hãy truy cập là O(1). Nếu bạn không biết chỉ mục, việc tìm kiếm mục sẽ mất nhiều thời gian hơn, O(n) cho một bộ sưu tập chưa được phân loại.

Sử dụng một Hashset<T> khi bạn muốn:

• Nhanh chóng tìm hiểu xem một đối tượng nào đó được chứa trong một bộ sưu tập.

Nếu bạn biết tên của điều bạn muốn tìm, Tra cứu là O(1) (đó là phần 'băm'). Nó không duy trì thứ tự như List<T> và bạn không thể lưu trữ bản sao (thêm một bản sao không có hiệu lực, đó là phần 'Đặt').

Ví dụ về thời điểm sử dụng Hashset<T> sẽ là nếu bạn muốn tìm hiểu xem một từ được chơi trong trò chơi Scrabble có phải là một từ hợp lệ bằng tiếng Anh (hoặc ngôn ngữ khác) hay không. Thậm chí tốt hơn là nếu bạn muốn xây dựng một dịch vụ web được sử dụng bởi tất cả các phiên bản trực tuyến của một trò chơi như vậy.

A List<T> sẽ là cấu trúc dữ liệu tốt để tạo bảng điểm để theo dõi điểm của người chơi.

Answer 6

Danh sách là danh sách có thứ tự. Đó là

• truy cập bằng một chỉ số nguyên
• thể chứa bản sao
• có một trật tự có thể dự đoán

HashSet là một tập hợp. Nó:

• thể chặn mục trùng lặp (xem Add(T))
• Không đảm bảo trật tự của các mục trong tập
• Có hoạt động bạn mong chờ trên một tập hợp, ví dụ , IntersectWith, IsProperSubsetOf, UnionWith.

Danh sách phù hợp hơn khi bạn muốn truy cập bộ sưu tập giống như một mảng mà bạn có thể chắp thêm, chèn và xóa các mục. HashSet là một lựa chọn tốt hơn nếu bạn muốn xử lý bộ sưu tập của mình như một "túi" của các mục mà thứ tự không quan trọng hoặc khi bạn muốn so sánh nó với các bộ khác bằng cách sử dụng các hoạt động như IntersectWith hoặc UnionWith.

Answer 7

Để cho phép chính xác hơn, hãy chứng minh bằng các ví dụ,

Bạn không thể sử dụng HashSet như trong ví dụ sau.

HashSet<string> hashSet1 = new HashSet<string>(){"1","2","3"}; 
for (int i = 0; i < hashSet1.Count; i++) 
    Console.WriteLine(hashSet1[i]); 

hashSet1[i] sẽ tạo ra một lỗi:

Cannot apply indexing with [] to an expression of type 'System.Collections.Generic.HashSet'

Bạn có thể dùng lệnh foreach:

foreach (var item in hashSet1) 
    Console.WriteLine(item); 

---

Bạn không thể thêm các mục trùng lặp để HashSet khi Danh sách cho phép bạn làm điều này và trong khi bạn đang thêm một mục vào HashSet, bạn có thể kiểm tra xem nó có chứa s mục hay không.

HashSet<string> hashSet1 = new HashSet<string>(){"1","2","3"}; 
if (hashSet1.Add("1")) 
    Console.WriteLine("'1' is successfully added to hashSet1!"); 
else 
    Console.WriteLine("'1' could not be added to hashSet1, because it contains '1'"); 

---

HashSet có một số chức năng hữu ích như IntersectWith, UnionWith, IsProperSubsetOf, ExceptWith, SymmetricExceptWith, vv

IsProperSubsetOf:

HashSet<string> hashSet1 = new HashSet<string>() { "1", "2", "3", "4" }; 
HashSet<string> hashSet2 = new HashSet<string>() { "2", "4", "6", "8" }; 
HashSet<string> hashSet3 = new HashSet<string>() { "1", "2", "3", "4", "5" }; 
if (hashSet1.IsProperSubsetOf(hashSet3)) 
    Console.WriteLine("hashSet3 contains all elements of hashSet1."); 
if (!hashSet1.IsProperSubsetOf(hashSet2)) 
    Console.WriteLine("hashSet2 does not contains all elements of hashSet1."); 

UnionWith:

HashSet<string> hashSet1 = new HashSet<string>() { "3", "4" }; 
HashSet<string> hashSet2 = new HashSet<string>() { "2", "4", "6", "8" }; 
hashSet1.UnionWith(hashSet2); //hashSet1 -> 3, 2, 4, 6, 8 

IntersectWith:

HashSet<string> hashSet1 = new HashSet<string>() { "3", "4", "8" }; 
HashSet<string> hashSet2 = new HashSet<string>() { "2", "4", "6", "8" } 
hashSet1.IntersectWith(hashSet2);//hashSet1 -> 4, 8 

ExceptWith:

HashSet<string> hashSet1 = new HashSet<string>() { "1", "2", "3", "5", "6" }; 
HashSet<string> hashSet2 = new HashSet<string>() { "1", "2", "3", "4" }; 
hashSet1.ExceptWith(hashSet2);//hashSet1 -> 5, 6 

SymmetricExceptWith:

HashSet<string> hashSet1 = new HashSet<string>() { "1", "2", "3", "5", "6" }; 
HashSet<string> hashSet2 = new HashSet<string>() { "1", "2", "3", "4" }; 
hashSet1.SymmetricExceptWith(hashSet2);//hashSet1 -> 4, 5, 6 

---

Bằng cách này, thứ tự không được bảo quản trong HashSets. Trong ví dụ này, chúng tôi đã thêm yếu tố "2" cuối cùng nhưng nó là theo thứ tự thứ hai:

HashSet<string> hashSet1 = new HashSet<string>() { "3", "4", "8" }; 
hashSet1.Add("1"); // 3, 4, 8, 1 
hashSet1.Remove("4"); // 3, 8, 1 
hashSet1.Add("2"); // 3, 2 ,8, 1 

Answer 8

Nếu bạn quyết định áp dụng các cấu trúc dữ liệu để sử dụng thực tế trong phát triển dựa trên dữ liệu, một HashSet là RẤT hữu ích trong việc thử nghiệm nhân rộng đối với nguồn bộ điều hợp dữ liệu, để làm sạch và di chuyển dữ liệu. Ngoài ra, nếu sử dụng Lớp DataAnnotations, người ta có thể thực hiện Logic khóa trên thuộc tính lớp và kiểm soát có hiệu quả một chỉ mục tự nhiên (nhóm hoặc không) với một HashSet, điều này sẽ rất khó khăn trong việc thực hiện Danh sách. Một lựa chọn mạnh mẽ cho việc sử dụng danh sách là thực hiện generics cho nhiều phương tiện trên một Model View, chẳng hạn như gửi danh sách các lớp đến một khung nhìn MVC cho một DropDownList Helper, và cũng để gửi như một cấu trúc JSON thông qua WebApi. Danh sách này cho phép logic thu thập lớp điển hình và giữ tính linh hoạt cho một "Giao diện" hơn như cách tiếp cận để tính toán một mô hình xem đơn lẻ cho các phương tiện khác nhau.