On Dec 10, 2012, at 4:02 AM, Serhiy Storchaka
On 10.12.12 05:30, Raymond Hettinger wrote:
On Dec 9, 2012, at 10:03 PM, MRAB
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)
That is a clever improvement. Thank you. Using your idea (plus some tweaks) cleans-up the code a bit (simplifying iteration, simplifying the resizing logic, and eliminating the UNUSED constant). I'm updating the posted code to reflect your suggestion. Thanks again, Raymond