I just had an idea: we have mp->ma_used and keys->dk_nentries. holes = mp->ma_keys->dk_nentries - mp->ma_used
is the number of holes in the dict. So, if holes == 0, you have O(1). But, if the dict has holes, you can't have O(1), but you can speedup the check of the entry by counting the NULLs in the for loop. When the number of NULLs reaches holes, you can jump safely to the dict entry you need. In this case, O(n) can happen only if the items are removed from the end, as with popitem(). _______________________________________________ Python-ideas mailing list -- python-ideas@python.org To unsubscribe send an email to python-ideas-le...@python.org https://mail.python.org/mailman3/lists/python-ideas.python.org/ Message archived at https://mail.python.org/archives/list/python-ideas@python.org/message/G4VO262RMJALR35G74B72PFCTXT524LQ/ Code of Conduct: http://python.org/psf/codeofconduct/
