Làm cách nào để tránh hết bộ nhớ bằng TDictionary ngày càng tăng?

Question

TDictionary<TKey,TValue> sử dụng một mảng nội bộ được tăng lên gấp đôi nếu nó là đầy đủ:

newCap := Length(FItems) * 2; 
if newCap = 0 then 
    newCap := 4; 
Rehash(newCap); 

này hoạt động tốt với số lượng trung bình các mặt hàng, nhưng nếu người ta được đến giới hạn trên nó là rất đáng tiếc, bởi vì nó có thể ném một EOutOfMemory ngoại trừ ngay cả khi có gần một nửa bộ nhớ vẫn có sẵn.

Có cách nào ảnh hưởng đến hành vi này không? Các lớp thu thập khác đối phó với kịch bản này như thế nào?

Answer 1

Bạn cần hiểu cách hoạt động của từ điển. Từ điển chứa danh sách "nhóm băm" nơi các mục bạn chèn được đặt. Đó là một số hữu hạn, vì vậy một khi bạn điền vào nó, bạn cần phải phân bổ nhiều xô hơn, không có cách nào xung quanh nó. Vì việc gán các đối tượng vào các nhóm dựa trên kết quả của hàm băm, bạn không thể chỉ thêm các thùng vào cuối mảng và đặt các công cụ trong đó, bạn cần phân bổ lại toàn bộ danh sách các khối, tái băm tất cả mọi thứ và đặt nó trong (mới) tương ứng xô.

Với hành vi này, cách duy nhất để làm cho từ điển không cấp lại sau khi đã đầy đủ để đảm bảo nó không bao giờ bị đầy. Nếu bạn biết số lượng các mục bạn sẽ chèn vào trong từ điển, hãy chuyển nó thành một tham số cho hàm khởi tạo và bạn sẽ hoàn thành, không còn thêm các từ điển.

Nếu bạn không thể làm điều đó (bạn không biết số lượng các mục bạn sẽ có trong từ điển), bạn sẽ cần phải xem xét lại những gì khiến bạn chọn TDictionary ở vị trí đầu tiên và chọn cấu trúc dữ liệu cung cấp sự thỏa hiệp tốt hơn cho thuật toán cụ thể của bạn. Ví dụ bạn có thể sử dụng cây tìm kiếm nhị phân, vì chúng làm cân bằng bằng cách xoay thông tin trong các nút hiện có, không cần phân bổ lại bao giờ.