• Tim Peters's avatar
    Implement an old idea of Christian Tismer's: use polynomial division · 15d4929a
    Tim Peters authored
    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.
    15d4929a
dictobject.c 45.5 KB