On 10.12.12 05:30, Raymond Hettinger wrote:
On Dec 9, 2012, at 10:03 PM, MRAB <pyt...@mrabarnett.plus.com
<mailto:pyt...@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)
_______________________________________________
Python-Dev mailing list
Python-Dev@python.org
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe:
http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
