Am 31.12.2011 13:03, schrieb Stephen J. Turnbull:
I don't know the implementation issues well enough to claim it is a solution, but this hasn't been mentioned before AFAICS:
While the dictionary probe has to start with a hash for backward compatibility reasons, is there a reason the overflow strategy for insertion has to be buckets containing lists? How about double-hashing, etc?
Python's dict implementation doesn't use bucket but open addressing (aka closed hashed table). The algorithm for conflict resolution doesn't use double hashing. Instead it takes the original and (in most cases) cached hash and perturbs the hash with a series of add, multiply and bit shift ops.