[Python-Dev] The Dictionary Gem is polished!

[Guido van Rossum]

> Problem: There are hash functions which are "good" in this sense,
> but they do not spread their randomness uniformly over the
> 32 bits.
> 
> Example: Integers use their own value as hash.
> This is ok, as far as the integers are uniformly distributed.
> But if they all contain a high power of two, for instance,
> the low bits give a very bad hash function.
> 
> Take a dictionary with integers range(1000) as keys and access
> all entries. Then use a dictionay with the integers shifted
> left by 16.
> Access time is slowed down by a factor of 100, since every
> access is a linear search now.

Ai.  I think what happened is this: long ago, the hash table sizes
were primes, or at least not powers of two!

I'll leave it to the more mathematically-inclined to judge your
solution...

--Guido van Rossum (home page: http://www.python.org/~guido/)