[Python-ideas] Re: Access (ordered) dict by index; insert slice

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().