Fibonacci Hashing revisted

[Richard B. Kreckel]

On Thu, 2 May 2002, Alexander Frink wrote:
> On Tue, 30 Apr 2002, Richard B. Kreckel wrote:
> > suggesting an improvement of a factor 260 or 270.  At the same time,
> > the timings got only very marginally better, indicating that there is
> > nothing to be gained by better hash functions, even perfect
> > collision-free ones (if they would exist), since deep traversals caused by
> > equal objects outweight deep traversals caused by hash collisions of
> > different objects.
> 
> Did you also measure the ratio between comparisons which turn out
> to be equal to those turning out to be different?

Why does this matter?  I mean, sure, the comparisons which turn out to be
equal are the ones that dominate.  They are about three orders of
magnitude more frequent than the ones that turn out to be different.  
This is why enhancements to the hashing are not going to help any more.

Cheers
    -richy.
-- 
Richard B. Kreckel
<Richard.Kreckel at Uni-Mainz.DE>
<http://wwwthep.physik.uni-mainz.de/~kreckel/>