(original) (raw)

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)