This issue tracker has been migrated to GitHub, and is currently read-only.
For more information, see the GitHub FAQs in the Python's Developer Guide.

Author neologix
Recipients jcon, mark.dickinson, neologix, pitrou, rhettinger, tim.peters
Date 2011-12-10.11:28:59
SpamBayes Score 8.8571244e-07
Marked as misclassified No
Message-id <1323516540.82.0.129469244432.issue10408@psf.upfronthosting.co.za>
In-reply-to
Content
This paper might be of interest:
http://www.siam.org/meetings/alenex05/papers/13gheileman.pdf

Basically, it concludes that most of the time, there's no speedup to be gained from the increased cached locality incurred by linear probing when the input sample differ from a uniform distribution. However, figure 1 shows a clear win with a uniform distribution, and figure 2 shows that even with a non-uniform distribution, there's still a gain as the load factor increases.
So if experiments show measurable improvements, this might be an interesting idea.
However, the problem with linear probing is that the performance will be much more dependent on the input distribution that with quadratic probing/double hashing, so this will definitely degrade with some workloads.

> The problem with linear probing, as noted in the comments, is that it 
> degrades performance quite a lot when the hashing function clusters 
> results. The solution I'm proposing is to apply an *initial* 
> perturbation, by multiplying the hash() with a prime number. 

I fail to see how this would avoid primary clustering: IIUC, you replace the hash function h(k) by h'(k), but you still use linear probing: an empty slot preceded by i filled slots has a probablility (i+1)/N of getting filled next (N being the total number of slots).
History
Date User Action Args
2011-12-10 11:29:00neologixsetrecipients: + neologix, tim.peters, rhettinger, mark.dickinson, pitrou, jcon
2011-12-10 11:29:00neologixsetmessageid: <1323516540.82.0.129469244432.issue10408@psf.upfronthosting.co.za>
2011-12-10 11:29:00neologixlinkissue10408 messages
2011-12-10 11:28:59neologixcreate