On 10.12.12 05:30, Raymond Hettinger wrote:

On Dec 9, 2012, at 10:03 PM, MRAB <python@mrabarnett.plus.com
<mailto:python@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)