[Python-Dev] More compact dictionaries with faster iteration

[Serhiy Storchaka]

On 10.12.12 05:30, Raymond Hettinger wrote:
> On Dec 9, 2012, at 10:03 PM, MRAB <python at mrabarnett.plus.com
> <mailto:python at mrabarnett.plus.com>> wrote:
>> What happens when a key is deleted? Will that leave an empty slot in
>> the entry array?
> Yes.  See the __delitem__() method in the pure python implemention
> at http://code.activestate.com/recipes/578375

You can move the last entry on freed place. This will preserve 
compactness of entries array and simplify and speedup iterations and 
some other operations.

def __delitem__(self, key, hashvalue=None):
         if hashvalue is None:
             hashvalue = hash(key)
         found, i = self._lookup(key, hashvalue)
         if found:
             index = self.indices[i]
             self.indices[i] = DUMMY
             self.size -= 1
             if index != size:
                 lasthash = self.hashlist[index]
                 lastkey = self.keylist[index]
                 found, j = self._lookup(lastkey, lasthash)
                 assert found
                 assert i != j
                 self.indices[j] = index
                 self.hashlist[index] = lasthash
                 self.keylist[index] = lastkey
                 self.valuelist[index] = self.valuelist[size]
                 index = size
             self.hashlist[index] = UNUSED
             self.keylist[index] = UNUSED
             self.valuelist[index] = UNUSED
         else:
             raise KeyError(key)