[Python-Dev] http://mail.python.org/pipermail/python-dev/2011-December/115172.html

Christian Heimes lists at cheimes.de
Mon Jan 2 02:04:38 CET 2012

Am 02.01.2012 01:37, schrieb Jim Jewett:
> Well, there is nothing wrong with switching to a different hash function after N
> collisions, rather than "in the first place".  The perturbation
> effectively does by
> shoving the high-order bits through the part of the hash that survives the mask.

Except that it won't work or slow down every lookup of missing keys?
It's absolutely crucial that the lookup time is kept as fast as possible.

You can't just change the hash algorithm in the middle of the work
without a speed impact on lookups. The size of the dict can shrink or
grow over time. This results into a different number of collisions for
the same string. Cuckoo hashing
(http://en.wikipedia.org/wiki/Hash_table#Collision_resolution) doesn't
sound feasible for us because it slows down lookup and requires an ABI
incompatible change for more hash slots on str/bytes/unicode instances.


PS: Something is wrong with your email client. Every of your replies
starts a new thread for me.

More information about the Python-Dev mailing list