Xây dựng từ điển được sắp xếp bằng ToDictionary

Question

Tôi không phải là chuyên gia về C# và LINQ.

Tôi có một Dictionary, mà tôi hiểu bảng băm, tức là, các khóa không được sắp xếp.

dataBase = new Dictionary<string, Record>() 

Record là lớp do người dùng xác định chứa một số dữ liệu cho chuỗi khóa nhất định.

Tôi tìm thấy một ví dụ thú vị có thể chuyển đổi Dictionary vào này một sắp xếp điển bởi LINQ:

var sortedDict = (from entry in dataBase orderby entry.Key ascending select entry) 
.ToDictionary(pair => pair.Key, pair => pair.Value); 

Mã này hoạt động một cách chính xác. Kết quả sortedDict được sắp xếp theo các khóa.

Câu hỏi: Tôi thấy rằng sortedDict vẫn là một bảng băm, một loại:

System.Collections.Generic.Dictionary<string, Record> 

tôi mong đợi từ điển kết quả phải là một loại map như trong C++ STL, mà thường được thực hiện như một cây nhị phân (cân bằng) để duy trì thứ tự của các phím. Tuy nhiên, từ điển kết quả vẫn là một bảng băm.

Cách sortedDict có thể duy trì thứ tự? Bảng băm không thể giữ thứ tự của các khóa. Việc triển khai C# 'Generic.Dictionary' của C# khác với bảng băm điển hình?

Answer 1

Dictionary duy trì hai cấu trúc dữ liệu: một mảng phẳng đó là giữ để chèn đếm và bảng băm để thu hồi theo khóa.

Nếu bạn sử dụng ToDictionary() trên bộ được sắp xếp, nó sẽ theo thứ tự khi được liệt kê, nhưng nó sẽ không được duy trì theo thứ tự. Bất kỳ mục mới được chèn nào sẽ được thêm vào mặt sau khi liệt kê.

Chỉnh sửa: Nếu bạn muốn dựa vào hành vi này, tôi khuyên bạn nên xem tài liệu MSDN để xem liệu điều này có được đảm bảo hay không.

Answer 2

SortedDictionary có sẵn Dictionary hiện tại trong hàm tạo để tạo SortedDictionary rất dễ dàng.

Nhưng bạn có thể làm cho nó trở thành một phương pháp mở rộng nếu bạn muốn thì bạn có thể sử dụng dataBase.ToSortedDictionary()

public static SortedDictionary<K, V> ToSortedDictionary<K,V>(this Dictionary<K, V> existing) 
{ 
    return new SortedDictionary<K, V>(existing); 
} 

Answer 3

mã linq sẽ tạo từ điển được sắp xếp, nhưng việc sắp xếp được thực hiện bởi LINQ, không phải từ điển, trong khi SortedDictionary nên duy trì việc sắp xếp theo chính nó.

để có được một cuốn từ điển được sắp xếp, sử dụng new SortedDictionary<string, Record>(yourNormalDictionary);

nếu bạn muốn làm cho nó dễ tiếp cận hơn, sau đó bạn có thể viết một mở rộng của IEnumerable:

public static class Extensions 
{ 
    public static SortedDictionary<T1, T2> ToSortedDictionary<T1, T2>(this IEnumerable<T2> source, Func<T2, T1> keySelector) 
    { 
     return new SortedDictionary<T1, T2>(source.ToDictionary(keySelector)); 
    } 
}