]> git.ipfire.org Git - thirdparty/Python/cpython.git/commit
Implement an old idea of Christian Tismer's: use polynomial division
authorTim Peters <tim.peters@gmail.com>
Sun, 27 May 2001 07:39:22 +0000 (07:39 +0000)
committerTim Peters <tim.peters@gmail.com>
Sun, 27 May 2001 07:39:22 +0000 (07:39 +0000)
commit15d4929ae4ad5206e2f7fa947d632bfba9b8bfd1
tree97abc7e1d28bcb8da6d31d3578759c70b0e2bf41
parentdac238bd46e95d1736cd6bee11df850a508f433b
Implement an old idea of Christian Tismer's:  use polynomial division
instead of multiplication to generate the probe sequence.  The idea is
recorded in Python-Dev for Dec 2000, but that version is prone to rare
infinite loops.

The value is in getting *all* the bits of the hash code to participate;
and, e.g., this speeds up querying every key in a dict with keys
 [i << 16 for i in range(20000)] by a factor of 500.  Should be equally
valuable in any bad case where the high-order hash bits were getting
ignored.

Also wrote up some of the motivations behind Python's ever-more-subtle
hash table strategy.
Misc/NEWS
Objects/dictobject.c