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

Jim Jewett jimjjewett at gmail.com
Mon Jan 2 02:23:16 CET 2012

On Sun, Jan 1, 2012 at 8:04 PM, Christian Heimes <lists at cheimes.de> wrote:
> 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.

It will only slow down missing keys that themselves hit more than N collisions.

Or were you assuming that I meant to switch the whole table, rather
than just that one key?  I agree that wouldn't work.

> You can't just change the hash algorithm in the middle of the work
> without a speed impact on lookups.

Right -- but there is nothing wrong with modifying the lookdict (and
insert_clean) functions to do something different after the Nth
collision than they did after the N-1th.


More information about the Python-Dev mailing list