Tại sao không có Dictionary.TrimExcess()?

Question

Trong .NET, có một hàm tạo cho Dictionary<TKey, TValue> lấy một tham số, int capacity. Điều này giống với nhiều bộ sưu tập khác như List<T>, Queue<T> và Stack<T>; hơn nữa, theo số the MSDN documentation:

Dung lượng của từ điển là số phần tử có thể được thêm vào từ điển trước khi thay đổi kích thước là cần thiết. Khi các phần tử được thêm vào một từ điển, dung lượng được tự động tăng lên theo yêu cầu bằng cách tái phân bổ mảng nội bộ.

này nghe có vẻ với tôi khá nhiều giống như với các bộ sưu tập khác như List<T>, vv Kể từ khi những bộ sưu tập đặc trưng tự động thay đổi kích thước hành vi khi cần thiết và do đó khả năng có công suất lớn hơn yêu cầu, hầu hết trong số họ được trang bị TrimExcess. Điều này rất tiện lợi nếu, giả sử bạn đang thêm một số mục không xác định vào bộ sưu tập cùng một lúc và sau đó bạn sẽ không thêm bất kỳ mục bổ sung nào.

Tại sao Dictionary<TKey, TValue> không có phương thức này TrimExcess?

(Tuyên bố từ chối trách nhiệm: Tôi khá quen thuộc với phản hồi "tính năng không tồn tại theo mặc định"; tôi đoán tôi hầu như không biết liệu có lý do cụ thể nào không ?:cho Dictionary sẽ khó thực hiện hơn nhiều so với các bộ sưu tập đơn giản như List.)

Answer 1

Mỗi Từ điển MSDN được triển khai dưới dạng bảng băm. Nếu bạn cắt giảm dư thừa bạn sẽ phải đưa ra một thuật toán mà vẫn cung cấp gần O (1) thời gian tra cứu trong những gì có hiệu quả sẽ là một danh sách được sắp xếp ngẫu nhiên.

Answer 2

Tôi đoán rằng trong trường hợp này, đối số công suất giúp xác định hàm băm cũng như số lượng nhóm; thay đổi kích thước/cắt tỉa một bộ sưu tập dữ liệu thưa thớt sẽ yêu cầu tính toán lại các băm của tất cả các mục được lưu trữ còn lại.

Answer 3

Đây là một phần đoán: Từ điển được "đặt hàng" dưới dạng bảng băm. Dung lượng được dành riêng, không chỉ đơn giản là một loạt các địa chỉ bộ nhớ miễn phí trên đầu trang của từ điển của bạn. Thay vào đó, nó bao gồm các phòng trống trong suốt từ điển. Điều này được thực hiện để làm cho thêm/di chuyển/loại bỏ vv rất hiệu quả. Nếu bạn có phương thức TrimExcess cho Từ điển, toàn bộ từ điển sẽ phải sao chép mọi thứ sang một vị trí mới mà không có bất kỳ khoảng trống nào giữa các phần tử.

Thực tế: các khoảng trống nên giữ nguyên nếu lợi ích của bảng băm bị vô hiệu, cắt tỉa (TrimExcess), nếu được triển khai, chỉ nên cắt nội bộ ValueCollection.

Cập nhật: mở rộng và thay đổi từ bệnh được lựa chọn của tôi
Cập nhật:the BCL team says TrimExcess for Dictionaries "could be useful".
Cập nhật: yêu cầu tính năng được giải quyết là Sẽ không khắc phục được: "Thật không may, chúng tôi sẽ không thể thực hiện việc này cho bản phát hành tiếp theo của .NET, vì vậy tôi giải quyết vấn đề này là không khắc phục . "

Answer 4

Thực ra tôi là người đã yêu cầu Microsoft triển khai TrimExcess. Tôi đã trình bày nhiều hơn một bài viết đề cập đến từ điển và trong mọi trường hợp tôi đã triển khai TrimExcess.Trên thực tế, Thay đổi kích thước được sử dụng khi các nhóm quá nhỏ có thể được gọi khi tăng hoặc giảm kích thước của các nhóm.

Hôm nay tôi vừa công bố một bài viết, nó là một C++ thực hiện một cuốn từ điển, mà hỗ trợ TrimExcess: http://www.codeproject.com/Articles/761040/A-NET-like-Dictionary-in-Cplusplus

thi khác (NET) có thể được tìm thấy trong bài viết này: http://www.codeproject.com/Articles/548406/Dictionary-plus-Locking-versus-ConcurrentDictionar