Why dictionaries do not change after deletion?

Question

Apparently deleting entries in the dictionary does not cause any changes. Resizing starts only after adding a record.

This can be seen from the following:

# 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 

as well as a question about SO (from what I found). set behave similarly to what you would expect according to what dicts do.

list s, on the other hand, resize when the new size becomes half the size already selected; this is indicated in the 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. */ 

Why dictionaries (and, indirectly, sets) do not use such a trick and instead wait for a new entry to be entered? The behavior described applies to Python 2.7 and 3.x (up to Python 3.7.0a0).

Answer 1

This is somewhat explained in Objects/dictnotes.txt , a companion file containing various notes on the implementation of dict:

Dictionary operations containing only one key can be O (1), if only resizing. By checking resizing only when the dictionary can grow (and resizing may be required), other operations remain O (1), and the chances of resizing or fragmenting the memory are reduced. In particular, an algorithm that frees the dictionary from repeatedly calling .pop will not be resized, which may not be necessary at all, because the dictionary is ultimately discarded completely.

One important consideration is that compressing the list buffer is very simple, and compressing the internal dict hash table is a much more complicated operation.