Tại sao từ điển không thay đổi kích thước sau khi xóa?

Question

Rõ ràng xóa các mục trong từ điển không kích hoạt bất kỳ thay đổi kích thước nào. Thay đổi kích thước chỉ được kích hoạt sau khi bạn thêm mục nhập.

Điều này có thể được nhìn thấy từ sau:

# Drastic example, nobody does such 
# things with dicts FWIK 
from sys import getsizeof 

d = {i:i for i in range(100)} 
print(getsizeof(d)) # 4704 
for i in range(100): 
    del d[i] # similarly with pop 
print(getsizeof(d)) # 4704 
d[0] = 1 # triggers resize 

cũng như từ a question on SO (từ những gì tôi đã tìm thấy). set s hoạt động theo cách tương tự, được dự kiến ​​sẽ phù hợp với những gì dicts làm. Mặt khác, kích thước

list s, thay đổi kích cỡ khi kích thước mới trở thành một nửa số đã được phân bổ; này được trình bày trong một list_resize comment:

/* Bypass realloc() when a previous overallocation is large enough 
    to accommodate the newsize. If the newsize falls lower than half 
    the allocated size, then proceed with the realloc() to shrink the list. 
*/ 

Tại sao nó mà điển (và, gián tiếp, bộ) không sử dụng một thủ thuật tương tự và thay vào đó chờ đợi cho một mục mới sẽ được chèn vào? Hành vi được mô tả áp dụng cho Python 2.7 và 3.x (lên đến Python 3.7.0a0).

Answer 1

này phần nào giải thích trong Objects/dictnotes.txt, một file đồng hành chứa ghi chú khác nhau về việc thực hiện dict:

điển hoạt động liên quan đến chỉ một chìa khóa duy nhất có thể là O (1) trừ khi thay đổi kích thước là có thể. Bằng cách chỉ kiểm tra kích thước khi từ điển có thể phát triển (và có thể yêu cầu kích thước), các hoạt động khác vẫn là O (1) và tỷ lệ phân chia kích thước hoặc phân mảnh bộ nhớ bị giảm. Cụ thể, một thuật toán làm trống từ điển bằng cách liên tục gọi .pop sẽ không thấy thay đổi kích thước, có thể không phải là cần thiết vì tất cả từ điển cuối cùng bị loại bỏ hoàn toàn.

Một lưu ý quan trọng là việc thu gọn bộ đệm của danh sách thực sự dễ dàng, trong khi thu hẹp bảng băm nội bộ của dict là thao tác phức tạp hơn nhiều.