On Nov 24, 2007 6:18 PM, Neil Toronto
Jim Jewett wrote:
I think this isn't quite true, because of DUMMY entries.
Insert key1. Insert key2 that wants the same slot. Register an observer that cares about key2 but not key1.
Delete key1. The key1 entry is replaced with DUMMY, but the entry for key2 is not affected.
Look up key2 (by some other code which hasn't already taken this shortcut) and the lookdict function (as a side effect) moves key2 to the better location that key1 no longer occupies. As described, I think this breaks your cache.
Good grief old chap, you freaked me out.
Turns out it all still works. Whether the lookdict functions used to move entries around I don't know, but now it doesn't. It's probably because deletions are so rare compared to other operations that it's not worth the extra logic in those tight little loops.
I don't know where Jim gets his information, but I don't recall that just looking up a key has ever moved entries around. You'd have to delete and re-add it to get it moved. (Or you'd have to hit the "rehash everything to a larger hash table" of course.) -- --Guido van Rossum (home page: http://www.python.org/~guido/)