4 ms·
> Quadratic probing is used because it's very effective for unsuccessful lookups IS it really that good? If you end up having to probe a lot with linear probi
by zzleeper 10y ago
> Quadratic probing is used because it's very effective for unsuccessful lookups
IS it really that good?
If you end up having to probe a lot with linear probing, it is likely you have a bad hash function, which is the same reason you give against prime modulus (that they are a stopgap more than a solution).
Second, don't you end up having to jump all over the place, which means cache misses, that are way more expensive that a few probes on consecutive slots?
- thomasahle 10y agoI found the lecture notes that made this claim on internet archive https://web.archive.org/web/20031127062932/http://www.augustana.ca/~mohrj/courses/1999.fall/csc210/lecture_notes/hashing.html https://web.archive.org/web/20031127062932/http://www.august... It doesn't give any sources unfortunately.