Just a quick update. I've been analysing and profile the behaviour of my new dict and messing about with various implementation options. I've settled on a new implementation. Its the same basic idea, but with better locality of reference for unshared keys. Guido asked:
Another question: a common pattern is to use (immutable) class variables as default values for instance variables, and only set the instance variables once they need to be different. Does such a class benefit from your improvement?
For those instances which keep the default, yes. Otherwise the answer is, as Martin pointed out, it could yes provided that adding a new key does not force a resize. Although it is a bit arbitrary when a resize occurs. The new version will incorporate this behaviour. Expect version 2 soon. Cheers, Mark.